BGL: dijkstra_shortest_paths and adjacency_list<listS, listS, undirectedS>

From: Jan van der Veen (j.van-der-veen_at_[hidden])
Date: 2000-10-06 10:17:06

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.

Thanks,

Jan.

--- 

#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_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);
    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);
    graph_traits<graph_t>::vertex_iterator vi, vend;
    for(tie(vi,vend) = vertices(G); vi != vend; ++vi)
        cout << "distance(" << *vi << ") = " << d[*vi] << endl;
    cout << endl;
    
    return 0;
}