Re: [Boost-users] [Graph] New user needs example for shortest-path algorithm

Greg Link wrote:

Boost-Aficionados - I've been trying to incorporate the boost library into my code for longer than I'd like to admit, and I keep getting stonewalled due to my lack of fundamental understanding of much of the 'best practices' and basic types used in boost. In short, I can't quite make it up the initial learning curve. As a first test-example, I've been trying to find the shortest path(s) in a simple 2-dimensional mesh, where each edge has a non-negative weight, which would seem to be a good case for dijkstra_shortest_paths. While I got that to compile, the resulting output wasn't the shortest path, nor the longest. After some trying (and a question on this list) I gave up on that, and tried bellman_ford_shortest_paths, just to see if that wouldn't go better. I'm still having problems, and am hoping that one of the many frequent boost users might be able to help me out with a bit of simple checking and exampling.

I've included a simple test-program below (that doesn't compile) showing what I /think/ things should look like. Obviously, since it's not compiling, I'm horribly wrong. Still, I'm hoping some kind soul is willing to run through it and give me pointers on not only what's wrong, but how to fix it (and/or links to documentation that can help).

Thanks for your time, Greg Link //---------------------------------------------------------------------- ---------- /* * testcase.cpp * speedgraph * * Created by Greg Link on 4/6/06. * Copyright 2006 __MyCompanyName__. All rights reserved. * */

#include <iostream> #include #include #include #include #include <cstdlib> #include <cmath>

using namespace boost;

typedef adjacency_list > graph_t; typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor; typedef graph_traits < graph_t >::edge_descriptor edge_descriptor; typedef std::pair Edge;

int main(int argc, char * argv[]) { int mesh_size = 6; int num_nodes = mesh_size * 2; // eventually to be a 6x6 2- dimensional mesh/grid structure, with undirected edges. //int num_edges = 2*num_nodes - 2*mesh_size; //Every node has a south and and east connection - except the bottom and right sides.

graph_t test_graph(num_nodes); // generate an unconnected graph

//Now to populate the edges of the graph. //iterate over each node, adding southernly and easterly edges for(int x = 0; x<(mesh_size);x++){ // nodes are [0..mesh_size], so we don't need to add easterly edges to nodes where x==mesh_size for(int y = 0; y<(mesh_size);y++){ // see above, and thus don't add southerly edges if y==mesh_size int cur_node_number = x+(y*mesh_size); int easterly_node_number = (x+1)+(y*mesh_size); if(x<(mesh_size-1)){ // add easterly edge double easterlyweight = x + ((x+1)/10); // just a placeholder value, with form (source.destination) for mesh_size < 10. add_edge (cur_node_number,easterly_node_number,easterlyweight,test_graph); } int southernly_node_number = x + ((y+1)*mesh_size); if(y<(mesh_size-1)){ // add southernly edge double southernlyweight = y + ((y+1)/10); // just a placeholder value, with form (source.destination) for mesh_size < 10. add_edge (cur_node_number,southernly_node_number,southernlyweight,test_graph); } } } //finished populated edges of the graph

// initialize the distance map to infinity double maxdouble = (std::numeric_limits <double>::max)(); for(int node = 0; node

//At this point, I provide two non-proper ways of trying to call b_f_s_p, and failing, miserably. // and I can't make the parameters seem to be accepted.

// doesn't work - though http://boost.org/libs/graph/doc/ using_property_maps.html and // http://boost.org/boost/graph/properties.hpp seem to imply this should. /*bool validbf = bellman_ford_shortest_paths(test_graph, num_nodes, weight_map(get(edge_weight,test_graph)). distance_map(get(vertex_distance,test_graph)). predecessor_map(get(vertex_predecessor,test_graph))); */ // doesn't work with 'default' parameters either - I really should initialize distance and source, but I don't know how. //bool validbf = bellman_ford_shortest_paths(test_graph, num_nodes);

std::cout << "Program complete. Bellman-Ford returned ("<

return ((int) validbf); } Hola Greg, Pleas take a look. It works more or less (with 1.33.1 & MSVC8). References: http://boost.org/libs/graph/doc/dijkstra_shortest_paths.html boost_1_33_1\libs\graph\example\dijkstra-example.cpp --dima

