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
20static 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
26typedef struct blk_t {
27 Agnode_t **data;
28 Agnode_t **endp;
29 struct blk_t *prev;
30 struct blk_t *next;
31} blk_t;
32
33typedef struct {
34 blk_t *fstblk;
35 blk_t *curblk;
36 Agnode_t **curp;
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
44static 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
56static void freeBlk (blk_t* bp)
57{
58 free (bp->data);
59 free (bp);
60}
61
62static 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
73static 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
99static 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
112static 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
132static 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 */
146static void insertFn(Agnode_t * n, void *state)
147{
148 agsubnode((Agraph_t *) state,n,1);
149}
150
151/* markFn:
152 */
153static 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 */
164static char*
165setPrefix (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 */
196Agraph_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 }
258packerror:
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 */
288Agraph_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
343typedef struct {
344 Agrec_t h;
345 char cc_subg; /* true iff subgraph corresponds to a component */
346} ccgraphinfo_t;
347
348typedef struct {
349 Agrec_t h;
350 char mark;
351 union {
352 Agraph_t* g;
353 Agnode_t* n;
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
362Agnode_t*
363dnodeOf (Agnode_t* v)
364{
365 ccgnodeinfo_t* ip = (ccgnodeinfo_t*)aggetrec(v, NRECNAME, FALSE);
366 if (ip)
367 return ip->ptr.n;
368 fprintf (stderr, "nodeinfo undefined\n");
369 return 0;
370}
371void
372dnodeSet (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 */
396static 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 */
426static 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 */
467static 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 */
486static 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 */
500int node_induce(Agraph_t * g, Agraph_t* eg)
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
518typedef struct {
519 Agrec_t h;
520 Agraph_t* orig;
521} orig_t;
522
523#define ORIG_REC "orig"
524
525Agraph_t*
526mapClust(Agraph_t *cl)
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 */
541static 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 */
575static void
576subgInduce(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
593static void
594subGInduce(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 */
608Agraph_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 */
682int isConnected(Agraph_t * g)
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 */
718int nodeInduce(Agraph_t * g)
719{
720 return node_induce (g, g->root);
721}
722