[boost] BGL: dijkstra_shortest_paths and adjacency_list<listS, listS, undirectedS>

From: jsiek_at_[hidden]
Date: 2000-10-06 11:03:37

Hi Jan,

Jan van der Veen writes:
 > The enclosed file (a slight modification of dijkstra.cpp) does not
 > compile (g++ 2.95.2) unless VertexList=vecS. I understand why this is
 > the case. Still, I would like to ask if it is possible to rewrite
 > dijkstra_shortest_paths to at least accept VertexList=listS.

The difference between VertexList=vecS and VertexList=listS that is
causing you trouble is that the vecS version has a builtin
vertex_index property (in fact, the vertex_descriptors are integers),
while listS does not, and dijkstra requires the vertex_index
property. I've changed the example below to explicitly add
vertex_index to the graph, and to initialize the vertex indices.

Cheers,

Jeremy

#include <iostream>

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/transpose_graph.hpp>

using namespace boost;

int main(int argc, char* argv[])
{
    typedef adjacency_list<listS, listS, undirectedS,
                    property<vertex_index_t, std::size_t,
                    property<vertex_distance_t, int,
                    property<vertex_color_t, default_color_type> > >,
                    property<edge_weight_t, int>
                > graph_t;
    typedef graph_traits<graph_t>::vertex_descriptor vertex_t;
    typedef property_map<graph_t, vertex_distance_t>::type
                  vertex_distance_map_t;
    
    typedef pair<int,int> E;
    
    const int num_nodes = 5;
    E         edges[] = {E(0,2), E(1,1), E(1,3), E(1,4),
                         E(2,1), E(2,3), E(3,4), E(4,0)};
    int       W[] = {1, 2, 1, 2, 7, 3, 1, 1};
    graph_t   G(num_nodes,edges,edges + sizeof(edges) / sizeof(E), W);

    property_map<graph_t, vertex_index_t>::type
      index = get(vertex_index, G);

    // Initialize the vertex indices
    graph_traits<graph_t>::vertex_iterator vi, vend;
    graph_traits<graph_t>::vertices_size_type cnt = 0;
    for(tie(vi,vend) = vertices(G); vi != vend; ++vi)
      put(index, *vi, cnt++);

    vertex_t  s = *(vertices(G).first);
    
    dijkstra_shortest_paths(G, s);
    
    cout << "distances from start vertex:" << endl;
    vertex_distance_map_t d = get(vertex_distance, G);
    for(tie(vi,vend) = vertices(G); vi != vend; ++vi)
        cout << "distance(" << get(index, *vi) << ") = " << d[*vi] << endl;
    cout << endl;
    
    return 0;
}