Re: [Boost-users] [Graph] problem with arguments of transitive closure algorithm ?

From: Stephan Diederich (stephan.diederich_at_[hidden])
Date: 2007-08-02 08:16:31

Hi Emmanuel,

On 8/1/07, Emmanuel Viaud <emmanuel.viaud_at_[hidden]> wrote:
> Hello.
>
> Using Boost 1.34.1 (with g++-3.4.2) and more specifically the Boost
> Graph library, I stumbled on a small problem with the
> transitive_closure algorithm.
>
> I saw in the documentation that I can get a map containing the mapping
> between the vertices of the original graph and the ones in the
> transitive closure graph (the orig_to_copy parameter). But every time
> I call the method, I get an empty map as a result.
> To sum up my code, I use the following data structures for the graph:
>
> typedef boost::adjacency_list < boost::vecS, boost::vecS,
> boost::directedS > graph_t;
> typedef boost::graph_traits < graph_t >::vertex_descriptor vertex_t;
>
> and the following one for the expected map:
>
> typedef std::map < vertex_t, vertex_t > ioMap_t;
>
> The graphs and map are declared the following way:
>
> graph_t myGraph;
> graph_t myTCGraph;
>
> ioMap_t ioMap;
>
>
> I used both versions of the algorithm:
>  1) using named parameters, I call:
>     transitive_closure(myGraph, myTCGraph, orig_to_copy(ioMap));
>
>  2) using "standard" parameters, I call:
>     transitive_closure(myGraph, myTCGraph, ioMap, get(vertex_index, myGraph));
>
> So, the main question is easy: Where did I write something wrong ? :-)

You did not pass transitive_closure a property map. Instead you give
the algorithm a std::map.

typedef std::map < vertex_t, vertex_t > ioMap_t;
ioMap_t vertex_vertex_map;
boost::associative_property_map< std::map<vertex_t, vertex_t> >
ioMap(vertex_vertex_map);

Should work.
To speed things up, you could also use a std::vector and let the
specialization of property maps for pointers kick in.
Create the container:
std::vector<vertex_t> ioMap(num_vertices(myGraph));
and use it:
transitive_closure(myGraph, myTCGraph, &ioMap[0], get(vertex_index, myGraph));

An additional
function_requires < Mutable_LvaluePropertyMapConcept <
G_to_TC_VertexMap, vertex > >();
in transitive_closure would have spotted that problem.

HTH,
Stephan