[Boost-users] Newbie Q: Boost Graph stuff

From: Ori (opr9t_at_[hidden])
Date: 2004-03-15 00:47:56

Hi everyone,

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.

The application here is a rigid body simulator, and I'm constructing a 
graph of contact points between bodies. The idea is to find an ordering 
to apply collision impulses, which logically means from the ground up. 
Vertices are thus bodies, and edges denote a contact (collision) case.

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 : )

Any help someone out there can give is really appreciated. Thanks!

~ Ori