Re: [Boost-users] Boost Graph Library: Shortest path problem

From: Grégoire Dooms (dooms_at_[hidden])
Date: 2006-04-07 12:04:59

>
> Date: Fri, 07 Apr 2006 11:39:20 +0200
> From: Steven Van Ingelgem <steven.vaningelgem_at_[hidden]>
> Subject: [Boost-users] Boost Graph Library: Shortest path problem
> To: boost-users_at_[hidden]
> Message-ID:
> 	<D3D675A5A7892D4287068E36BAFABB91016EC6DD_at_[hidden]>
> Content-Type: text/plain; charset=us-ascii
>
> Hi,
>
>
>
> I have a problem with using (actually with finding the correct function
> for my problem) the BGL.
>
> What I have is 5000 cities (vertices), 14000 roads (edges) between them
> (directional roads)... And what I want to know is which roads I have to
> take to encounter the least cities on my way.
>   

Simple answer: take no road at all ;-)

> Every edge has a weight of 1... So the documentation points me to using
> the breadth_first_search algorithm.
>
> But this function - as far as I can see - goes through the entire graph.
> I don't see any way to stop it (for example when it has discovered my
> targetcity)??
>   
Sorry about that, I did know you had a target city.

If you want to stop at the target city, the short answer is : use a 
visitor and throw an exception.

void breadth_first_search(const Graph& g,
   typename graph_traits<Graph>::vertex_descriptor s,
   Buffer& Q, BFSVisitor vis, ColorMap color);

The BFSVisitor can be made with the make_bfs_visitor
http://www.boost.org/libs/graph/doc/bfs_visitor.html
pass it an eventlist made of a predecessor_recorder and a custom 
eventprocessor
use
breadth_first_search(g, s, Q,
make_bfs_visitor(make_pair(record_predecessors(predecessor_map, 
on_tree_edge), my_eventvisitor(target_node)), 
colormap)

with

struct my_eventvisitor : public boost::base_visitor<my_eventvisitor>{
        typedef boost::on_finish_vertex event_filter;
        Graph::vertex_descriptor target;
        my_eventvisitor(Graph::vertex_descriptor target): target(target) {}
        template <class Vertex, class Graph>
                void operator()(Vertex v, Graph& g) {
                        if (v==target){
                             throw TargetDiscoveredException;
                }
};

I did not try to compile this but it should be along the lines of what 
you are looking for.

> Is it possible someone can point me where I can have a look at?
> In short I need to calculate (a lot) of roads from different cities to
> other cities (so it's not that I always have the same root vertex).
>
>   
If you have to compute the distance for nearly all pairs of cities, you 
might want to look for one of the all pairs shortest paths.

Hope this helps,
--
Gregoire Dooms