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
|
//=======================================================================
// Copyright 2001 University of Notre Dame.
// Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#include <stdio.h>
#include <iostream>
#include <boost/graph/stanford_graph.hpp>
#include <boost/graph/strong_components.hpp>
#define specs(v) \
(filename ? index_map[v] : v->cat_no) << " " << v->name
int main(int argc, char* argv[])
{
using namespace boost;
Graph* g;
typedef graph_traits<Graph*>::vertex_descriptor vertex_t;
unsigned long n = 0;
unsigned long d = 0;
unsigned long p = 0;
long s = 0;
char* filename = NULL;
int c, i;
while (--argc) {
if (sscanf(argv[argc], "-n%lu", &n) == 1);
else if (sscanf(argv[argc], "-d%lu", &d) == 1);
else if (sscanf(argv[argc], "-p%lu", &p) == 1);
else if (sscanf(argv[argc], "-s%ld", &s) == 1);
else if (strncmp(argv[argc], "-g", 2) == 0)
filename = argv[argc] + 2;
else {
fprintf(stderr, "Usage: %s [-nN][-dN][-pN][-sN][-gfoo]\n", argv[0]);
return -2;
}
}
g = (filename ? restore_graph(filename) : roget(n, d, p, s));
if (g == NULL) {
fprintf(stderr, "Sorry, can't create the graph! (error code %ld)\n",
panic_code);
return -1;
}
printf("Reachability analysis of %s\n\n", g->id);
// - The root map corresponds to what Knuth calls the "min" field.
// - The discover time map is the "rank" field
// - Knuth uses the rank field for double duty, to record the
// discover time, and to keep track of which vertices have
// been visited. The BGL strong_components() function needs
// a separate field for marking colors, so we use the w field.
std::vector<int> comp(num_vertices(g));
property_map<Graph*, vertex_index_t>::type
index_map = get(vertex_index, g);
property_map<Graph*, v_property<vertex_t> >::type
root = get(v_property<vertex_t>(), g);
int num_comp = strong_components
(g, make_iterator_property_map(comp.begin(), index_map),
root_map(root).
discover_time_map(get(z_property<long>(), g)).
color_map(get(w_property<long>(), g)));
std::vector< std::vector<vertex_t> > strong_comp(num_comp);
// First add representative vertices to each component's list
graph_traits<Graph*>::vertex_iterator vi, vi_end;
for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
if (root[*vi] == *vi)
strong_comp[comp[index_map[*vi]]].push_back(*vi);
// Then add the other vertices of the component
for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
if (root[*vi] != *vi)
strong_comp[comp[index_map[*vi]]].push_back(*vi);
// We do not print out the "from" and "to" information as Knuth
// does because we no longer have easy access to that information
// from outside the algorithm.
for (c = 0; c < num_comp; ++c) {
vertex_t v = strong_comp[c].front();
std::cout << "Strong component `" << specs(v) << "'";
if (strong_comp[c].size() > 1) {
std::cout << " also includes:\n";
for (i = 1; i < strong_comp[c].size(); ++i)
std::cout << " " << specs(strong_comp[c][i]) << std::endl;
} else
std::cout << std::endl;
}
// Next we print out the "component graph" or "condensation", that
// is, we consider each component to be a vertex in a new graph
// where there is an edge connecting one component to another if there
// is one or more edges connecting any of the vertices from the
// first component to any of the vertices in the second. We use the
// name of the representative vertex as the name of the component.
printf("\nLinks between components:\n");
// This array provides an efficient way to check if we've already
// created a link from the current component to the component
// of the target vertex.
std::vector<int> mark(num_comp, (std::numeric_limits<int>::max)());
// We go in reverse order just to mimic the output ordering in
// Knuth's version.
for (c = num_comp - 1; c >= 0; --c) {
vertex_t u = strong_comp[c][0];
for (i = 0; i < strong_comp[c].size(); ++i) {
vertex_t v = strong_comp[c][i];
graph_traits<Graph*>::out_edge_iterator ei, ei_end;
for (tie(ei, ei_end) = out_edges(v, g); ei != ei_end; ++ei) {
vertex_t x = target(*ei, g);
int comp_x = comp[index_map[x]];
if (comp_x != c && mark[comp_x] != c) {
mark[comp_x] = c;
vertex_t w = strong_comp[comp_x][0];
std::cout << specs(u) << " -> " << specs(w)
<< " (e.g., " << specs(v) << " -> " << specs(x) << ")\n";
} // if
} // for
} // for
} // for
}
|
