← Back to branch summary

~ubuntu-branches/ubuntu/lucid/graphviz/lucid-updates

« back to all changes in this revision

Viewing changes to cmd/tools/ccomps.c

  • Committer: Bazaar Package Importer
  • Author(s): Bryce Harrington
  • Date: 2008-06-19 20:23:23 UTC
  • mfrom: (1.2.5 upstream)
  • Revision ID: james.westby@ubuntu.com-20080619202323-ls23h96ntj9ny94m
Tags: 2.18-1ubuntu1
https://launchpad.net/bugs/174749
* Merge from debian unstable, remaining changes:
  - Build depend on liblualib50-dev instead of liblua5.1-0-dev.
  - Drop libttf-dev (libttf-dev is in universe) (LP: #174749).
  - Replace gs-common with ghostscript.
  - Build-depend on python-dev instead of python2.4-dev or python2.5-dev.
  - Mention the correct python version for the python bindings in the
    package description.

Show diffs side-by-side

added added

removed removed

Lines of Context:
cmd/tools/ccomps.c
1
 
/* $Id: ccomps.c,v 1.5 2007/08/08 23:00:58 erg Exp $ $Revision: 1.5 $ */
 
1
/* $Id: ccomps.c,v 1.6 2008/01/09 20:50:35 erg Exp $ $Revision: 1.6 $ */
2
2
/* vim:set shiftwidth=4 ts=8: */
3
3
 
4
4
/**********************************************************
26
26
 
27
27
#include <ctype.h>
28
28
 
 
29
#ifdef USE_CGRAPH
 
30
#include <stdlib.h>
 
31
#include <cgraph.h>
 
32
 
 
33
typedef struct {
 
34
    Agrec_t h;
 
35
    char cc_subg;
 
36
} Agraphinfo_t;
 
37
 
 
38
typedef struct {
 
39
    Agrec_t h;
 
40
    char mark;
 
41
    Agobj_t* ptr;
 
42
} Agnodeinfo_t;
 
43
 
 
44
#define GD_cc_subg(g)  (((Agraphinfo_t*)(g->base.data))->cc_subg)
 
45
#define ND_mark(n)  (((Agnodeinfo_t*)(n->base.data))->mark)
 
46
#define ND_ptr(n)  (((Agnodeinfo_t*)(n->base.data))->ptr)
 
47
#define ND_dn(n)  ((Agnode_t*)ND_ptr(n))
 
48
#define ND_clust(n)  ((Agraph_t*)ND_ptr(n))
 
49
#define agfindnode(G,N) (agnode(G, N, 0))
 
50
#else
29
51
typedef struct {
30
52
    char cc_subg;
31
53
} Agraphinfo_t;
41
63
#define GD_cc_subg(g) (g)->u.cc_subg
42
64
#define ND_mark(n) (n)->u.mark
43
65
#define ND_ptr(n) (n)->u.ptr
 
66
#include <graph.h>
 
67
#define agnameof(x) (agobjkind(x) == AGNODE ? ((Agnode_t*)(x))->name : ((Agraph_t*)(x))->name)
 
68
#define agtail(e) ((e)->tail)
 
69
#define aghead(e) ((e)->head)
 
70
#endif
44
71
 
45
72
#ifdef HAVE_GETOPT_H
46
73
#include <getopt.h>
48
75
#include "compat_getopt.h"
49
76
#endif
50
77
 
51
 
#include <graph.h>
52
78
#ifdef HAVE_UNISTD_H
53
79
#include        <unistd.h>
54
80
#endif
57
83
 
58
84
  /* internals of libgraph */
59
85
#define TAG_NODE            1
60
 
extern Agdict_t *agdictof(void *);
61
86
 
62
87
#define INTERNAL 0
63
88
#define EXTERNAL 1
116
141
 */
117
142
static int isCluster(Agraph_t * g)
118
143
{
119
 
    return (strncmp(g->name, "cluster", 7) == 0);
 
144
    return (strncmp(agnameof(g), "cluster", 7) == 0);
120
145
}
121
146
 
122
147
static void init(int argc, char *argv[])
123
148
{
124
149
    int c;
125
150
 
 
151
#ifndef USE_CGRAPH
126
152
    aginit();
 
153
#endif
127
154
    while ((c = getopt(argc, argv, ":o:xCX:nsv?")) != -1) {
128
155
        switch (c) {
129
156
        case 'o':
183
210
 
184
211
    ND_mark(n) = 1;
185
212
    cnt++;
 
213
#ifdef USE_CGRAPH
 
214
    agsubnode(out, n, 1);
 
215
#else
186
216
    aginsert(out, n);
 
217
#endif
187
218
    for (e = agfstedge(g, n); e; e = agnxtedge(g, e, n)) {
188
 
        if ((other = e->tail) == n)
189
 
            other = e->head;
 
219
        if ((other = agtail(e)) == n)
 
220
            other = aghead(e);
190
221
        if (ND_mark(other) == 0)
191
222
            cnt = dfs(g, other, out, cnt);
192
223
    }
193
224
    return cnt;
194
225
}
195
226
 
 
227
/* nodeInduce:
 
228
 * Using the edge set of eg, add to g any edges
 
229
 * with both endpoints in g.
 
230
 */
196
231
static int nodeInduce(Agraph_t * g, Agraph_t * eg)
197
232
{
198
233
    Agnode_t *n;
201
236
 
202
237
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
203
238
        for (e = agfstout(eg, n); e; e = agnxtout(eg, e)) {
204
 
            if (agcontains(g, e->head)) {
 
239
#ifdef USE_CGRAPH
 
240
            if (agsubnode(g, aghead(e), 0)) {
 
241
                agsubedge(g, e, 1);
 
242
#else
 
243
            if (agcontains(g, aghead(e))) {
205
244
                aginsert(g, e);
 
245
#endif
206
246
                e_cnt++;
207
247
            }
208
248
        }
251
291
    }
252
292
}
253
293
 
254
 
/* copyAttr:
255
 
 * Copy the attributes of g2 to g1.
256
 
 */
257
 
static void copyAttr(Agraph_t * g1, Agraph_t * g2)
258
 
{
259
 
    Agdict_t *dict;
260
 
    Agsym_t *a;
261
 
    int i, n;
262
 
 
263
 
    dict = agdictof(g2);
264
 
    n = dtsize(dict->dict);
265
 
    for (i = 0; i < n; i++) {
266
 
        a = dict->list[i];
267
 
        agxset(g1, a->index, agxget(g2, a->index));
268
 
    }
269
 
}
270
 
 
271
294
/* getBuf
272
295
 * Return pointer to buffer containing at least n bytes.
273
296
 * Non-reentrant.
304
327
    char *name;
305
328
 
306
329
    for (n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
307
 
        if ((m = agfindnode(g, n->name))) {
 
330
        if ((m = agfindnode(g, agnameof(n)))) {
308
331
            if (proj == 0) {
309
 
                name = getBuf(strlen(subg->name) + pfxlen + 2);
310
 
                sprintf(name, "%s_%s", subg->name, pfx);
 
332
                name = getBuf(strlen(agnameof(subg)) + pfxlen + 2);
 
333
                sprintf(name, "%s_%s", agnameof(subg), pfx);
 
334
#ifdef USE_CGRAPH
 
335
                proj = agsubg(g, name, 1);
 
336
#else
311
337
                proj = agsubg(g, name);
 
338
#endif
312
339
            }
 
340
#ifdef USE_CGRAPH
 
341
            agsubnode(proj, m, 1);
 
342
#else
313
343
            aginsert(proj, m);
 
344
#endif
314
345
        }
315
346
    }
316
347
    if (!proj && inCluster) {
317
 
        name = getBuf(strlen(subg->name) + pfxlen + 2);
318
 
        sprintf(name, "%s_%s", subg->name, pfx);
 
348
        name = getBuf(strlen(agnameof(subg)) + pfxlen + 2);
 
349
        sprintf(name, "%s_%s", agnameof(subg), pfx);
 
350
#ifdef USE_CGRAPH
 
351
        proj = agsubg(g, name, 1);
 
352
#else
319
353
        proj = agsubg(g, name);
 
354
#endif
320
355
    }
321
356
    if (proj) {
322
357
        nodeInduce(proj, subg);
323
 
        copyAttr(proj, subg);
 
358
        agcopyattr(subg, proj);
324
359
    }
325
360
 
326
361
    return proj;
330
365
 * Project subgraphs of root graph on subgraph.
331
366
 * If non-empty, add to subgraph.
332
367
 */
 
368
#ifdef USE_CGRAPH
 
369
static void
 
370
subgInduce(Agraph_t * root, Agraph_t * g, char *pfx, int pfxlen,
 
371
           int inCluster)
 
372
{
 
373
    Agraph_t *subg;
 
374
    Agraph_t *proj;
 
375
    int in_cluster;
 
376
 
 
377
/* fprintf (stderr, "subgInduce %s inCluster %d\n", agnameof(root), inCluster); */
 
378
    for (subg = agfstsubg(root); subg; subg = agnxtsubg(subg)) {
 
379
        if (GD_cc_subg(subg))
 
380
            continue;
 
381
        if ((proj = projectG(subg, g, pfx, pfxlen, inCluster))) {
 
382
            in_cluster = inCluster || (useClusters && isCluster(subg));
 
383
            subgInduce(subg, proj, pfx, pfxlen, in_cluster);
 
384
        }
 
385
    }
 
386
}
 
387
 
 
388
static void
 
389
subGInduce(Agraph_t* g, Agraph_t * out)
 
390
{
 
391
    subgInduce(g, out, agnameof(out), strlen(agnameof(out)), 0);
 
392
}
 
393
#else
333
394
static void
334
395
subgInduce(Agraph_t * root, Agraph_t * g, char *pfx, int pfxlen,
335
396
           int inCluster)
355
416
    }
356
417
}
357
418
 
 
419
#endif
 
420
 
358
421
#define PFX1 "%s_cc"
359
422
#define PFX2 "%s_cc_%ld"
360
423
 
363
426
 * top-level nodes and there is an edge in dg if there is an edge in g
364
427
 * between any nodes in the respective clusters.
365
428
 */
 
429
#ifdef USE_CGRAPH
 
430
static Agraph_t *deriveGraph(Agraph_t * g)
 
431
{
 
432
    Agraph_t *dg;
 
433
    Agnode_t *dn;
 
434
    Agnode_t *n;
 
435
    Agraph_t *subg;
 
436
 
 
437
    dg = agopen("dg", Agstrictundirected, (Agdisc_t *) 0);
 
438
 
 
439
    for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
 
440
        if (!strncmp(agnameof(subg), "cluster", 7)) {
 
441
            dn = agnode(dg, agnameof(subg), 1);
 
442
            ND_ptr(dn) = (Agobj_t*)subg;
 
443
            for (n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
 
444
                ND_ptr(n) = (Agobj_t*)dn;
 
445
            }
 
446
        }
 
447
    }
 
448
 
 
449
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
 
450
        if (ND_dn(n))
 
451
            continue;
 
452
        dn = agnode(dg, agnameof(n), 1);
 
453
        ND_ptr(dn) = (Agobj_t*)n;
 
454
        ND_ptr(n) = (Agobj_t*)dn;
 
455
    }
 
456
 
 
457
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
 
458
        Agedge_t *e;
 
459
        Agnode_t *hd;
 
460
        Agnode_t *tl = ND_dn(n);
 
461
        for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
 
462
            hd = ND_dn(aghead(e));
 
463
            if (hd == tl)
 
464
                continue;
 
465
            if (hd > tl)
 
466
                agedge(dg, tl, hd, 0, 1);
 
467
            else
 
468
                agedge(dg, hd, tl, 0, 1);
 
469
        }
 
