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 /*
16 * Decompose finds the connected components of a graph.
17 * It searches the temporary edges and ignores non-root nodes.
18 * The roots of the search are the real nodes of the graph,
19 * but any virtual nodes discovered are also included in the
20 * component.
21 */
22
23 #include "dot.h"
24
25 static node_t *Last_node;
26 static char Cmark;
27
28 static void
begin_component(graph_t * g)29 begin_component(graph_t* g)
30 {
31 Last_node = GD_nlist(g) = NULL;
32 }
33
34 static void
add_to_component(graph_t * g,node_t * n)35 add_to_component(graph_t* g, node_t * n)
36 {
37 GD_n_nodes(g)++;
38 ND_mark(n) = Cmark;
39 if (Last_node) {
40 ND_prev(n) = Last_node;
41 ND_next(Last_node) = n;
42 } else {
43 ND_prev(n) = NULL;
44 GD_nlist(g) = n;
45 }
46 Last_node = n;
47 ND_next(n) = NULL;
48 }
49
50 static void
end_component(graph_t * g)51 end_component(graph_t* g)
52 {
53 int i;
54
55 i = GD_comp(g).size++;
56 GD_comp(g).list = ALLOC(GD_comp(g).size, GD_comp(g).list, node_t *);
57 GD_comp(g).list[i] = GD_nlist(g);
58 }
59
60 typedef struct blk_t {
61 Agnode_t **data;
62 Agnode_t **endp;
63 struct blk_t *prev;
64 struct blk_t *next;
65 } blk_t;
66
67 typedef struct {
68 blk_t *fstblk;
69 blk_t *curblk;
70 Agnode_t **curp;
71 } stk_t;
72
73 #define BIGBUF 1000000
74
initStk(stk_t * sp,blk_t * bp,node_t ** base,int size)75 static void initStk(stk_t* sp, blk_t* bp, node_t** base, int size)
76 {
77 bp->data = base;
78 bp->endp = bp->data + size;
79 bp->next = NULL;
80 bp->prev = NULL;
81 sp->curblk = sp->fstblk = bp;
82 sp->curp = sp->curblk->data;
83 }
84
freeStk(stk_t * sp)85 static void freeStk(stk_t* sp)
86 {
87 blk_t* bp = sp->fstblk->next;
88 blk_t* nbp;
89 while (bp) {
90 nbp = bp->next;
91 free (bp->data);
92 free (bp);
93 bp = nbp;
94 }
95 }
96
push(stk_t * sp,node_t * np)97 static void push(stk_t* sp, node_t * np)
98 {
99 if (sp->curp == sp->curblk->endp) {
100 if (sp->curblk->next == NULL) {
101 blk_t *bp = NEW(blk_t);
102 bp->prev = sp->curblk;
103 bp->next = NULL;
104 bp->data = N_NEW(BIGBUF, Agnode_t *);
105 bp->endp = bp->data + BIGBUF;
106 sp->curblk->next = bp;
107 }
108 sp->curblk = sp->curblk->next;
109 sp->curp = sp->curblk->data;
110 }
111 ND_mark(np) = Cmark+1;
112 *sp->curp++ = np;
113 }
114
pop(stk_t * sp)115 static node_t *pop(stk_t* sp)
116 {
117 if (sp->curp == sp->curblk->data) {
118 if (sp->curblk == sp->fstblk)
119 return 0;
120 sp->curblk = sp->curblk->prev;
121 sp->curp = sp->curblk->endp;
122 }
123 sp->curp--;
124 return *sp->curp;
125 }
126
127 /* search_component:
128 * iterative dfs for components.
129 * We process the edges in reverse order of the recursive version to maintain
130 * the processing order of the nodes.
131 * Since are using a stack, we need to indicate nodes on the stack. Nodes unprocessed
132 * in this call to decompose will have mark < Cmark; processed nodes will have mark=Cmark;
133 * so we use mark = Cmark+1 to indicate nodes on the stack.
134 */
135 static void
search_component(stk_t * stk,graph_t * g,node_t * n)136 search_component(stk_t* stk, graph_t * g, node_t * n)
137 {
138 int c, i;
139 elist vec[4];
140 node_t *other;
141 edge_t *e;
142 edge_t **ep;
143
144 push(stk, n);
145 while ((n = pop(stk))) {
146 if (ND_mark(n) == Cmark) continue;
147 add_to_component(g, n);
148 vec[0] = ND_out(n);
149 vec[1] = ND_in(n);
150 vec[2] = ND_flat_out(n);
151 vec[3] = ND_flat_in(n);
152
153 for (c = 3; c >= 0; c--) {
154 if (vec[c].list) {
155 for (i = vec[c].size-1, ep = vec[c].list+i; i >= 0; i--, ep--) {
156 e = *ep;
157 if ((other = aghead(e)) == n)
158 other = agtail(e);
159 if ((ND_mark(other) != Cmark) && (other == UF_find(other)))
160 push(stk, other);
161 }
162 }
163 }
164 }
165 }
166
167 #if 0
168 static void
169 osearch_component(graph_t * g, node_t * n)
170 {
171 int c, i;
172 elist vec[4];
173 node_t *other;
174 edge_t *e;
175
176 add_to_component(g, n);
177 vec[0] = ND_out(n);
178 vec[1] = ND_in(n);
179 vec[2] = ND_flat_out(n);
180 vec[3] = ND_flat_in(n);
181
182 for (c = 0; c <= 3; c++) {
183 if (vec[c].list)
184 for (i = 0; (e = vec[c].list[i]); i++) {
185 if ((other = aghead(e)) == n)
186 other = agtail(e);
187 if ((ND_mark(other) != Cmark) && (other == UF_find(other)))
188 osearch_component(g, other);
189 }
190 }
191 }
192 #endif
193
decompose(graph_t * g,int pass)194 void decompose(graph_t * g, int pass)
195 {
196 graph_t *subg;
197 node_t *n, *v;
198 stk_t stk;
199 blk_t blk;
200 Agnode_t *base[SMALLBUF];
201
202 initStk (&stk, &blk, base, SMALLBUF);
203 if (++Cmark == 0)
204 Cmark = 1;
205 GD_n_nodes(g) = GD_comp(g).size = 0;
206 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
207 v = n;
208 if ((pass > 0) && (subg = ND_clust(v)))
209 v = GD_rankleader(subg)[ND_rank(v)];
210 else if (v != UF_find(v))
211 continue;
212 if (ND_mark(v) != Cmark) {
213 begin_component(g);
214 search_component(&stk, g, v);
215 end_component(g);
216 }
217 }
218 freeStk (&stk);
219 }
220