>

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