470
    }
 
471
 
 
472
    return dg;
 
473
}
 
474
#else
366
475
static Agraph_t *deriveGraph(Agraph_t * g)
367
476
{
368
477
    Agraph_t *mg;
391
500
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
392
501
        if (ND_ptr(n).dn)
393
502
            continue;
394
 
        dn = agnode(dg, n->name);
 
503
        dn = agnode(dg, agnameof(n));
395
504
        ND_ptr(dn).clust = (Agraph_t *) n;
396
505
        ND_ptr(n).dn = dn;
397
506
    }
401
510
        Agnode_t *hd;
402
511
        Agnode_t *tl = ND_ptr(n).dn;
403
512
        for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
404
 
            hd = ND_ptr(e->head).dn;
 
513
            hd = ND_ptr(aghead(e)).dn;
405
514
            if (hd == tl)
406
515
                continue;
407
516
            if (hd > tl)
413
522
 
414
523
    return dg;
415
524
}
 
525
#endif
416
526
 
417
527
/* unionNodes:
418
528
 * Add all nodes in cluster nodes of dg to g
424
534
    Agraph_t *clust;
425
535
 
426
536
    for (dn = agfstnode(dg); dn; dn = agnxtnode(dg, dn)) {
 
537
#ifdef USE_CGRAPH
 
538
        if (AGTYPE(ND_ptr(dn)) == AGNODE) {
 
539
            agsubnode(g, ND_dn(dn), 1);
 
540
        } else {
 
541
            clust = ND_clust(dn);
 
542
            for (n = agfstnode(clust); n; n = agnxtnode(clust, n))
 
543
                agsubnode(g, n, 1);
 
544
        }
 
545
#else
427
546
        clust = ND_ptr(dn).clust;
428
547
        if (clust->tag == TAG_NODE) {
429
548
            n = (Agnode_t *) clust;
432
551
            for (n = agfstnode(clust); n; n = agnxtnode(clust, n))
433
552
                aginsert(g, n);
434
553
        }
 
554
#endif
435
555
    }
436
556
}
437
557
 
454
574
        n = agfindnode(g, x_node);
455
575
        if (!n) {
456
576
            fprintf(stderr, "ccomps: node %s not found in graph %s\n",
457
 
                    x_node, g->name);
 
577
                    x_node, agnameof(g));
458
578
            return 1;
459
579
        }
460
 
        name = getBuf(sizeof(PFX1) + strlen(g->name));
461
 
        sprintf(name, PFX1, g->name);
 
580
        name = getBuf(sizeof(PFX1) + strlen(agnameof(g)));
 
581
        sprintf(name, PFX1, agnameof(g));
 
582
#ifdef USE_CGRAPH
 
583
        dout = agsubg(dg, name, 1);
 
584
        out = agsubg(g, name, 1);
 
585
#else
462
586
        dout = agsubg(dg, name);
463
587
        out = agsubg(g, name);
 
588
#endif
464
589
        GD_cc_subg(out) = 1;
 
590
#ifdef USE_CGRAPH
 
591
        dn = ND_dn(n);
 
592
#else
465
593
        dn = ND_ptr(n).dn;
 
594
#endif
466
595
        n_cnt = dfs(dg, dn, dout, 0);
467
596
        unionNodes(dout, out);
468
597
        e_cnt = nodeInduce(out, out->root);
469
598
        if (doAll)
 
599
#ifdef USE_CGRAPH
 
600
            subGInduce(g, out);
 
601
#else
470
602
            subgInduce(g, out, out->name, strlen(out->name), 0);
 
603
#endif
471
604
        gwrite(out);
472
605
        if (verbose)
473
606
            fprintf(stderr, " %7ld nodes %7ld edges\n", n_cnt, e_cnt);
478
611
    for (dn = agfstnode(dg); dn; dn = agnxtnode(dg, dn)) {
479
612
        if (ND_mark(dn))
480
613
            continue;
481
 
        name = getBuf(sizeof(PFX2) + strlen(g->name) + 32);
482
 
        sprintf(name, "%s_component_%ld", g->name, c_cnt);
 
614
        name = getBuf(sizeof(PFX2) + strlen(agnameof(g)) + 32);
 
615
        sprintf(name, "%s_component_%ld", agnameof(g), c_cnt);
 
616
#ifdef USE_CGRAPH
 
617
        dout = agsubg(dg, name, 1);
 
618
        out = agsubg(g, name, 1);
 
619
#else
483
620
        dout = agsubg(dg, name);
484
621
        out = agsubg(g, name);
 
622
#endif
485
623
        GD_cc_subg(out) = 1;
486
624
        n_cnt = dfs(dg, dn, dout, 0);
487
625
        unionNodes(dout, out);
488
626
        e_cnt = nodeInduce(out, out->root);
489
627
        if (printMode == EXTERNAL) {
490
628
            if (doAll)
 
629
#ifdef USE_CGRAPH
 
630
                subGInduce(g, out);
 
631
#else
491
632
                subgInduce(g, out, out->name, strlen(out->name), 0);
 
633
#endif
492
634
            gwrite(out);
493
635
        } else if (printMode == EXTRACT) {
494
636
            if (x_index == c_cnt) {
495
637
                if (doAll)
 
638
#ifdef USE_CGRAPH
 
639
                    subGInduce(g, out);
 
640
#else
496
641
                    subgInduce(g, out, out->name, strlen(out->name), 0);
 
642
#endif
497
643
                gwrite(out);
498
644
                return 0;
499
645
            }
509
655
    if (printMode == EXTRACT) {
510
656
        fprintf(stderr,
511
657
                "ccomps: component %d not found in graph %s - ignored\n",
512
 
                x_index, g->name);
 
658
                x_index, agnameof(g));
513
659
        return 1;
514
660
    }
515
661
 
518
664
 
519
665
    if (verbose)
520
666
        fprintf(stderr, "       %7d nodes %7d edges %7ld components %s\n",
521
 
                agnnodes(g), agnedges(g), c_cnt, g->name);
 
667
                agnnodes(g), agnedges(g), c_cnt, agnameof(g));
522
668
 
523
669
    agclose(dg);
524
670
 
535
681
    Agraph_t *out;
536
682
    Agnode_t *n;
537
683
 
 
684
#ifdef USE_CGRAPH
 
685
    aginit(g, AGNODE, "nodeinfo", sizeof(Agnodeinfo_t), TRUE);
 
686
    aginit(g, AGRAPH, "graphinfo", sizeof(Agraphinfo_t), TRUE);
 
687
#endif
 
688
 
538
689
    if (useClusters)
539
690
        return processClusters(g);
540
691
 
543
694
        if (!n) {
544
695
            fprintf(stderr,
545
696
                    "ccomps: node %s not found in graph %s - ignored\n",
546
 
                    x_node, g->name);
 
697
                    x_node, agnameof(g));
547
698
            return 1;
548
699
        }
549
 
        name = getBuf(sizeof(PFX1) + strlen(g->name));
550
 
        sprintf(name, PFX1, g->name);
 
700
        name = getBuf(sizeof(PFX1) + strlen(agnameof(g)));
 
701
        sprintf(name, PFX1, agnameof(g));
 
702
#ifdef USE_CGRAPH
 
703
        out = agsubg(g, name, 1);
 
704
#else
551
705
        out = agsubg(g, name);
 
706
#endif
552
707
        GD_cc_subg(out) = 1;
553
708
        n_cnt = dfs(g, n, out, 0);
554
709
        e_cnt = nodeInduce(out, out->root);
555
710
        if (doAll)
 
711
#ifdef USE_CGRAPH
 
712
            subGInduce(g, out);
 
713
#else
556
714
            subgInduce(g, out, out->name, strlen(out->name), 0);
 
715
#endif
557
716
        gwrite(out);
558
717
        if (verbose)
559
718
            fprintf(stderr, " %7ld nodes %7ld edges\n", n_cnt, e_cnt);
564
723
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
565
724
        if (ND_mark(n))
566
725
            continue;
567
 
        name = getBuf(sizeof(PFX2) + strlen(g->name) + 32);
568
 
        sprintf(name, "%s_component_%ld", g->name, c_cnt);
 
726
        name = getBuf(sizeof(PFX2) + strlen(agnameof(g)) + 32);
 
727
        sprintf(name, "%s_component_%ld", agnameof(g), c_cnt);
 
728
#ifdef USE_CGRAPH
 
729
        out = agsubg(g, name, 1);
 
730
#else
569
731
        out = agsubg(g, name);
 
732
#endif
570
733
        GD_cc_subg(out) = 1;
571
734
        n_cnt = dfs(g, n, out, 0);
572
735
        e_cnt = nodeInduce(out, out->root);
573
736
        if (printMode == EXTERNAL) {
574
737
            if (doAll)
 
738
#ifdef USE_CGRAPH
 
739
                subGInduce(g, out);
 
740
#else
575
741
                subgInduce(g, out, out->name, strlen(out->name), 0);
 
742
#endif
576
743
            gwrite(out);
577
744
        } else if (printMode == EXTRACT) {
578
745
            if (x_index == c_cnt) {
579
746
                if (doAll)
 
747
#ifdef USE_CGRAPH
 
748
                    subGInduce(g, out);
 
749
#else
580
750
                    subgInduce(g, out, out->name, strlen(out->name), 0);
 
751
#endif
581
752
                gwrite(out);
582
753
                return 0;
583
754
            }
592
763
    if (printMode == EXTRACT) {
593
764
        fprintf(stderr,
594
765
                "ccomps: component %d not found in graph %s - ignored\n",
595
 
                x_index, g->name);
 
766
                x_index, agnameof(g));
596
767
        return 1;
597
768
    }
598
769
 
601
772
 
602
773
    if (verbose)
603
774
        fprintf(stderr, "       %7d nodes %7d edges %7ld components %s\n",
604
 
                agnnodes(g), agnedges(g), c_cnt, g->name);
 
775
                agnnodes(g), agnedges(g), c_cnt, agnameof(g));
605
776
    return (c_cnt ? 1 : 0);
606
777
}
607
778
 
 
779
#ifdef USE_CGRAPH
 
780
static Agraph_t *gread(FILE * fp)
 
781
{
 
782
    return agread(fp, (Agdisc_t *) 0);
 
783
}
 
784
#endif
 
785
 
608
786
int main(int argc, char *argv[])
609
787
{
610
788
    Agraph_t *g;
612
790
    int r = 0;
613
791
 
614
792
    init(argc, argv);
 
793
#ifdef USE_CGRAPH
 
794
    newIngraph(&ig, Files, gread);
 
795
#else
615
796
    newIngraph(&ig, Files, agread);
 
797
#endif
616
798
 
617
799
    while ((g = nextGraph(&ig)) != 0) {
618
800
        r += process(g);