Re: [Boost-users] Find all the shortest path from a graph

From: Harsh Deshmane (hdeshmane_at_[hidden])
Date: 2005-12-08 13:46:58

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