Boost Graph Library: Shortest path problem

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Boost Graph Library: Shortest path problem

Steven Van Ingelgem
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.

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


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



Thanks for any suggestion!
Steven Van Ingelgem
_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: Boost Graph Library: Shortest path problem

Johan Oudinet
On 4/7/06, Steven Van Ingelgem <[hidden email]> wrote:

> 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.
>
> 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)??
>
>
> Is it possible someone can point me where I can have a look at?

Yes, just throw an exception with a bfs visitor when it has discovered
your target city. Look at in archive of this mailing list, their are
some examples how to do that.

Regards,

--
Johan
_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: Boost Graph Library: Shortest path problem

Grégoire Dooms
In reply to this post by Steven Van Ingelgem
>
> Date: Fri, 07 Apr 2006 11:39:20 +0200
> From: Steven Van Ingelgem <[hidden email]>
> Subject: [Boost-users] Boost Graph Library: Shortest path problem
> To: [hidden email]
> Message-ID:
> <[hidden email]>
> 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


_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users