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
139
140
141
142
143
144
145
146
147
148
|
//=======================================================================
// Copyright 2001 University of Notre Dame.
// Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
//
// This file is part of the Boost Graph Library
//
// You should have received a copy of the License Agreement for the
// Boost Graph Library along with the software; see the file LICENSE.
// If not, contact Office of Research, University of Notre Dame, Notre
// Dame, IN 46556.
//
// Permission to modify the code and to distribute modified code is
// granted, provided the text of this NOTICE is retained, a notice that
// the code was modified is included with the above COPYRIGHT NOTICE and
// with the COPYRIGHT NOTICE in the LICENSE file, and that the LICENSE
// file is distributed with the modified code.
//
// LICENSOR MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED.
// By way of example, but not limitation, Licensor MAKES NO
// REPRESENTATIONS OR WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY
// PARTICULAR PURPOSE OR THAT THE USE OF THE LICENSED SOFTWARE COMPONENTS
// OR DOCUMENTATION WILL NOT INFRINGE ANY PATENTS, COPYRIGHTS, TRADEMARKS
// OR OTHER RIGHTS.
//=======================================================================
#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
}
|
