Graphviz  2.35.20130930.0449
ccomps.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 #include <ctype.h>
16 #include <setjmp.h>
17 #include "render.h"
18 #include "pack.h"
19 
20 static jmp_buf jbuf;
21 
22 #define MARKED(n) ND_mark(n)
23 #define MARK(n) (ND_mark(n) = 1)
24 #define ONSTACK(n) (ND_mark(n) = 1)
25 #define UNMARK(n) (ND_mark(n) = 0)
26 
27 typedef void (*dfsfn) (Agnode_t *, void *);
28 
29 #if 0
30 static void dfs(Agraph_t * g, Agnode_t * n, dfsfn action, void *state)
31 {
32  Agedge_t *e;
33  Agnode_t *other;
34 
35  MARK(n);
36  action(n, state);
37  for (e = agfstedge(g, n); e; e = agnxtedge(g, e, n)) {
38  if ((other = agtail(e)) == n)
39  other = aghead(e);
40  if (!MARKED(other))
41  dfs(g, other, action, state);
42  }
43 }
44 #endif
45 
46 typedef struct blk_t {
49  struct blk_t *prev;
50  struct blk_t *next;
51 } blk_t;
52 
53 typedef struct {
57 } stk_t;
58 
59 #define INITBUF 1024
60 #define BIGBUF 1000000
61 
62 static void initStk(stk_t* sp, blk_t* bp, Agnode_t** base)
63 {
64  bp->data = base;
65  bp->endp = bp->data + INITBUF;
66  bp->prev = bp->next = NULL;
67  sp->curblk = sp->fstblk = bp;
68  sp->curp = sp->curblk->data;
69 }
70 
71 static void freeBlk (blk_t* bp)
72 {
73  free (bp->data);
74  free (bp);
75 }
76 
77 static void freeStk (stk_t* sp)
78 {
79  blk_t* bp;
80  blk_t* nxtbp;
81 
82  for (bp = sp->fstblk->next; bp; bp = nxtbp) {
83  nxtbp = bp->next;
84  freeBlk (bp);
85  }
86 }
87 
88 static void push(stk_t* sp, Agnode_t * np)
89 {
90  if (sp->curp == sp->curblk->endp) {
91  if (sp->curblk->next == NULL) {
92  blk_t *bp = GNEW(blk_t);
93  if (bp == 0) {
94  agerr(AGERR, "gc: Out of memory\n");
95  longjmp(jbuf, 1);
96  }
97  bp->prev = sp->curblk;
98  bp->next = NULL;
99  bp->data = N_GNEW(BIGBUF, Agnode_t *);
100  if (bp->data == 0) {
101  agerr(AGERR, "gc: Out of memory\n");
102  longjmp(jbuf, 1);
103  }
104  bp->endp = bp->data + BIGBUF;
105  sp->curblk->next = bp;
106  }
107  sp->curblk = sp->curblk->next;
108  sp->curp = sp->curblk->data;
109  }
110  ONSTACK(np);
111  *sp->curp++ = np;
112 }
113 
114 static Agnode_t *pop(stk_t* sp)
115 {
116  if (sp->curp == sp->curblk->data) {
117  if (sp->curblk == sp->fstblk)
118  return 0;
119  sp->curblk = sp->curblk->prev;
120  sp->curp = sp->curblk->endp;
121  }
122  sp->curp--;
123  return *sp->curp;
124 }
125 
126 
127 static void dfs(Agraph_t * g, Agnode_t * n, dfsfn action, void *state, stk_t* stk)
128 {
129  Agedge_t *e;
130  Agnode_t *other;
131 
132  push (stk, n);
133  while ((n = pop(stk))) {
134  MARK(n);
135  action(n, state);
136  for (e = agfstedge(g, n); e; e = agnxtedge(g, e, n)) {
137  if ((other = agtail(e)) == n)
138  other = aghead(e);
139  if (!MARKED(other))
140  push(stk, other);
141  }
142  }
143 }
144 
145 static int isLegal(char *p)
146 {
147  unsigned char c;
148 
149  while ((c = *(unsigned char *) p++)) {
150  if ((c != '_') && !isalnum(c))
151  return 0;
152  }
153 
154  return 1;
155 }
156 
157 /* insertFn:
158  */
159 static void insertFn(Agnode_t * n, void *state)
160 {
161 #ifndef WITH_CGRAPH
162  aginsert((Agraph_t *) state, n);
163 #else /* WITH_CGRAPH */
164  agsubnode((Agraph_t *) state,n,1);
165 #endif /* WITH_CGRAPH */
166 }
167 
168 /* pccomps:
169  * Return an array of subgraphs consisting of the connected
170  * components of graph g. The number of components is returned in ncc.
171  * All pinned nodes are in one component.
172  * If pfx is non-null and a legal graph name, we use it as the prefix
173  * for the name of the subgraphs created. If not, a simple default is used.
174  * If pinned is non-null, *pinned set to 1 if pinned nodes found
175  * and the first component is the one containing the pinned nodes.
176  * Note that the component subgraphs do not contain any edges. These must
177  * be obtained from the root graph.
178  * Return NULL on error or if graph is empty.
179  */
180 Agraph_t **pccomps(Agraph_t * g, int *ncc, char *pfx, boolean * pinned)
181 {
182  int c_cnt = 0;
183  char buffer[SMALLBUF];
184  char *name;
185  Agraph_t *out = 0;
186  Agnode_t *n;
187  Agraph_t **ccs;
188  int len;
189  int bnd = 10;
190  boolean pin = FALSE;
191  stk_t stk;
192  blk_t blk;
193  Agnode_t* base[INITBUF];
194  int error = 0;
195 
196  if (agnnodes(g) == 0) {
197  *ncc = 0;
198  return 0;
199  }
200  if (!pfx || !isLegal(pfx)) {
201  pfx = "_cc_";
202  }
203  len = strlen(pfx);
204  if (len + 25 <= SMALLBUF)
205  name = buffer;
206  else
207  name = (char *) gmalloc(len + 25);
208  strcpy(name, pfx);
209 
210  for (n = agfstnode(g); n; n = agnxtnode(g, n))
211  UNMARK(n);
212 
213  ccs = N_GNEW(bnd, Agraph_t *);
214 
215  initStk (&stk, &blk, base);
216  if (setjmp(jbuf)) {
217  error = 1;
218  goto packerror;
219  }
220  /* Component with pinned nodes */
221  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
222  if (MARKED(n) || !isPinned(n))
223  continue;
224  if (!out) {
225  sprintf(name + len, "%d", c_cnt);
226 #ifndef WITH_CGRAPH
227  out = agsubg(g, name);
228 #else /* WITH_CGRAPH */
229  out = agsubg(g, name,1);
230  agbindrec(out, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE); //node custom data
231 #endif /* WITH_CGRAPH */
232  ccs[c_cnt] = out;
233  c_cnt++;
234  pin = TRUE;
235  }
236  dfs (g, n, insertFn, out, &stk);
237  }
238 
239  /* Remaining nodes */
240  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
241  if (MARKED(n))
242  continue;
243  sprintf(name + len, "%d", c_cnt);
244 #ifndef WITH_CGRAPH
245  out = agsubg(g, name);
246 #else /* WITH_CGRAPH */
247  out = agsubg(g, name,1);
248  agbindrec(out, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE); //node custom data
249 #endif /* WITH_CGRAPH */
250  dfs(g, n, insertFn, out, &stk);
251  if (c_cnt == bnd) {
252  bnd *= 2;
253  ccs = RALLOC(bnd, ccs, Agraph_t *);
254  }
255  ccs[c_cnt] = out;
256  c_cnt++;
257  }
258 packerror:
259  freeStk (&stk);
260  if (name != buffer)
261  free(name);
262  if (error) {
263  int i;
264  *ncc = 0;
265  for (i=0; i < c_cnt; i++) {
266  agclose (ccs[i]);
267  }
268  free (ccs);
269  ccs = NULL;
270  }
271  else {
272  ccs = RALLOC(c_cnt, ccs, Agraph_t *);
273  *ncc = c_cnt;
274  *pinned = pin;
275  }
276  return ccs;
277 }
278 
279 /* ccomps:
280  * Return an array of subgraphs consisting of the connected
281  * components of graph g. The number of components is returned in ncc.
282  * If pfx is non-null and a legal graph name, we use it as the prefix
283  * for the name of the subgraphs created. If not, a simple default is used.
284  * Note that the component subgraphs do not contain any edges. These must
285  * be obtained from the root graph.
286  * Returns NULL on error or if graph is empty.
287  */
288 Agraph_t **ccomps(Agraph_t * g, int *ncc, char *pfx)
289 {
290  int c_cnt = 0;
291  char buffer[SMALLBUF];
292  char *name;
293  Agraph_t *out;
294  Agnode_t *n;
295  Agraph_t **ccs;
296  int len;
297  int bnd = 10;
298  stk_t stk;
299  blk_t blk;
300  Agnode_t* base[INITBUF];
301 
302  if (agnnodes(g) == 0) {
303  *ncc = 0;
304  return 0;
305  }
306  if (!pfx || !isLegal(pfx)) {
307  pfx = "_cc_";
308  }
309  len = strlen(pfx);
310  if (len + 25 <= SMALLBUF)
311  name = buffer;
312  else {
313  if (!(name = (char *) gmalloc(len + 25))) return NULL;
314  }
315  strcpy(name, pfx);
316 
317  for (n = agfstnode(g); n; n = agnxtnode(g, n))
318  UNMARK(n);
319 
320  ccs = N_GNEW(bnd, Agraph_t *);
321  initStk (&stk, &blk, base);
322  if (setjmp(jbuf)) {
323  freeStk (&stk);
324  free (ccs);
325  if (name != buffer)
326  free(name);
327  *ncc = 0;
328  return NULL;
329  }
330  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
331  if (MARKED(n))
332  continue;
333  sprintf(name + len, "%d", c_cnt);
334 #ifndef WITH_CGRAPH
335  out = agsubg(g, name);
336 #else /* WITH_CGRAPH */
337  out = agsubg(g, name,1);
338  agbindrec(out, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE); //node custom data
339 #endif /* WITH_CGRAPH */
340  dfs(g, n, insertFn, out, &stk);
341  if (c_cnt == bnd) {
342  bnd *= 2;
343  ccs = RALLOC(bnd, ccs, Agraph_t *);
344  }
345  ccs[c_cnt] = out;
346  c_cnt++;
347  }
348  freeStk (&stk);
349  ccs = RALLOC(c_cnt, ccs, Agraph_t *);
350  if (name != buffer)
351  free(name);
352  *ncc = c_cnt;
353  return ccs;
354 }
355 
356 /* cntFn:
357  */
358 static void cntFn(Agnode_t * n, void *s)
359 {
360  *(int *) s += 1;
361 }
362 
363 /* isConnected:
364  * Returns 1 if the graph is connected.
365  * Returns 0 if the graph is not connected.
366  * Returns -1 if the graph is error.
367  */
369 {
370  Agnode_t *n;
371  int ret = 1;
372  int cnt = 0;
373  stk_t stk;
374  blk_t blk;
375  Agnode_t* base[INITBUF];
376 
377  for (n = agfstnode(g); n; n = agnxtnode(g, n))
378  UNMARK(n);
379 
380  n = agfstnode(g);
381  if (n) {
382  initStk (&stk, &blk, base);
383  if (setjmp(jbuf)) {
384  freeStk (&stk);
385  return -1;
386  }
387  dfs(g, n, cntFn, &cnt, &stk);
388  if (cnt != agnnodes(g))
389  ret = 0;
390  freeStk (&stk);
391  }
392  return ret;
393 }
394 
395 /* nodeInduce:
396  * Given a subgraph, adds all edges in the root graph both of whose
397  * endpoints are in the subgraph.
398  * If g is a connected component, this will be all edges attached to
399  * any node in g.
400  * Returns the number of edges added.
401  */
403 {
404  Agnode_t *n;
405  Agraph_t *root = g->root;
406  Agedge_t *e;
407  int e_cnt = 0;
408 
409  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
410  for (e = agfstout(root, n); e; e = agnxtout(root, e)) {
411  if (agcontains(g, aghead(e))) { /* test will always be true */
412 #ifndef WITH_CGRAPH
413  aginsert(g, e); /* for connected component */
414 #else /* WITH_CGRAPH */
415  agsubedge(g,e,1);
416 #endif /* WITH_CGRAPH */
417  e_cnt++;
418  }
419  }
420  }
421  return e_cnt;
422 }