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

From: Greg Link (link_at_[hidden])
Date: 2006-04-06 14:54:56

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 <boost/config.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/bellman_ford_shortest_paths.hpp>
#include <cstdlib>
#include <cmath>

using namespace boost;

typedef adjacency_list <vecS, vecS, undirectedS, no_property,  
property <edge_weight_t, double> > graph_t;
typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;
typedef std::pair<int, int> 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<num_nodes;node++) {
                vertex_descriptor current_node = node;
                put(get(vertex_distance,test_graph), current_node, maxdouble);
        }
        //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.
        //bool validbf = bellman_ford_shortest_paths(test_graph, num_nodes);
        
        std::cout << "Program complete. Bellman-Ford returned  
("<<validbf<<")." << std::endl;
        
        return ((int) validbf);
}