Re: [Boost-users] Dijkstra Shortest path problem

Subject: Re: [Boost-users] Dijkstra Shortest path problem
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-03-16 01:45:41

On Tue, 16 Mar 2010, Kya Bey wrote:

> Hi all, 
> I'm trying to get Dijkstra's shortest path algorithm to work with my graph which has some bundled edge properties with weight as an
> attribute in the bundle
> 
> struct edge_properties
> {
>     int         capacity ; 
>     double      weight ;
> };
> 
> typedef boost::adjacency_list<listS, vecS, bidirectionalS, //directedS, 
>                               property<vertex_name_t, std::string>,
>                               edge_properties> Graph;
> 
> 
> I read in the graph using the graph viz library and that works fine. (tested by printing the graph info)
> 
>     dynamic_properties                        dp;
> 
>     dp.property("weight", get(&edge_properties::weight, g));
>     dp.property("capacity", get(&edge_properties::capacity, g));
>     read_graphviz(in, g,dp , "name") ;
> 
> I'm constantly seeing compiler errors when i use something from dijkstra-example.cpp. 
> 
>     // Dijkstra SRC is set to 1. 
>     vertex_descriptor src = vertex(1, g);
>     // Just as in the example
>     std::vector<vertex_descriptor> p(num_vertices(g));
>     std::vector<double> d(num_vertices(g));
> 
>     //RESULTS in compiler errors. See below. 
>     dijkstra_shortest_paths( g, src,
>                              predecessor_map(&p[0]).distance_map(&d[0]) ) ;

You are missing the weight map, which is a required argument to 
dijkstra_shortest_paths.  The graph in dijkstra-example.cpp has a built-in 
weight map (using old-style properties); the default method for finding 
weight maps does not find bundled properties named "weight".

>     //USING This call works. But have no way to get the predecessor/distance info
>     // This fails if ***Graph*** is defined as listS,listS  but works if Graph is defined as listS,vecS or vecS,vecS
>     dijkstra_shortest_paths( g, src,
>                              weight_map(get(&edge_properties::weight,network.g)) );

The reason that this fails with listS,listS is that the default distance 
map requires that the graph have a vertex index map; graphs with vecS as 
the vertex container have one built in, but graphs with listS require the 
user to define (and fill) one manually.

-- Jeremiah Willcock