Graphviz  2.39.20141221.0545
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(stk,n) ((stk)->markfn(n,-1))
23 #define MARK(stk,n) ((stk)->markfn(n,1))
24 #define UNMARK(stk,n) ((stk)->markfn(n,0))
25 
26 typedef struct blk_t {
29  struct blk_t *prev;
30  struct blk_t *next;
31 } blk_t;
32 
33 typedef struct {
37  void (*actionfn) (Agnode_t *, void *);
38  int (*markfn) (Agnode_t *, int);
39 } stk_t;
40 
41 #define INITBUF 1024
42 #define BIGBUF 1000000
43 
44 static void initStk(stk_t* sp, blk_t* bp, Agnode_t** base, void (*actionfn) (Agnode_t *, void *),
45  int (*markfn) (Agnode_t *, int))
46 {
47  bp->data = base;
48  bp->endp = bp->data + INITBUF;
49  bp->prev = bp->next = NULL;
50  sp->curblk = sp->fstblk = bp;
51  sp->curp = sp->curblk->data;
52  sp->actionfn = actionfn;
53  sp->markfn = markfn;
54 }
55 
56 static void freeBlk (blk_t* bp)
57 {
58  free (bp->data);
59  free (bp);
60 }
61 
62 static void freeStk (stk_t* sp)
63 {
64  blk_t* bp;
65  blk_t* nxtbp;
66 
67  for (bp = sp->fstblk->next; bp; bp = nxtbp) {
68  nxtbp = bp->next;
69  freeBlk (bp);
70  }
71 }
72 
73 static void push(stk_t* sp, Agnode_t * np)
74 {
75  if (sp->curp == sp->curblk->endp) {
76  if (sp->curblk->next == NULL) {
77  blk_t *bp = GNEW(blk_t);
78  if (bp == 0) {
79  agerr(AGERR, "gc: Out of memory\n");
80  longjmp(jbuf, 1);
81  }
82  bp->prev = sp->curblk;
83  bp->next = NULL;
84  bp->data = N_GNEW(BIGBUF, Agnode_t *);
85  if (bp->data == 0) {
86  agerr(AGERR, "gc: Out of memory\n");
87  longjmp(jbuf, 1);
88  }
89  bp->endp = bp->data + BIGBUF;
90  sp->curblk->next = bp;
91  }
92  sp->curblk = sp->curblk->next;
93  sp->curp = sp->curblk->data;
94  }
95  MARK(sp,np);
96  *sp->curp++ = np;
97 }
98 
99 static Agnode_t *pop(stk_t* sp)
100 {
101  if (sp->curp == sp->curblk->data) {
102  if (sp->curblk == sp->fstblk)
103  return 0;
104  sp->curblk = sp->curblk->prev;
105  sp->curp = sp->curblk->endp;
106  }
107  sp->curp--;
108  return *sp->curp;
109 }
110 
111 
112 static int dfs(Agraph_t * g, Agnode_t * n, void *state, stk_t* stk)
113 {
114  Agedge_t *e;
115  Agnode_t *other;
116  int cnt = 0;
117 
118  push (stk, n);
119  while ((n = pop(stk))) {
120  cnt++;
121  if (stk->actionfn) stk->actionfn(n, state);
122  for (e = agfstedge(g, n); e; e = agnxtedge(g, e, n)) {
123  if ((other = agtail(e)) == n)
124  other = aghead(e);
125  if (!MARKED(stk,other))
126  push(stk, other);
127  }
128  }
129  return cnt;
130 }
131 
132 static int isLegal(char *p)
133 {
134  unsigned char c;
135 
136  while ((c = *(unsigned char *) p++)) {
137  if ((c != '_') && !isalnum(c))
138  return 0;
139  }
140 
141  return 1;
142 }
143 
144 /* insertFn:
145  */
146 static void insertFn(Agnode_t * n, void *state)
147 {
148  agsubnode((Agraph_t *) state,n,1);
149 }
150 
151 /* markFn:
152  */
153 static int markFn (Agnode_t* n, int v)
154 {
155  int ret;
156  if (v < 0) return ND_mark(n);
157  ret = ND_mark(n);
158  ND_mark(n) = v;
159  return ret;
160 }
161 
162 /* setPrefix:
163  */
164 static char*
165 setPrefix (char* pfx, int* lenp, char* buf, int buflen)
166 {
167  int len;
168  char* name;
169 
170  if (!pfx || !isLegal(pfx)) {
171  pfx = "_cc_";
172  }
173  len = strlen(pfx);
174  if (len + 25 <= buflen)
175  name = buf;
176  else {
177  if (!(name = (char *) gmalloc(len + 25))) return NULL;
178  }
179  strcpy(name, pfx);
180  *lenp = len;
181  return name;
182 }
183 
184 /* pccomps:
185  * Return an array of subgraphs consisting of the connected
186  * components of graph g. The number of components is returned in ncc.
187  * All pinned nodes are in one component.
188  * If pfx is non-null and a legal graph name, we use it as the prefix
189  * for the name of the subgraphs created. If not, a simple default is used.
190  * If pinned is non-null, *pinned set to 1 if pinned nodes found
191  * and the first component is the one containing the pinned nodes.
192  * Note that the component subgraphs do not contain any edges. These must
193  * be obtained from the root graph.
194  * Return NULL on error or if graph is empty.
195  */
196 Agraph_t **pccomps(Agraph_t * g, int *ncc, char *pfx, boolean * pinned)
197 {
198  int c_cnt = 0;
199  char buffer[SMALLBUF];
200  char *name;
201  Agraph_t *out = 0;
202  Agnode_t *n;
203  Agraph_t **ccs;
204  int len;
205  int bnd = 10;
206  boolean pin = FALSE;
207  stk_t stk;
208  blk_t blk;
209  Agnode_t* base[INITBUF];
210  int error = 0;
211 
212  if (agnnodes(g) == 0) {
213  *ncc = 0;
214  return 0;
215  }
216  name = setPrefix (pfx, &len, buffer, SMALLBUF);
217 
218  ccs = N_GNEW(bnd, Agraph_t *);
219 
220  initStk (&stk, &blk, base, insertFn, markFn);
221  for (n = agfstnode(g); n; n = agnxtnode(g, n))
222  UNMARK(&stk,n);
223 
224  if (setjmp(jbuf)) {
225  error = 1;
226  goto packerror;
227  }
228  /* Component with pinned nodes */
229  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
230  if (MARKED(&stk,n) || !isPinned(n))
231  continue;
232  if (!out) {
233  sprintf(name + len, "%d", c_cnt);
234  out = agsubg(g, name,1);
235  agbindrec(out, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE); //node custom data
236  ccs[c_cnt] = out;
237  c_cnt++;
238  pin = TRUE;
239  }
240  dfs (g, n, out, &stk);
241  }
242 
243  /* Remaining nodes */
244  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
245  if (MARKED(&stk,n))
246  continue;
247  sprintf(name + len, "%d", c_cnt);
248  out = agsubg(g, name,1);
249  agbindrec(out, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE); //node custom data
250  dfs(g, n, 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  name = setPrefix (pfx, &len, buffer, SMALLBUF);
307 
308  ccs = N_GNEW(bnd, Agraph_t *);
309  initStk (&stk, &blk, base, insertFn, markFn);
310  for (n = agfstnode(g); n; n = agnxtnode(g, n))
311  UNMARK(&stk,n);
312 
313  if (setjmp(jbuf)) {
314  freeStk (&stk);
315  free (ccs);
316  if (name != buffer)
317  free(name);
318  *ncc = 0;
319  return NULL;
320  }
321  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
322  if (MARKED(&stk,n))
323  continue;
324  sprintf(name + len, "%d", c_cnt);
325  out = agsubg(g, name,1);
326  agbindrec(out, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE); //node custom data
327  dfs(g, n, out, &stk);
328  if (c_cnt == bnd) {
329  bnd *= 2;
330  ccs = RALLOC(bnd, ccs, Agraph_t *);
331  }
332  ccs[c_cnt] = out;
333  c_cnt++;
334  }
335  freeStk (&stk);
336  ccs = RALLOC(c_cnt, ccs, Agraph_t *);
337  if (name != buffer)
338  free(name);
339  *ncc = c_cnt;
340  return ccs;
341 }
342 
343 typedef struct {
345  char cc_subg; /* true iff subgraph corresponds to a component */
346 } ccgraphinfo_t;
347 
348 typedef struct {
350  char mark;
351  union {
354  void* v;
355  } ptr;
356 } ccgnodeinfo_t;
357 
358 #define GRECNAME "ccgraphinfo"
359 #define NRECNAME "ccgnodeinfo"
360 #define GD_cc_subg(g) (((ccgraphinfo_t*)aggetrec(g, GRECNAME, FALSE))->cc_subg)
361 #ifdef DEBUG
362 Agnode_t*
363 dnodeOf (Agnode_t* v)
364 {
366  if (ip)
367  return ip->ptr.n;
368  fprintf (stderr, "nodeinfo undefined\n");
369  return 0;
370 }
371 void
372 dnodeSet (Agnode_t* v, Agnode_t* n)
373 {
374  ((ccgnodeinfo_t*)aggetrec(v, NRECNAME, FALSE))->ptr.n = n;
375 }
376 #else
377 #define dnodeOf(v) (((ccgnodeinfo_t*)aggetrec(v, NRECNAME, FALSE))->ptr.n)
378 #define dnodeSet(v,w) (((ccgnodeinfo_t*)aggetrec(v, NRECNAME, FALSE))->ptr.n=w)
379 #endif
380 
381 #define ptrOf(np) (((ccgnodeinfo_t*)((np)->base.data))->ptr.v)
382 #define nodeOf(np) (((ccgnodeinfo_t*)((np)->base.data))->ptr.n)
383 #define clustOf(np) (((ccgnodeinfo_t*)((np)->base.data))->ptr.g)
384 #define clMark(n) (((ccgnodeinfo_t*)(n->base.data))->mark)
385 
386 /* isCluster:
387  * Return true if graph is a cluster
388  */
389 #define isCluster(g) (strncmp(agnameof(g), "cluster", 7) == 0)
390 
391 /* deriveClusters:
392  * Construct nodes in derived graph corresponding top-level clusters.
393  * Since a cluster might be wrapped in a subgraph, we need to traverse
394  * down into the tree of subgraphs
395  */
396 static void deriveClusters(Agraph_t* dg, Agraph_t * g)
397 {
398  Agraph_t *subg;
399  Agnode_t *dn;
400  Agnode_t *n;
401 
402  for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
403  if (isCluster(subg)) {
404  dn = agnode(dg, agnameof(subg), 1);
405  agbindrec (dn, NRECNAME, sizeof(ccgnodeinfo_t), TRUE);
406  clustOf(dn) = subg;
407  for (n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
408  if (dnodeOf(n)) {
409  fprintf (stderr, "Error: node \"%s\" belongs to two non-nested clusters \"%s\" and \"%s\"\n",
410  agnameof (n), agnameof(subg), agnameof(dnodeOf(n)));
411  }
412  dnodeSet(n,dn);
413  }
414  }
415  else {
416  deriveClusters (dg, subg);
417  }
418  }
419 }
420 
421 /* deriveGraph:
422  * Create derived graph dg of g where nodes correspond to top-level nodes
423  * or clusters, and there is an edge in dg if there is an edge in g
424  * between any nodes in the respective clusters.
425  */
426 static Agraph_t *deriveGraph(Agraph_t * g)
427 {
428  Agraph_t *dg;
429  Agnode_t *dn;
430  Agnode_t *n;
431 
432  dg = agopen("dg", Agstrictundirected, (Agdisc_t *) 0);
433 
434  deriveClusters (dg, g);
435 
436  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
437  if (dnodeOf(n))
438  continue;
439  dn = agnode(dg, agnameof(n), 1);
440  agbindrec (dn, NRECNAME, sizeof(ccgnodeinfo_t), TRUE);
441  nodeOf(dn) = n;
442  dnodeSet(n,dn);
443  }
444 
445  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
446  Agedge_t *e;
447  Agnode_t *hd;
448  Agnode_t *tl = dnodeOf(n);
449  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
450  hd = aghead(e);
451  hd = dnodeOf(hd);
452  if (hd == tl)
453  continue;
454  if (hd > tl)
455  agedge(dg, tl, hd, 0, 1);
456  else
457  agedge(dg, hd, tl, 0, 1);
458  }
459  }
460 
461  return dg;
462 }
463 
464 /* unionNodes:
465  * Add all nodes in cluster nodes of dg to g
466  */
467 static void unionNodes(Agraph_t * dg, Agraph_t * g)
468 {
469  Agnode_t *n;
470  Agnode_t *dn;
471  Agraph_t *clust;
472 
473  for (dn = agfstnode(dg); dn; dn = agnxtnode(dg, dn)) {
474  if (AGTYPE(ptrOf(dn)) == AGNODE) {
475  agsubnode(g, nodeOf(dn), 1);
476  } else {
477  clust = clustOf(dn);
478  for (n = agfstnode(clust); n; n = agnxtnode(clust, n))
479  agsubnode(g, n, 1);
480  }
481  }
482 }
483 
484 /* clMarkFn:
485  */
486 static int clMarkFn (Agnode_t* n, int v)
487 {
488  int ret;
489  if (v < 0) return clMark(n);
490  ret = clMark(n);
491  clMark(n) = v;
492  return ret;
493 }
494 
495 /* node_induce:
496  * Using the edge set of eg, add to g any edges
497  * with both endpoints in g.
498  * Returns the number of edges added.
499  */
501 {
502  Agnode_t *n;
503  Agedge_t *e;
504  int e_cnt = 0;
505 
506  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
507  for (e = agfstout(eg, n); e; e = agnxtout(eg, e)) {
508  if (agsubnode(g, aghead(e),0)) {
509  agsubedge(g,e,1);
510  e_cnt++;
511  }
512  }
513  }
514  return e_cnt;
515 }
516 
517 
518 typedef struct {
521 } orig_t;
522 
523 #define ORIG_REC "orig"
524 
525 Agraph_t*
527 {
528  orig_t* op = (orig_t*)aggetrec(cl, ORIG_REC, 0);
529  assert (op);
530  return op->orig;
531 }
532 
533 /* projectG:
534  * If any nodes of subg are in g, create a subgraph of g
535  * and fill it with all nodes of subg in g and their induced
536  * edges in subg. Copy the attributes of subg to g. Return the subgraph.
537  * If not, return null.
538  * If subg is a cluster, the new subgraph will contain a pointer to it
539  * in the record "orig".
540  */
541 static Agraph_t *projectG(Agraph_t * subg, Agraph_t * g, int inCluster)
542 {
543  Agraph_t *proj = 0;
544  Agnode_t *n;
545  Agnode_t *m;
546  orig_t *op;
547 
548  for (n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
549  if ((m = agfindnode(g, agnameof(n)))) {
550  if (proj == 0) {
551  proj = agsubg(g, agnameof(subg), 1);
552  }
553  agsubnode(proj, m, 1);
554  }
555  }
556  if (!proj && inCluster) {
557  proj = agsubg(g, agnameof(subg), 1);
558  }
559  if (proj) {
560  node_induce(proj, subg);
561  agcopyattr(subg, proj);
562  if (isCluster(proj)) {
563  op = agbindrec(proj,ORIG_REC, sizeof(orig_t), 0);
564  op->orig = subg;
565  }
566  }
567 
568  return proj;
569 }
570 
571 /* subgInduce:
572  * Project subgraphs of root graph on subgraph.
573  * If non-empty, add to subgraph.
574  */
575 static void
576 subgInduce(Agraph_t * root, Agraph_t * g, int inCluster)
577 {
578  Agraph_t *subg;
579  Agraph_t *proj;
580  int in_cluster;
581 
582 /* fprintf (stderr, "subgInduce %s inCluster %d\n", agnameof(root), inCluster); */
583  for (subg = agfstsubg(root); subg; subg = agnxtsubg(subg)) {
584  if (GD_cc_subg(subg))
585  continue;
586  if ((proj = projectG(subg, g, inCluster))) {
587  in_cluster = (inCluster || isCluster(subg));
588  subgInduce(subg, proj, in_cluster);
589  }
590  }
591 }
592 
593 static void
594 subGInduce(Agraph_t* g, Agraph_t * out)
595 {
596  subgInduce(g, out, 0);
597 }
598 
599 /* cccomps:
600  * Decompose g into "connected" components, where nodes are connected
601  * either by an edge or by being in the same cluster. The components
602  * are returned in an array of subgraphs. ncc indicates how many components
603  * there are. The subgraphs use the prefix pfx in their names, if non-NULL.
604  * Note that cluster subgraph of the main graph, corresponding to a component,
605  * is cloned within the subgraph. Each cloned cluster contains a record pointing
606  * to the real cluster.
607  */
608 Agraph_t **cccomps(Agraph_t * g, int *ncc, char *pfx)
609 {
610  Agraph_t *dg;
611  long n_cnt, c_cnt, e_cnt;
612  char *name;
613  Agraph_t *out;
614  Agraph_t *dout;
615  Agnode_t *dn;
616  char buffer[SMALLBUF];
617  Agraph_t **ccs;
618  stk_t stk;
619  blk_t blk;
620  Agnode_t* base[INITBUF];
621  int len, sz = sizeof(ccgraphinfo_t);
622 
623  if (agnnodes(g) == 0) {
624  *ncc = 0;
625  return 0;
626  }
627 
628  /* Bind ccgraphinfo to graph and all subgraphs */
629  aginit(g, AGRAPH, GRECNAME, -sz, FALSE);
630 
631  /* Bind ccgraphinfo to graph and all subgraphs */
632  aginit(g, AGNODE, NRECNAME, sizeof(ccgnodeinfo_t), FALSE);
633 
634  name = setPrefix (pfx, &len, buffer, SMALLBUF);
635 
636  dg = deriveGraph(g);
637 
638  ccs = N_GNEW(agnnodes(dg), Agraph_t *);
639  initStk (&stk, &blk, base, insertFn, clMarkFn);
640 
641  c_cnt = 0;
642  for (dn = agfstnode(dg); dn; dn = agnxtnode(dg, dn)) {
643  if (MARKED(&stk,dn))
644  continue;
645  sprintf(name + len, "%ld", c_cnt);
646  dout = agsubg(dg, name, 1);
647  out = agsubg(g, name, 1);
648  agbindrec(out, GRECNAME, sizeof(ccgraphinfo_t), FALSE);
649  GD_cc_subg(out) = 1;
650  n_cnt = dfs(dg, dn, dout, &stk);
651  unionNodes(dout, out);
652  e_cnt = nodeInduce(out);
653  subGInduce(g, out);
654  ccs[c_cnt] = out;
655  agdelete(dg, dout);
656  if (Verbose)
657  fprintf(stderr, "(%4ld) %7ld nodes %7ld edges\n",
658  c_cnt, n_cnt, e_cnt);
659  c_cnt++;
660  }
661 
662  if (Verbose)
663  fprintf(stderr, " %7d nodes %7d edges %7ld components %s\n",
664  agnnodes(g), agnedges(g), c_cnt, agnameof(g));
665 
666  agclose(dg);
667  agclean (g, AGRAPH, GRECNAME);
668  agclean (g, AGNODE, NRECNAME);
669  freeStk (&stk);
670  ccs = RALLOC(c_cnt, ccs, Agraph_t *);
671  if (name != buffer)
672  free(name);
673  *ncc = c_cnt;
674  return ccs;
675 }
676 
677 /* isConnected:
678  * Returns 1 if the graph is connected.
679  * Returns 0 if the graph is not connected.
680  * Returns -1 if the graph is error.
681  */
683 {
684  Agnode_t *n;
685  int ret = 1;
686  int cnt = 0;
687  stk_t stk;
688  blk_t blk;
689  Agnode_t* base[INITBUF];
690 
691  if (agnnodes(g) == 0)
692  return 1;
693 
694  initStk (&stk, &blk, base, NULL, markFn);
695  for (n = agfstnode(g); n; n = agnxtnode(g, n))
696  UNMARK(&stk,n);
697 
698  if (setjmp(jbuf)) {
699  freeStk (&stk);
700  return -1;
701  }
702 
703  n = agfstnode(g);
704  cnt = dfs(g, agfstnode(g), NULL, &stk);
705  if (cnt != agnnodes(g))
706  ret = 0;
707  freeStk (&stk);
708  return ret;
709 }
710 
711 /* nodeInduce:
712  * Given a subgraph, adds all edges in the root graph both of whose
713  * endpoints are in the subgraph.
714  * If g is a connected component, this will be all edges attached to
715  * any node in g.
716  * Returns the number of edges added.
717  */
719 {
720  return node_induce (g, g->root);
721 }
Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:494
Definition: cgraph.h:389
#define RALLOC(size, ptr, type)
Definition: memory.h:42
#define dnodeSet(v, w)
Definition: ccomps.c:378
Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:502
struct blk_t * prev
Definition: ccomps.c:29
Agrec_t h
Definition: ccomps.c:519
#define ptrOf(np)
Definition: ccomps.c:381
Agrec_t * aggetrec(void *obj, char *name, int move_to_front)
Definition: rec.c:34
int agdelete(Agraph_t *g, void *obj)
Definition: obj.c:16
#define MARKED(stk, n)
Definition: ccomps.c:22
#define isPinned(n)
Definition: macros.h:25
blk_t * curblk
Definition: ccomps.c:35
int nodeInduce(Agraph_t *g)
Definition: ccomps.c:718
#define MARK(stk, n)
Definition: ccomps.c:23
int agnedges(Agraph_t *g)
#define BIGBUF
Definition: ccomps.c:42
void(* actionfn)(Agnode_t *, void *)
Definition: ccomps.c:37
#define SMALLBUF
Definition: const.h:17
Agrec_t h
Definition: ccomps.c:344
Definition: ccomps.c:518
void * v
Definition: ccomps.c:354
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
#define assert(x)
Definition: cghdr.h:48
Agdesc_t Agstrictundirected
Definition: graph.c:279
int agclose(Agraph_t *g)
Definition: graph.c:93
void * gmalloc(size_t nbytes)
Definition: memory.c:44
int agnnodes(Agraph_t *g)
Agraph_t ** pccomps(Agraph_t *g, int *ncc, char *pfx, boolean *pinned)
Definition: ccomps.c:196
#define nodeOf(np)
Definition: ccomps.c:382
Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition: edge.c:86
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:142
Agraph_t ** cccomps(Agraph_t *g, int *ncc, char *pfx)
Definition: ccomps.c:608
Agnode_t ** data
Definition: ccomps.c:27
#define ND_mark(n)
Definition: types.h:475
#define dnodeOf(v)
Definition: ccomps.c:377
int node_induce(Agraph_t *g, Agraph_t *eg)
Definition: ccomps.c:500
Agnode_t * agsubnode(Agraph_t *g, Agnode_t *n, int createflag)
Definition: node.c:254
#define clMark(n)
Definition: ccomps.c:384
#define AGTYPE(obj)
Definition: cgraph.h:100
Agnode_t * agnode(Agraph_t *g, char *name, int createflag)
Definition: node.c:142
Definition: ccomps.c:33
Agnode_t ** endp
Definition: ccomps.c:28
blk_t * fstblk
Definition: ccomps.c:34
void agclean(Agraph_t *g, int kind, char *rec_name)
Definition: rec.c:231
void free()
int i
Definition: gvdevice.c:448
Agraph_t * agsubg(Agraph_t *g, char *name, int cflag)
Definition: subg.c:52
#define clustOf(np)
Definition: ccomps.c:383
#define GRECNAME
Definition: ccomps.c:358
#define isCluster(g)
Definition: ccomps.c:389
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
Agraph_t * agopen(char *name, Agdesc_t desc, Agdisc_t *disc)
Definition: graph.c:44
Agraph_t * g
Definition: ccomps.c:352
struct blk_t blk_t
Agnode_t * n
Definition: ccomps.c:353
Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
#define INITBUF
Definition: ccomps.c:41
#define NRECNAME
Definition: ccomps.c:359
Definition: cgraph.h:70
#define AGNODE
Definition: cgraph.h:88
char cc_subg
Definition: ccomps.c:345
#define ORIG_REC
Definition: ccomps.c:523
#define push(s, x)
Definition: closest.c:63
void aginit(Agraph_t *g, int kind, char *rec_name, int rec_size, int move_to_front)
Definition: rec.c:198
char mark
Definition: ccomps.c:350
#define agfindnode(g, n)
Definition: types.h:565
int agcopyattr(void *oldobj, void *newobj)
Definition: attr.c:535
#define NULL
Definition: logic.h:50
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
#define UNMARK(stk, n)
Definition: ccomps.c:24
#define GNEW(t)
Definition: memory.h:37
EXTERN unsigned char Verbose
Definition: globals.h:73
Agrec_t h
Definition: ccomps.c:349
#define GD_cc_subg(g)
Definition: ccomps.c:360
char * agnameof(void *)
Definition: id.c:143
Agraph_t * agfstsubg(Agraph_t *g)
Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Definition: edge.c:95
Agraph_t * orig
Definition: ccomps.c:520
union ccgnodeinfo_t::@26 ptr
int(* markfn)(Agnode_t *, int)
Definition: ccomps.c:38
struct blk_t * next
Definition: ccomps.c:30
Agraph_t ** ccomps(Agraph_t *g, int *ncc, char *pfx)
Definition: ccomps.c:288
Agraph_t * root
Definition: cgraph.h:241
Definition: ccomps.c:26
int isConnected(Agraph_t *g)
Definition: ccomps.c:682
Agedge_t * agsubedge(Agraph_t *g, Agedge_t *e, int createflag)
Definition: edge.c:378
void * agbindrec(void *obj, char *name, unsigned int size, int move_to_front)
Definition: rec.c:86
#define pop(s, x)
Definition: closest.c:71
Agedge_t * agedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, char *name, int createflag)
Definition: edge.c:281
Agnode_t ** curp
Definition: ccomps.c:36
#define N_GNEW(n, t)
Definition: agxbuf.c:20
#define FALSE
Definition: cgraph.h:24
Agraph_t * mapClust(Agraph_t *cl)
Definition: ccomps.c:526
Agraph_t * agnxtsubg(Agraph_t *subg)
Definition: subg.c:77
#define AGRAPH
Definition: cgraph.h:87
#define TRUE
Definition: cgraph.h:27