Boost logo

Boost Users :

From: Vladimir Prus (ghost_at_[hidden])
Date: 2004-03-15 02:23:54


Hi Ori,

> I have a question concerning the Boost Graph library, specifically with
> strongly connected components.
>
> My problem is this:
> I have a graph that I need to collapse into strongly connected
> components, then topologically sort the resulting DAG of components.
> Then I want to traverse the sorted DAG (in order), and for each
> component (now just a vertex I guess), look up into the original graph
> to find all the vertices that belong to this component.

I suggest that you take a look at boost/graph/transitive_closure.hpp. The
implementation there does all you ask for, except for traversing the sorted
DAG. I'm not sure you can immediately use that implementation, but it could
be a starting point.

> I've constructed the original graph, and using the example online,
> performed the strong_components algorithm on it. However, I'm unsure of
> how to correctly create a graph of the components. I presume using the
> root_map is somehow involved, but I'm kind of at a loss. Here's what I
> got:
>
> // typedefs, most stolen from graph introduction at boost.org
> typedef std::pair<int, int> Edge;
> struct pen_index_t { typedef edge_property_tag kind; };
> typedef property<pen_index_t, int> PenProperty;
> typedef adjacency_list<vecS, vecS, directedS, no_property, PenProperty>
> Graph;
> typedef adjacency_list<setS, vecS, directedS, no_property, PenProperty>
> ComponentGraph;
> typedef graph_traits<Graph>::vertex_descriptor Vertex;
>
> ...
>
> // actual code
> Graph contactGraph(NUM_BODIES);
>
> ... various junk to fill up the graph ...
>
> // now, collapse strongly connected components
> vector<int> component(num_vertices(contactGraph));
> vector<Vertex> root(num_vertices(contactGraph));
> bgl_named_params< Vertex*, vertex_root_t, no_property> rootMap =
> root_map(&root[0]);
> int num = strong_components(contactGraph, &component[0], rootMap);
>
> // create a new graph with each component as a vertex...
> // ...how?
>
> I tried variations on get(...) on the rootMap and such, but was met with
> the usual nightmarish stl/boost compiler errors when you mess up
> something involving templates : )

Frankly, I don't know if 'rootMap' is of any use here. My code was:

   vector< vector<int> > condensation_graph(num);
   for /* (s,t) in all original edges */
        condensation_graph[component[s]].push_back(component[t]);

HTH,
Volodya


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net