Graphviz  2.41.20170921.2350
decomp.c
Go to the documentation of this file.
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
29 begin_component(graph_t* g)
30 {
31  Last_node = GD_nlist(g) = NULL;
32 }
33 
34 static void
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
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 {
63  struct blk_t *prev;
64  struct blk_t *next;
65 } blk_t;
66 
67 typedef struct {
71 } stk_t;
72 
73 #define BIGBUF 1000000
74 
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 
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 
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  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 
121 static 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  */
141 static void
142 search_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
174 static void
175 osearch_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 
200 void 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 }
blk_t * curblk
Definition: decomp.c:69
#define ND_rank(n)
Definition: types.h:529
Definition: cgraph.h:388
#define GD_nlist(g)
Definition: types.h:401
#define N_NEW(n, t)
Definition: memory.h:36
#define GD_rankleader(g)
Definition: types.h:405
struct blk_t blk_t
#define SMALLBUF
Definition: const.h:17
#define ALLOC(size, ptr, type)
Definition: memory.h:41
#define ND_flat_in(n)
Definition: types.h:498
struct blk_t * prev
Definition: decomp.c:63
void decompose(graph_t *g, int pass)
Definition: decomp.c:200
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:141
#define ND_mark(n)
Definition: types.h:514
#define ND_clust(n)
Definition: types.h:495
node_t * UF_find(node_t *n)
Definition: utils.c:146
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
Agnode_t ** endp
Definition: decomp.c:62
Definition: decomp.c:67
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
Definition: types.h:261
CGRAPH_API Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:533
blk_t * fstblk
Definition: decomp.c:68
struct blk_t * next
Definition: decomp.c:64
edge_t ** list
Definition: types.h:262
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
#define push(s, x)
Definition: closest.c:63
#define GD_n_nodes(g)
Definition: types.h:397
#define NULL
Definition: logic.h:39
#define ND_in(n)
Definition: types.h:507
#define ND_next(n)
Definition: types.h:517
#define GD_comp(g)
Definition: types.h:366
#define ND_out(n)
Definition: types.h:522
Agnode_t ** curp
Definition: decomp.c:70
#define BIGBUF
Definition: decomp.c:73
#define ND_flat_out(n)
Definition: types.h:499
Definition: decomp.c:60
#define pop(s, x)
Definition: closest.c:71
#define ND_prev(n)
Definition: types.h:527
Agnode_t ** data
Definition: decomp.c:61
#define NEW(t)
Definition: memory.h:35