[Boost-users] Re: Newbie Q: Boost Graph stuff

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 Edge; struct pen_index_t { typedef edge_property_tag kind; }; typedef property PenProperty; typedef adjacency_list Graph; typedef adjacency_list 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