1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
/**
* @file
* @brief make directed graph acyclic, implements @ref graphviz_acyclic, used
* in cmd/tools/acyclic.c
*
* @ingroup cgraph_app
*
* Copyright (c) 2011 AT&T Intellectual Property
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
* https://www.eclipse.org/legal/epl-v10.html
*
* Authors: Stephen North, Emden Gansner
* Contributors: Details at https://graphviz.org
*/
#include <cgraph/cghdr.h>
#include <stdbool.h>
#include <stddef.h>
typedef struct {
Agrec_t h;
int mark;
bool onstack : 1;
} Agnodeinfo_t;
#define ND_mark(n) (((Agnodeinfo_t *)((n)->base.data))->mark)
#define ND_onstack(n) (((Agnodeinfo_t *)((n)->base.data))->onstack)
#define graphName(g) (agnameof(g))
/* Add a reversed version of e. The new edge has the same key.
* We also copy the attributes, reversing the roles of head and
* tail ports.
* This assumes we've already checked that such an edge does not exist.
*/
static void addRevEdge(Agraph_t *g, Agedge_t *e) {
Agsym_t *sym;
Agedge_t *f = agedge(g, aghead(e), agtail(e), agnameof(e), 1);
agcopyattr(e, f);
sym = agattr_text(g, AGEDGE, TAILPORT_ID, 0);
if (sym)
agsafeset(f, HEADPORT_ID, agxget(e, sym), "");
sym = agattr_text(g, AGEDGE, HEADPORT_ID, 0);
if (sym)
agsafeset(f, TAILPORT_ID, agxget(e, sym), "");
}
/// Return true if the graph has a cycle.
static bool dfs(Agraph_t *g, Agnode_t *t, bool hasCycle, size_t *num_rev) {
Agedge_t *e;
Agedge_t *f;
Agnode_t *h;
ND_mark(t) = 1;
ND_onstack(t) = true;
for (e = agfstout(g, t); e; e = f) {
f = agnxtout(g, e);
if (agtail(e) == aghead(e))
continue;
h = aghead(e);
if (ND_onstack(h)) {
if (agisstrict(g)) {
if (agedge(g, h, t, 0, 0) == 0) {
addRevEdge(g, e);
++*num_rev;
}
} else {
char *key = agnameof(e);
if (!key || agedge(g, h, t, key, 0) == 0) {
addRevEdge(g, e);
++*num_rev;
}
}
agdelete(g, e);
hasCycle = true;
} else if (ND_mark(h) == 0)
hasCycle |= dfs(g, h, hasCycle, num_rev);
}
ND_onstack(t) = false;
return hasCycle;
}
bool graphviz_acyclic(Agraph_t *g, const graphviz_acyclic_options_t *opts,
size_t *num_rev) {
bool has_cycle = false;
aginit(g, AGNODE, "info", sizeof(Agnodeinfo_t), true);
for (Agnode_t *n = agfstnode(g); n; n = agnxtnode(g, n)) {
if (ND_mark(n) == 0) {
has_cycle |= dfs(g, n, false, num_rev);
}
}
if (opts->doWrite) {
agwrite(g, opts->outFile);
fflush(opts->outFile);
}
return has_cycle;
}
|
