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

From: Dmitry Bufistov (dmitry_at_[hidden])
Date: 2006-04-07 09:03:07

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 <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);
> }
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 <boost/config.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/bellman_ford_shortest_paths.hpp>

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[])
{
        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<vertex_descriptor> p(num_vertices(test_graph));
        std::vector<double> d(num_vertices(test_graph));
        vertex_descriptor s = 5;
        boost::property_map<graph_t, vertex_index_t>::type	indexmap(get(vertex_index, test_graph));
        boost::property_map<graph_t, edge_weight_t>::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);
}