Re: [Boost-users] [graph] predecessor_recorder and VertexList=listS

Subject: Re: [Boost-users] [graph] predecessor_recorder and VertexList=listS
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2008-10-31 11:16:03

>
> I've following graph:
> typedef adjacency_list<vecS, listS, bidirectionalS,
> property<vertex_distance_t, unsigned int, VertexContainer   >, cPose>
> BGLGraph
> typedef graph_traits<BGLGraph>::vertex_descriptor BGLVertexDescriptor;
>
> with VertexList=listS, two vertex properties (distance map and a bundled
> property VertexContainer) and a bundled edge property cPose.
>
> Now I try to create a predecessor map with the predecessor_recorder but I'm
> not able to create a map that obtains the predecessor informations. I know I
> can't use std::vector<BGLVertexDescriptor> like the example (
> http://www.boost.org/doc/libs/1_35_0/libs/graph/example/bfs.cpp) because I
> use VertexList=listS. HenceI tried std::map<BGLVertexDescriptor,
> BGLVertexDescriptor> but this leads to another compiler error.
>

The short answer is: don't use listS :)

For the long answer, it would be nice to know the compiler error, but you're
going about it the wrong way - in two ways. First, there ar two components
to building property maps - the source (frequently a container of some kind)
and the map. The source is responsible for implementing the mapping of
vertex (or edge) descriptor to data. The map implements the put() and get()
functions for the source. Just creating a map (as you've just done) is only
half the job. You need to create teh map.

typedef std::map<Vertex, Vertex> PredSource;
typedef associative_property_map<Source> PredMap;

PredSource preds;
PredMap pm(preds);
put(*vertices(g).first, *vertices(g).first); // root has itself as a parent

Now you should be able to use pm as a predecessor map any place that
requires one.

The second reason this is the wrong way is that you really want to create a
vertex index map for your graph. Graphs with vecS vertex stores have one by
default. Since you're using listS, you need to do a little more work. See
the attached for two methods of creating index maps. Most algorithms create
exterior properties (labels/property maps) as vectors by default. A vector
only works as the source of a property map if you have a vertex index map
(mapping descriptor to index). The attached file shows two ways of doing
this - one using a completely external property, the other using bundled
properties to accomplish the same thing.

Note that the external map will result in significantly slower algorithms
since lookups in std::map are O(lg n). You could swap std::map for
unordered_map and improved lookup times, but there might be some weird
library issues lurking around.

Andrew Sutton
andrew.n.sutton_at_[hidden]