1 | //======================================================================= |
---|
2 | // Copyright 2001 University of Notre Dame. |
---|
3 | // Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee |
---|
4 | // |
---|
5 | // Distributed under the Boost Software License, Version 1.0. (See |
---|
6 | // accompanying file LICENSE_1_0.txt or copy at |
---|
7 | // http://www.boost.org/LICENSE_1_0.txt) |
---|
8 | //======================================================================= |
---|
9 | |
---|
10 | #include <stdio.h> |
---|
11 | #include <iostream> |
---|
12 | #include <boost/graph/stanford_graph.hpp> |
---|
13 | #include <boost/graph/strong_components.hpp> |
---|
14 | |
---|
15 | #define specs(v) \ |
---|
16 | (filename ? index_map[v] : v->cat_no) << " " << v->name |
---|
17 | |
---|
18 | int main(int argc, char* argv[]) |
---|
19 | { |
---|
20 | using namespace boost; |
---|
21 | Graph* g; |
---|
22 | typedef graph_traits<Graph*>::vertex_descriptor vertex_t; |
---|
23 | unsigned long n = 0; |
---|
24 | unsigned long d = 0; |
---|
25 | unsigned long p = 0; |
---|
26 | long s = 0; |
---|
27 | char* filename = NULL; |
---|
28 | int c, i; |
---|
29 | |
---|
30 | while (--argc) { |
---|
31 | if (sscanf(argv[argc], "-n%lu", &n) == 1); |
---|
32 | else if (sscanf(argv[argc], "-d%lu", &d) == 1); |
---|
33 | else if (sscanf(argv[argc], "-p%lu", &p) == 1); |
---|
34 | else if (sscanf(argv[argc], "-s%ld", &s) == 1); |
---|
35 | else if (strncmp(argv[argc], "-g", 2) == 0) |
---|
36 | filename = argv[argc] + 2; |
---|
37 | else { |
---|
38 | fprintf(stderr, "Usage: %s [-nN][-dN][-pN][-sN][-gfoo]\n", argv[0]); |
---|
39 | return -2; |
---|
40 | } |
---|
41 | } |
---|
42 | |
---|
43 | g = (filename ? restore_graph(filename) : roget(n, d, p, s)); |
---|
44 | if (g == NULL) { |
---|
45 | fprintf(stderr, "Sorry, can't create the graph! (error code %ld)\n", |
---|
46 | panic_code); |
---|
47 | return -1; |
---|
48 | } |
---|
49 | printf("Reachability analysis of %s\n\n", g->id); |
---|
50 | |
---|
51 | // - The root map corresponds to what Knuth calls the "min" field. |
---|
52 | // - The discover time map is the "rank" field |
---|
53 | // - Knuth uses the rank field for double duty, to record the |
---|
54 | // discover time, and to keep track of which vertices have |
---|
55 | // been visited. The BGL strong_components() function needs |
---|
56 | // a separate field for marking colors, so we use the w field. |
---|
57 | |
---|
58 | std::vector<int> comp(num_vertices(g)); |
---|
59 | property_map<Graph*, vertex_index_t>::type |
---|
60 | index_map = get(vertex_index, g); |
---|
61 | |
---|
62 | property_map<Graph*, v_property<vertex_t> >::type |
---|
63 | root = get(v_property<vertex_t>(), g); |
---|
64 | |
---|
65 | int num_comp = strong_components |
---|
66 | (g, make_iterator_property_map(comp.begin(), index_map), |
---|
67 | root_map(root). |
---|
68 | discover_time_map(get(z_property<long>(), g)). |
---|
69 | color_map(get(w_property<long>(), g))); |
---|
70 | |
---|
71 | std::vector< std::vector<vertex_t> > strong_comp(num_comp); |
---|
72 | |
---|
73 | // First add representative vertices to each component's list |
---|
74 | graph_traits<Graph*>::vertex_iterator vi, vi_end; |
---|
75 | for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
---|
76 | if (root[*vi] == *vi) |
---|
77 | strong_comp[comp[index_map[*vi]]].push_back(*vi); |
---|
78 | |
---|
79 | // Then add the other vertices of the component |
---|
80 | for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
---|
81 | if (root[*vi] != *vi) |
---|
82 | strong_comp[comp[index_map[*vi]]].push_back(*vi); |
---|
83 | |
---|
84 | // We do not print out the "from" and "to" information as Knuth |
---|
85 | // does because we no longer have easy access to that information |
---|
86 | // from outside the algorithm. |
---|
87 | |
---|
88 | for (c = 0; c < num_comp; ++c) { |
---|
89 | vertex_t v = strong_comp[c].front(); |
---|
90 | std::cout << "Strong component `" << specs(v) << "'"; |
---|
91 | if (strong_comp[c].size() > 1) { |
---|
92 | std::cout << " also includes:\n"; |
---|
93 | for (i = 1; i < strong_comp[c].size(); ++i) |
---|
94 | std::cout << " " << specs(strong_comp[c][i]) << std::endl; |
---|
95 | } else |
---|
96 | std::cout << std::endl; |
---|
97 | } |
---|
98 | |
---|
99 | // Next we print out the "component graph" or "condensation", that |
---|
100 | // is, we consider each component to be a vertex in a new graph |
---|
101 | // where there is an edge connecting one component to another if there |
---|
102 | // is one or more edges connecting any of the vertices from the |
---|
103 | // first component to any of the vertices in the second. We use the |
---|
104 | // name of the representative vertex as the name of the component. |
---|
105 | |
---|
106 | printf("\nLinks between components:\n"); |
---|
107 | |
---|
108 | // This array provides an efficient way to check if we've already |
---|
109 | // created a link from the current component to the component |
---|
110 | // of the target vertex. |
---|
111 | std::vector<int> mark(num_comp, (std::numeric_limits<int>::max)()); |
---|
112 | |
---|
113 | // We go in reverse order just to mimic the output ordering in |
---|
114 | // Knuth's version. |
---|
115 | for (c = num_comp - 1; c >= 0; --c) { |
---|
116 | vertex_t u = strong_comp[c][0]; |
---|
117 | for (i = 0; i < strong_comp[c].size(); ++i) { |
---|
118 | vertex_t v = strong_comp[c][i]; |
---|
119 | graph_traits<Graph*>::out_edge_iterator ei, ei_end; |
---|
120 | for (tie(ei, ei_end) = out_edges(v, g); ei != ei_end; ++ei) { |
---|
121 | vertex_t x = target(*ei, g); |
---|
122 | int comp_x = comp[index_map[x]]; |
---|
123 | if (comp_x != c && mark[comp_x] != c) { |
---|
124 | mark[comp_x] = c; |
---|
125 | vertex_t w = strong_comp[comp_x][0]; |
---|
126 | std::cout << specs(u) << " -> " << specs(w) |
---|
127 | << " (e.g., " << specs(v) << " -> " << specs(x) << ")\n"; |
---|
128 | } // if |
---|
129 | } // for |
---|
130 | } // for |
---|
131 | } // for |
---|
132 | } |
---|