Boost logo

Boost Users :

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


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