Re: [Boost-users] [BGL, Graph] listS and property maps

From: Johan Oudinet (johan.oudinet_at_[hidden])
Date: 2005-11-17 08:15:35

On 11/15/05, Stephane Grabli <Stephane.Grabli_at_[hidden]> wrote:
> Hi,
>
> I'm new to the BGL and I'm trying to use the strong_components
> algorithm, defined this way:
>
> template <class Graph, class ComponentMap, class P, class T, class R>
> typename property_traits<ComponentMap>::value_type
> strong_components(Graph& g, ComponentMap comp,
>     const bgl_named_params<P, T, R>& params = all defaults)
>
> with a graph
> defined like this:
>
> typedef adjacency_list<listS,listS,directedS> Graph;
>
> (in particular using listS for vertices storage).
>
> Does anyone know how I should declare the ComponentMap property map?
> I couldn't figure this out from the documentation and the examples I've
> seen all assume that a vecS type storage is used for vertices in the graph.
> Thanks!
>

When you use vecS for vertices storage, BGL provides a default
property : vertex_index
A lot of BGL algorithms (like strong_components) need a
vertex_index_map and the default value is get(vertex_index, g).
Unfortunately, when you use a different vertices container, there
isn't the vertex_index property by default (because there isn't an
efficient way to do it).
So you have 2 solutions:
1) Add a vertex_index property in your graph
2) Provide a vertex_index_map when you call the strong_components
algorithm (never use the default vertex_index_map unless the
vertex_index property is defined)

How to do 1) is explained by Aaron Windsor in this thread, and to do
2) follow the instuctions provide by Gregoire Dooms in this thread
too, add call the algorithm with your vertex_index map:
strong_components(g, comp,
      vertex_index_map (make_associative_property_map (your_map)));
--
Johan