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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
/*************************************************************************
* 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
*
* Contributors: Details at https://graphviz.org
*************************************************************************/
/* comp.c:
* Written by Emden R. Gansner
*
* Support for "connected components". Components are either connected
* or have a port node or have a pinned node.
*
*/
/* use PRIVATE interface */
#define FDP_PRIVATE 1
#include <cgraph/cgraph.h>
#include <fdpgen/fdp.h>
#include <fdpgen/comp.h>
#include <pack/pack.h>
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <util/agxbuf.h>
#include <util/alloc.h>
#include <util/bitarray.h>
#include <util/prisize_t.h>
static void dfs(Agraph_t *g, Agnode_t *n, Agraph_t *out, bitarray_t *marks) {
Agedge_t *e;
Agnode_t *other;
bitarray_set(marks, ND_id(n), true);
agsubnode(out,n,1);
for (e = agfstedge(g, n); e; e = agnxtedge(g, e, n)) {
if ((other = agtail(e)) == n)
other = aghead(e);
if (!bitarray_get(*marks, ND_id(other)))
dfs(g, other, out, marks);
}
}
/* findCComp:
* Finds generalized connected components of graph g.
* This merges all components containing a port node or a pinned node.
* Assumes nodes have unique id's in range [0,agnnodes(g)-1].
* Components are stored as subgraphs of g, with name sg_<i>.
* Returns 0-terminated array of components.
* If cnt is non-0, count of components is stored there.
* If pinned is non-0, *pinned is set to 1 if there are pinned nodes.
* Note that if ports and/or pinned nodes exists, they will all be
* in the first component returned by findCComp.
*/
static size_t C_cnt = 0;
graph_t **findCComp(graph_t *g, size_t *cnt, int *pinned) {
node_t *n;
graph_t *subg;
agxbuf name = {0};
size_t c_cnt = 0;
bport_t *pp;
graph_t **comps;
graph_t **cp;
int pinflag = 0;
assert(agnnodes(g) >= 0);
bitarray_t marks = bitarray_new((size_t)agnnodes(g));
/* Create component based on port nodes */
subg = 0;
if ((pp = PORTS(g))) {
agxbprint(&name, "cc%s_%" PRISIZE_T, agnameof(g), c_cnt++ + C_cnt);
subg = agsubg(g, agxbuse(&name), 1);
agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), true);
GD_alg(subg) = gv_alloc(sizeof(gdata));
PORTS(subg) = pp;
NPORTS(subg) = NPORTS(g);
for (; pp->n; pp++) {
if (bitarray_get(marks, ND_id(pp->n)))
continue;
dfs(g, pp->n, subg, &marks);
}
}
/* Create/extend component based on pinned nodes */
/* Note that ports cannot be pinned */
for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
if (bitarray_get(marks, ND_id(n)))
continue;
if (ND_pinned(n) != P_PIN)
continue;
if (!subg) {
agxbprint(&name, "cc%s_%" PRISIZE_T, agnameof(g), c_cnt++ + C_cnt);
subg = agsubg(g, agxbuse(&name), 1);
agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), true);
GD_alg(subg) = gv_alloc(sizeof(gdata));
}
pinflag = 1;
dfs(g, n, subg, &marks);
}
if (subg)
(void)graphviz_node_induce(subg, NULL);
/* Pick up remaining components */
for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
if (bitarray_get(marks, ND_id(n)))
continue;
agxbprint(&name, "cc%s+%" PRISIZE_T, agnameof(g), c_cnt++ + C_cnt);
subg = agsubg(g, agxbuse(&name), 1);
agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), true); //node custom data
GD_alg(subg) = gv_alloc(sizeof(gdata));
dfs(g, n, subg, &marks);
(void)graphviz_node_induce(subg, NULL);
}
bitarray_reset(&marks);
agxbfree(&name);
C_cnt += c_cnt;
if (cnt)
*cnt = c_cnt;
if (pinned)
*pinned = pinflag;
/* freed in layout */
comps = cp = gv_calloc(c_cnt + 1, sizeof(graph_t*));
for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
*cp++ = subg;
c_cnt--;
}
assert(c_cnt == 0);
*cp = 0;
return comps;
}
|