//---------------------------------------------------------------------- ---------- /* * testcase.cpp * speedgraph * * Created by Greg Link on 4/6/06. * Copyright 2006 __MyCompanyName__. All rights reserved. * */ #include #include #include #include #include #include using namespace boost; typedef adjacency_list > graph_t; typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor; typedef graph_traits < graph_t >::edge_descriptor edge_descriptor; //typedef std::pair Edge; int main(int argc, char * argv[]) { const int mesh_size = 6; const int num_nodes = mesh_size * 2; // eventually to be a 6x6 2- dimensional mesh/grid structure, with undirected edges. //int num_edges = 2*num_nodes - 2*mesh_size; //Every node has a south and and east connection - except the bottom and right sides. graph_t test_graph; // generate an unconnected graph //Now to populate the edges of the graph. //iterate over each node, adding southernly and easterly edges for(int x = 0; x < mesh_size; ++x) { // nodes are [0..mesh_size], so we don't need to add easterly edges to nodes where x==mesh_size for(int y = 0; y < mesh_size; ++y) { // see above, and thus don't add southerly edges if y==mesh_size int cur_node_number = x + y * mesh_size; int easterly_node_number = (x+1) + (y * mesh_size); if(x < (mesh_size-1)) { // add easterly edge double easterlyweight = x + ((x+1)/10); // just a placeholder value, with form (source.destination) for mesh_size < 10. add_edge (cur_node_number, easterly_node_number,easterlyweight,test_graph); } int southernly_node_number = x + ((y+1)*mesh_size); if(y<(mesh_size-1)){ // add southernly edge double southernlyweight = y + ((y+1)/10); // just a placeholder value, with form (source.destination) for mesh_size < 10. add_edge (cur_node_number, southernly_node_number, southernlyweight, test_graph); } } } //finished populated edges of the graph std::cout << "Num vertices of test_graph is " << num_vertices(test_graph) << std::endl; boost::print_graph(test_graph); boost::print_edges2(test_graph, get(vertex_index, test_graph), get(edge_weight, test_graph)); // initialize the distance map to infinity const double max_double = (std::numeric_limits <double>::max)(); /*for(int node = 0; node < num_nodes; node++) { vertex_descriptor current_node = node; put(get(vertex_distance, test_graph), current_node, max_double); }*/ //and assign a distance of zero to the source node /*int sourcenode_number = 5; // row 1, column 1, I believe. vertex_descriptor sourcenode = sourcenode_number; put(get(vertex_distance,test_graph), sourcenode, 0); */ //At this point, I provide two non-proper ways of trying to call b_f_s_p, and failing, miserably. // and I can't make the parameters seem to be accepted. // doesn't work - though http://boost.org/libs/graph/doc/ using_property_maps.html and // http://boost.org/boost/graph/properties.hpp seem to imply this should. /*bool validbf = bellman_ford_shortest_paths(test_graph, num_nodes, weight_map(get(edge_weight,test_graph)). distance_map(get(vertex_distance,test_graph)). predecessor_map(get(vertex_predecessor,test_graph))); */ // doesn't work with 'default' parameters either - I really should initialize distance and source, but I don't know how. std::vector p(num_vertices(test_graph)); std::vector<double> d(num_vertices(test_graph)); vertex_descriptor s = 5; boost::property_map::type indexmap(get(vertex_index, test_graph)); boost::property_map::type weightmap(get(edge_weight, test_graph)); bool validbf(false); dijkstra_shortest_paths(test_graph, s, &p[0], &d[0], weightmap, indexmap, std::less<double>(), closed_plus<double>(), (std::numeric_limits<double>::max)(), 0, default_dijkstra_visitor()); std::cout << "Shortest pathes from 5 vertex: "; std::copy(d.begin(), d.end(), std::ostream_iterator<double>(std::cout, " ")); return ((int) validbf); }