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
|
/* $Id: decomp.c,v 1.5 2009/06/03 01:10:52 ellson Exp $ $Revision: 1.5 $ */
/* vim:set shiftwidth=4 ts=8: */
/**********************************************************
* This software is part of the graphviz package *
* http://www.graphviz.org/ *
* *
* Copyright (c) 1994-2004 AT&T Corp. *
* and is licensed under the *
* Common Public License, Version 1.0 *
* by AT&T Corp. *
* *
* Information and Software Systems Research *
* AT&T Research, Florham Park NJ *
**********************************************************/
/*
* Decompose finds the connected components of a graph.
* It searches the temporary edges and ignores non-root nodes.
* The roots of the search are the real nodes of the graph,
* but any virtual nodes discovered are also included in the
* component.
*/
#include "dot.h"
static graph_t *G;
static node_t *Last_node;
static char Cmark;
static void
begin_component(void)
{
Last_node = GD_nlist(G) = NULL;
}
static void
add_to_component(node_t * n)
{
GD_n_nodes(G)++;
ND_mark(n) = Cmark;
if (Last_node) {
ND_prev(n) = Last_node;
ND_next(Last_node) = n;
} else {
ND_prev(n) = NULL;
GD_nlist(G) = n;
}
Last_node = n;
ND_next(n) = NULL;
}
static void
end_component(void)
{
int i;
i = GD_comp(G).size++;
GD_comp(G).list = ALLOC(GD_comp(G).size, GD_comp(G).list, node_t *);
GD_comp(G).list[i] = GD_nlist(G);
}
static void
search_component(graph_t * g, node_t * n)
{
int c, i;
elist vec[4];
node_t *other;
edge_t *e;
add_to_component(n);
vec[0] = ND_out(n);
vec[1] = ND_in(n);
vec[2] = ND_flat_out(n);
vec[3] = ND_flat_in(n);
for (c = 0; c <= 3; c++) {
if (vec[c].list)
for (i = 0; (e = vec[c].list[i]); i++) {
if ((other = aghead(e)) == n)
other = agtail(e);
if ((ND_mark(other) != Cmark) && (other == UF_find(other)))
search_component(g, other);
}
}
}
void decompose(graph_t * g, int pass)
{
graph_t *subg;
node_t *n, *v;
G = g;
if (++Cmark == 0)
Cmark = 1;
GD_n_nodes(g) = GD_comp(g).size = 0;
for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
v = n;
if ((pass > 0) && (subg = ND_clust(v)))
v = GD_rankleader(subg)[ND_rank(v)];
else if (v != UF_find(v))
continue;
if (ND_mark(v) != Cmark) {
begin_component();
search_component(g, v);
end_component();
}
}
}
|
