Re: [Boost-users] [BGL] dijkstra_shortest_paths with listS

Subject: Re: [Boost-users] [BGL] dijkstra_shortest_paths with listS
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-01-04 18:29:24

On Mon, 4 Jan 2010, gast128 wrote:

> Hello all,
>
> BGL supports a lot of graph algorithms, and lots of stuff get default filled
> in when using vecS as container type of vertices. However things become pretty
> ugly when not using this container. Below I used a listS for both edges and
> vertices. Maybe it can help other people (and maybe somebody can cross check
> me). Note that some constructs could be bundled, but for clearity I explicitly
> wrote all things out.

I think this is right.  I put a few notes in it.

> I use the graph from the BGL book as example (figure 13.3).
>
>
> void TestgraphDijkstra()
> {
>   typedef boost::adjacency_list<boost::listS,
>                                 boost::listS,
>                                 boost::bidirectionalS,
>                                 std::string>            Graph;

I know about your note about not using properties for everything possible, 
but using an old-style vertex_index property would make some things like 
color maps much easier.  However, your way (an external property) works 
well also.

>   typedef boost::graph_traits<Graph>::vertex_descriptor VertexDescriptor;
>   typedef boost::graph_traits<Graph>::edge_descriptor   EdgeDescriptor;
>
>   typedef int                                           Weight;
>
>   typedef std::map<EdgeDescriptor, Weight>              WeightMap;
>   typedef std::map<VertexDescriptor, size_t>            VertexIndexMap;
>   typedef std::map<VertexDescriptor, Weight>            DistanceMap;
>   typedef std::map<VertexDescriptor, VertexDescriptor>  PredecessorMap;
>
>   Graph                                           graph;
>
>   WeightMap                                       mapWeigth;
>   VertexIndexMap                                  mapVertexIndex;
>   DistanceMap                                     mapDistance;
>   PredecessorMap                                  mapPredecessor;
>
>   boost::associative_property_map<WeightMap>      pmWeigth(mapWeigth);
>   boost::associative_property_map<VertexIndexMap> pmVertexIndex
> (mapVertexIndex);
>   boost::associative_property_map<DistanceMap>    pmDistance(mapDistance);
>   boost::associative_property_map<PredecessorMap> pmPredecessor
> (mapPredecessor);
>
>   //build a graph according to figure 13.3
>
>   //add vertices
>   const VertexDescriptor vA  = boost::add_vertex(graph);
>   const VertexDescriptor vB  = boost::add_vertex(graph);
>   const VertexDescriptor vC  = boost::add_vertex(graph);
>   const VertexDescriptor vD  = boost::add_vertex(graph);
>   const VertexDescriptor vE  = boost::add_vertex(graph);
>
>   //set vertex names
>   graph[vA] = "A";
>   graph[vB] = "B";
>   graph[vC] = "C";
>   graph[vD] = "D";
>   graph[vE] = "E";
>
>   //add edges
>   const EdgeDescriptor eAC = boost::add_edge(vA, vC, graph).first;
>   const EdgeDescriptor eBB = boost::add_edge(vB, vB, graph).first;
>   const EdgeDescriptor eBD = boost::add_edge(vB, vD, graph).first;
>   const EdgeDescriptor eBE = boost::add_edge(vB, vE, graph).first;
>   const EdgeDescriptor eCB = boost::add_edge(vC, vB, graph).first;
>   const EdgeDescriptor eCD = boost::add_edge(vC, vD, graph).first;
>   const EdgeDescriptor eDE = boost::add_edge(vD, vE, graph).first;
>   const EdgeDescriptor eEB = boost::add_edge(vE, vB, graph).first;
>   const EdgeDescriptor eEA = boost::add_edge(vE, vA, graph).first;
>
>   //set edge weights
>   boost::put(pmWeigth, eAC, 1);
>   boost::put(pmWeigth, eBB, 2);
>   boost::put(pmWeigth, eBD, 1);
>   boost::put(pmWeigth, eBE, 2);
>   boost::put(pmWeigth, eCB, 7);
>   boost::put(pmWeigth, eCD, 3);
>   boost::put(pmWeigth, eDE, 1);
>   boost::put(pmWeigth, eEB, 1);
>   boost::put(pmWeigth, eEA, 1);
>
>   //build index map
>   boost::put(pmVertexIndex, vA, 0);
>   boost::put(pmVertexIndex, vB, 1);
>   boost::put(pmVertexIndex, vC, 2);
>   boost::put(pmVertexIndex, vD, 3);
>   boost::put(pmVertexIndex, vE, 4);

An easier way is to just loop over the vertices and assign indices 
sequentially, making index assignment independent from the actual graph 
structure.  You can use the (currently undocumented) header 
<boost/graph/iteration_macros.hpp> for that:

{
   int i = 0;
   BGL_FORALL_VERTICES(v, graph, Graph) {
     boost::put(pmVertexIndex, v, i++);
}

>   //note: color map not needed, because of index map?

That is correct.  For the color map, the following three possibilities are 
tried (in order) by the algorithm:

1. An explicitly specified color map.
2. Creating a new color map using an explicitly specified vertex index 
map.
3. Creating a new color map using a named vertex_index property in the 
graph.

>   boost::dijkstra_shortest_paths(graph, vA, boost::weight_map
> (pmWeigth).vertex_index_map(pmVertexIndex).distance_map
> (pmDistance).predecessor_map(pmPredecessor));
>
>   for (DistanceMap::const_iterator itDist = mapDistance.begin(); itDist !=
> mapDistance.end(); ++itDist)
>   {
>      //dump
>      const VertexDescriptor v     = itDist->first;
>      const VertexDescriptor vPrev = mapPredecessor[v];
>
>      std::cout << "Distance(" << graph[v] << ") = " << itDist->second
>               << ", "
>               << "Parent("   << graph[v] << ") = " << graph[vPrev]
>               << std::endl;
>   }
> }

-- Jeremiah Willcock