123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133 |
- //=======================================================================
- // 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 <cstdio>
- #include <cstring>
- #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 (boost::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 (boost::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 (boost::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
- }
|