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@gmail.com