1/* $Id$ $Revision$ */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14
15/* comp.c:
16 * Written by Emden R. Gansner
17 *
18 * Support for "connected components". Components are either connected
19 * or have a port node or have a pinned node.
20 *
21 */
22
23/* use PRIVATE interface */
24#define FDP_PRIVATE 1
25
26#include <fdp.h>
27#include <comp.h>
28#include <pack.h>
29#include <assert.h>
30
31#define MARK(n) (marks[ND_id(n)])
32
33static void dfs(Agraph_t * g, Agnode_t * n, Agraph_t * out, char *marks)
34{
35 Agedge_t *e;
36 Agnode_t *other;
37
38 MARK(n) = 1;
39 agsubnode(out,n,1);
40 for (e = agfstedge(g, n); e; e = agnxtedge(g, e, n)) {
41 if ((other = agtail(e)) == n)
42 other = aghead(e);
43 if (!MARK(other))
44 dfs(g, other, out, marks);
45 }
46}
47
48/* findCComp:
49 * Finds generalized connected components of graph g.
50 * This merges all components containing a port node or a pinned node.
51 * Assumes nodes have unique id's in range [0,agnnodes(g)-1].
52 * Components are stored as subgraphs of g, with name sg_<i>.
53 * Returns 0-terminated array of components.
54 * If cnt is non-0, count of components is stored there.
55 * If pinned is non-0, *pinned is set to 1 if there are pinned nodes.
56 * Note that if ports and/or pinned nodes exists, they will all be
57 * in the first component returned by findCComp.
58 */
59static int C_cnt = 0;
60graph_t **findCComp(graph_t * g, int *cnt, int *pinned)
61{
62 node_t *n;
63 graph_t *subg;
64 char name[128];
65 int c_cnt = 0;
66 char *marks;
67 bport_t *pp;
68 graph_t **comps;
69 graph_t **cp;
70 int pinflag = 0;
71
72/* fprintf (stderr, "comps of %s starting at %d \n", g->name, c_cnt); */
73 marks = N_NEW(agnnodes(g), char); /* freed below */
74
75 /* Create component based on port nodes */
76 subg = 0;
77 if ((pp = PORTS(g))) {
78 sprintf(name, "cc%s_%d", agnameof(g), c_cnt++ + C_cnt);
79 subg = agsubg(g, name,1);
80 agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE);
81 GD_alg(subg) = (void *) NEW(gdata);
82 PORTS(subg) = pp;
83 NPORTS(subg) = NPORTS(g);
84 for (; pp->n; pp++) {
85 if (MARK(pp->n))
86 continue;
87 dfs(g, pp->n, subg, marks);
88 }
89 }
90
91 /* Create/extend component based on pinned nodes */
92 /* Note that ports cannot be pinned */
93 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
94 if (MARK(n))
95 continue;
96 if (ND_pinned(n) != P_PIN)
97 continue;
98 if (!subg) {
99 sprintf(name, "cc%s_%d", agnameof(g), c_cnt++ + C_cnt);
100 subg = agsubg(g, name,1);
101 agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE);
102 GD_alg(subg) = (void *) NEW(gdata);
103 }
104 pinflag = 1;
105 dfs(g, n, subg, marks);
106 }
107 if (subg)
108 nodeInduce(subg);
109
110 /* Pick up remaining components */
111 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
112 if (MARK(n))
113 continue;
114 sprintf(name, "cc%s+%d", agnameof(g), c_cnt++ + C_cnt);
115 subg = agsubg(g, name,1);
116 agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE); //node custom data
117 GD_alg(subg) = (void *) NEW(gdata);
118 dfs(g, n, subg, marks);
119 nodeInduce(subg);
120 }
121 free(marks);
122 C_cnt += c_cnt;
123
124 if (cnt)
125 *cnt = c_cnt;
126 if (pinned)
127 *pinned = pinflag;
128 /* freed in layout */
129 comps = cp = N_NEW(c_cnt + 1, graph_t *);
130 for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
131 *cp++ = subg;
132 c_cnt--;
133 }
134 assert(c_cnt == 0);
135 *cp = 0;
136
137 return comps;
138}
139