[Boost-users] [BGL] dijkstra_shortest_paths with listS

Subject: [Boost-users] [BGL] dijkstra_shortest_paths with listS
From: gast128 (gast128_at_[hidden])
Date: 2010-01-04 09:46:57

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 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;
   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);
   
   //note: color map not needed, because of index map?
   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;
   }
}