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; nodehttp://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
("<
