← Back to branch summary

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

« back to all changes in this revision

Viewing changes to cmd/tools/acyclic.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/acyclic.c
1
 
/* $Id: acyclic.c,v 1.3 2007/08/08 23:00:58 erg Exp $ $Revision: 1.3 $ */
 
1
/* $Id: acyclic.c,v 1.4 2008/01/09 20:50:35 erg Exp $ $Revision: 1.4 $ */
2
2
/* vim:set shiftwidth=4 ts=8: */
3
3
 
4
4
/**********************************************************
20
20
 * Updated by Emden Gansner
21
21
 */
22
22
 
23
 
typedef char Agraphinfo_t;
24
 
typedef char Agedgeinfo_t;
25
 
typedef struct {
26
 
    int mark;
27
 
    int onstack;
28
 
} Agnodeinfo_t;
29
 
 
30
 
#define ND_mark(n) (n)->u.mark
31
 
#define ND_onstack(n) (n)->u.onstack
32
 
 
33
23
#ifdef HAVE_CONFIG_H
34
24
#include "config.h"
35
25
#endif
38
28
#include        <unistd.h>
39
29
#endif
40
30
#include <stdio.h>
 
31
#ifdef USE_CGRAPH
 
32
#include <stdlib.h>
 
33
#include <cgraph.h>
 
34
typedef struct {
 
35
    Agrec_t h;
 
36
    int mark;
 
37
    int onstack;
 
38
} Agnodeinfo_t;
 
39
 
 
40
#define ND_mark(n) (((Agnodeinfo_t*)((n)->base.data))->mark)
 
41
#define ND_onstack(n) (((Agnodeinfo_t*)((n)->base.data))->onstack)
 
42
#define graphName(g) (agnameof(g))
 
43
#else
 
44
typedef char Agraphinfo_t;
 
45
typedef char Agedgeinfo_t;
 
46
typedef struct {
 
47
    int mark;
 
48
    int onstack;
 
49
} Agnodeinfo_t;
 
50
 
 
51
#define ND_mark(n) (n)->u.mark
 
52
#define ND_onstack(n) (n)->u.onstack
 
53
#define aghead(e) ((e)->head)
 
54
#define agtail(e) ((e)->tail)
 
55
#define graphName(g) ((g)->name)
 
56
 
41
57
#include <graph.h>
 
58
#endif
42
59
 
43
60
#ifdef HAVE_GETOPT_H
44
61
#include <getopt.h>
52
69
static int Verbose;
53
70
static char *cmd;
54
71
 
 
72
/* addRevEdge:
 
73
 * Add a reversed version of e. The new edge has the same key.
 
74
 * We also copy the attributes, reversing the roles of head and 
 
75
 * tail ports.
 
76
 * This assumes we've already checked that such an edge does not exist.
 
77
 */
55
78
static void addRevEdge(Agraph_t * g, Agedge_t * e)
56
79
{
 
80
#ifdef USE_CGRAPH
 
81
    Agsym_t* sym;
 
82
    Agedge_t* f = agedge (g, aghead(e), agtail(e), agnameof(e), 1);
 
83
 
 
84
    agcopyattr (e, f);
 
85
 
 
86
    sym = agattr (g, AGEDGE, TAILPORT_ID, 0);
 
87
    if (sym) agsafeset (f, HEADPORT_ID, agxget (e, sym), "");
 
88
    sym = agattr (g, AGEDGE, HEADPORT_ID, 0);
 
89
    if (sym) agsafeset (f, TAILPORT_ID, agxget (e, sym), "");
 
90
#else
57
91
    Agedge_t *reve;
58
92
    char *tmps;
59
93
    char **attrs;
72
106
    tmps = reve->attr[1];
73
107
    reve->attr[1] = reve->attr[2];
74
108
    reve->attr[2] = tmps;
 
109
#endif
75
110
}
76
111
 
77
112
static int dfs(Agraph_t * g, Agnode_t * t, int hasCycle)
84
119
    ND_onstack(t) = 1;
85
120
    for (e = agfstout(g, t); e; e = f) {
86
121
        f = agnxtout(g, e);
87
 
        if (e->tail == e->head)
 
122
        if (agtail(e) == aghead(e))
88
123
            continue;
89
 
        h = e->head;
 
124
        h = aghead(e);
90
125
        if (ND_onstack(h)) {
 
126
#ifdef USE_CGRAPH
 
127
            if (agisstrict(g)) {
 
128
                if (agedge(g, h, t, 0, 0) == 0)
 
129
                    addRevEdge(g, e);
 
130
            } else {
 
131
                char* key = agnameof (e);
 
132
                if (!key || (agedge(g, h, t, key, 0) == 0))
 
133
                    addRevEdge(g, e);
 
134
            }
 
135
#else
91
136
            if (AG_IS_STRICT(g)) {
92
137
                if (agfindedge(g, h, t) == 0)
93
138
                    addRevEdge(g, e);
94
139
            } else
95
140
                addRevEdge(g, e);
 
141
#endif
96
142
            agdelete(g, e);
97
143
            hasCycle = 1;
98
144
        } else if (ND_mark(h) == 0)
137
183
    int c;
138
184
 
139
185
    cmd = argv[0];
 
186
#ifndef USE_CGRAPH
140
187
    aginit();
 
188
#endif
141
189
 
142
190
    while ((c = getopt(argc, argv, ":vno:?")) != -1)
143
191
        switch (c) {
182
230
 
183
231
    init(argc, argv);
184
232
 
 
233
#ifdef USE_CGRAPH
 
234
    if ((g = agread(inFile,  (Agdisc_t *) 0)) != 0) {
 
235
        if (agisdirected (g)) {
 
236
            aginit(g, AGNODE, "info", sizeof(Agnodeinfo_t), TRUE);
 
237
#else
185
238
    if ((g = agread(inFile)) != 0) {
186
239
        if (AG_IS_DIRECTED(g)) {
 
240
#endif
187
241
            for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
188
242
                if (ND_mark(n) == 0)
189
243
                    rv |= dfs(g, n, 0);
194
248
            }
195
249
            if (Verbose) {
196
250
                if (rv)
197
 
                    fprintf(stderr, "Graph %s has cycles\n", g->name);
 
251
                    fprintf(stderr, "Graph %s has cycles\n", graphName(g));
198
252
                else
199
 
                    fprintf(stderr, "Graph %s is acyclic\n", g->name);
 
253
                    fprintf(stderr, "Graph %s is acyclic\n", graphName(g));
200
254
            }
201
255
        } else {
202
256
            rv = 2;
203
257
            if (Verbose)
204
 
                fprintf(stderr, "Graph %s is undirected\n", g->name);
 
258
                fprintf(stderr, "Graph %s is undirected\n", graphName(g));
205
259
        }
206
260
        exit(rv);
207
261
    } else