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
25static node_t *Last_node;
26static char Cmark;
27
28static void
29begin_component(graph_t* g)
30{
31 Last_node = GD_nlist(g) = NULL;
32}
33
34static void
35add_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
50static void
51end_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
60typedef 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
67typedef struct {
68 blk_t *fstblk;
69 blk_t *curblk;
70 Agnode_t **curp;
71} stk_t;
72
73#define BIGBUF 1000000
74
75static 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
85static 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
97static 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 if (bp == 0) {
103 agerr(AGERR, "gc: Out of memory\n");
104 }
105 bp->prev = sp->curblk;
106 bp->next = NULL;
107 bp->data = N_NEW(BIGBUF, Agnode_t *);
108 if (bp->data == 0) {
109 agerr(AGERR, "dot: Out of memory\n");
110 }
111 bp->endp = bp->data + BIGBUF;
112 sp->curblk->next = bp;
113 }
114 sp->curblk = sp->curblk->next;
115 sp->curp = sp->curblk->data;
116 }
117 ND_mark(np) = Cmark+1;
118 *sp->curp++ = np;
119}
120
121static node_t *pop(stk_t* sp)
122{
123 if (sp->curp == sp->curblk->data) {
124 if (sp->curblk == sp->fstblk)
125 return 0;
126 sp->curblk = sp->curblk->prev;
127 sp->curp = sp->curblk->endp;
128 }
129 sp->curp--;
130 return *sp->curp;
131}
132
133/* search_component:
134 * iterative dfs for components.
135 * We process the edges in reverse order of the recursive version to maintain
136 * the processing order of the nodes.
137 * Since are using a stack, we need to indicate nodes on the stack. Nodes unprocessed
138 * in this call to decompose will have mark < Cmark; processed nodes will have mark=Cmark;
139 * so we use mark = Cmark+1 to indicate nodes on the stack.
140 */
141static void
142search_component(stk_t* stk, graph_t * g, node_t * n)
143{
144 int c, i;
145 elist vec[4];
146 node_t *other;
147 edge_t *e;
148 edge_t **ep;
149
150 push(stk, n);
151 while ((n = pop(stk))) {
152 if (ND_mark(n) == Cmark) continue;
153 add_to_component(g, n);
154 vec[0] = ND_out(n);
155 vec[1] = ND_in(n);
156 vec[2] = ND_flat_out(n);
157 vec[3] = ND_flat_in(n);
158
159 for (c = 3; c >= 0; c--) {
160 if (vec[c].list) {
161 for (i = vec[c].size-1, ep = vec[c].list+i; i >= 0; i--, ep--) {
162 e = *ep;
163 if ((other = aghead(e)) == n)
164 other = agtail(e);
165 if ((ND_mark(other) != Cmark) && (other == UF_find(other)))
166 push(stk, other);
167 }
168 }
169 }
170 }
171}
172
173#if 0
174static void
175osearch_component(graph_t * g, node_t * n)
176{
177 int c, i;
178 elist vec[4];
179 node_t *other;
180 edge_t *e;
181
182 add_to_component(g, n);
183 vec[0] = ND_out(n);
184 vec[1] = ND_in(n);
185 vec[2] = ND_flat_out(n);
186 vec[3] = ND_flat_in(n);
187
188 for (c = 0; c <= 3; c++) {
189 if (vec[c].list)
190 for (i = 0; (e = vec[c].list[i]); i++) {
191 if ((other = aghead(e)) == n)
192 other = agtail(e);
193 if ((ND_mark(other) != Cmark) && (other == UF_find(other)))
194 osearch_component(g, other);
195 }
196 }
197}
198#endif
199
200void decompose(graph_t * g, int pass)
201{
202 graph_t *subg;
203 node_t *n, *v;
204 stk_t stk;
205 blk_t blk;
206 Agnode_t *base[SMALLBUF];
207
208 initStk (&stk, &blk, base, SMALLBUF);
209 if (++Cmark == 0)
210 Cmark = 1;
211 GD_n_nodes(g) = GD_comp(g).size = 0;
212 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
213 v = n;
214 if ((pass > 0) && (subg = ND_clust(v)))
215 v = GD_rankleader(subg)[ND_rank(v)];
216 else if (v != UF_find(v))
217 continue;
218 if (ND_mark(v) != Cmark) {
219 begin_component(g);
220 search_component(&stk, g, v);
221 end_component(g);
222 }
223 }
224 freeStk (&stk);
225}
226