Hi Volodya, thanks for this solution [k_shortest.hpp]. It compiles and works for the files given (with minor changes - commenting out the io::<< declaration and some cout statements). However, when I use bundledProps for vectices and edges, I get compilation errors. So, for instance if the graph definition used is the following, instead of the one you have in the example k_shortest_test.cpp, then the compilation fails. struct CCRVertexProps { std::string vertex_name; // name of CCR int tmp; // could be anything }; struct CCREdgeProps { string name; // edgename int edge_weight_t; }; typedef boost::adjacency_list<vecS,vecS,bidirectionalS,CCRVertexProps, CCREdgeProps> myGraph; Do you have any recommendations (other than changing my graph definitions), to make it work with bundledProps ? I tried the simplistic changes recommended from http://www.boost.org/libs/graph/doc/bundles.html (&CCREdgeProps::edge_weight_t in the put() and get() calls), but there are still lots of errors. thanks for any help! -harsh top message of compilation errors is at the end of this mail..
From boost archives:
Hi Giulio,
Hi all,
I'd like to extract all possible shortest path from a source to a destination... not only one path. Please, could you help me to resolve this problem?
Hi, I'm afraid BGL does not have such a algorithm at the moment. One though that comes to me is the use another algorithm (not present in BGL, either), for finding k shortest paths. You'll then be getting next shortest path until the lengths are all the same. There are several algorithms for finding k shortest paths, one being http://citeseer.ist.psu.edu/jimenez94algorithm.html My implementation can be found at http://zigzag.cs.msu.su/~ghost/k_shortest Look specifically at the k_shortest.hpp file. Of course, no warranties. This worked for me and I did test it against independent implementation, but the only way to find it it works for you is to test. - Volodya ------------------------------------------------------------------------------------------------------ ------------------------------------------begin------------------------------------------------------ k_shortest.hpp: In member function `boost::Shortest_paths_finder<G>::Path_set::heap_type* boost::Shortest_paths_finder<G>::initialize_heap(boost::graph_traits<G>::vertex_descriptor) [with G = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, CCRVertexProps, CCREdgeProps, boost::no_property, boost::listS>]': k_shortest.hpp:208: instantiated from `boost::Shortest_paths_finder<G>::Path_set* boost::Shortest_paths_finder<G>::next_path_set(boost::Shortest_paths_finder<G>::Path_s et*) [with G = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, CCRVertexProps, CCREdgeProps, boost::no_property, boost::listS>]' k_shortest.hpp:174: instantiated from `bool boost::Shortest_paths_finder<G>::find_alternative() [with G = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirec tionalS, CCRVertexProps, CCREdgeProps, boost::no_property, boost::listS>]' k_shortest.hpp:321: instantiated from `void boost::k_shortest_f(const G&, boost::graph_traits<G>::vertex_descriptor, boost::graph_traits<G>::vertex_descriptor, int, New PathHandler) [with G = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, CCRVertexProps, CCREdgeProps, boost::no_property, boost::listS>, NewPathHand ler = boost::paths_recorder<main(int, char**)::ccrGraph>]' k_shortest.hpp:352: instantiated from `void boost::k_shortest(const G&, boost::graph_traits<G>::vertex_descriptor, boost::graph_traits<G>::vertex_descriptor, int, std:: vector<std::vector<boost::graph_traits<G>::vertex_descriptor, std::allocator<boost::detail::bfs_helper(VertexListGraph&, boost::graph_traits<G>::vertex_descriptor, ColorM ap, BFSVisitor, const boost::bgl_named_params<P, T, R>&)::Traits::vertex_descriptor> >, std::allocator<std::vector<boost::graph_traits<G>::vertex_descriptor, std::allocat or<boost::detail::bfs_helper(VertexListGraph&, boost::graph_traits<G>::vertex_descriptor, ColorMap, BFSVisitor, const boost::bgl_named_params<P, T, R>&)::Traits::vertex_d escriptor> > > >&) [with G = main(int, char**)::ccrGraph]' k_shortest_test.cpp:287: instantiated from here k_shortest.hpp:191: no match for `int& + boost::detail::error_property_not_found' operator -------------------------------------------end----------------------------------- for reference, line 287: boost::k_shortest(g, *vertices(g).first, *prior(vertices(g).second),100,paths);