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); }

On Apr 10, 2006, at 11:03 AM, Greg Link wrote:

Boost-List - About a week ago, I wrote to the list, asking for some basic assistance getting the boost Graph library utilized in a short sample program. One of the list members (Dmitry Bufistov) was kind enough to show me the problem areas in my sample program, and now I've got everything working quite nicely. My question, then is this: Would it be a 'good' thing to try to append the 93-line sample program I posted (now working properly) to the documentation regarding the boost Graph library? Given that the current dijkstra_shortest_paths example doesn't show instantiation of a non-constant path, nor does it show accessing said graph, would a more 'user friendly' example help others in the future?

Absolutely!

In general, my only problems with the boost libraries so far have been documentation related, so I'm eager to see future users have better access to information. What's the consensus regarding such 'user-friendly' examples, and how would I go about getting something added to the documentation if such examples are considered a 'good' thing?

If you could submit a patch to the documentation, someone (for the BGL, it would be me) will review the patch and put it in Boost CVS for an upcoming release. Users like yourself are the best people to write this kind of documentation, because you know where we made the mistakes in the current documentation. Those of us that have been writing BGL algorithms for years see things very differently. Doug