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

4 Jan 2010


      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