[Boost-users] [BGL] premature termination in dijkstra using visitor
Ralf Goertz
I have some very large undirected graphs (half a million vertices).
Edges have weight 0 or 1. For each vertex I need to find all vertices
* that are in sum 2 edges away
* whose distance is 0
Both tasks can be done with breadth-first searches but I don't know in
advance how many edges in depth I have to traverse. That's why I thought
of Dijkstra's algorithm. But in my case this is overkill as I am not
interested in the exact distance of a vertex from a given vertex but
only in if it is not farther than 0 or 2 away. Is it possible to use a
visitor to alter the colormap to mark vertices as final that are too far
even thought they are not final yet?
Ralf
_______________________________________________
Boost-users mailing list
Boost...@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Michael Fawcett
<R_Go...@usenet.arcornews.de> wrote:
> Hi,
>
> I have some very large undirected graphs (half a million vertices).
> Edges have weight 0 or 1. For each vertex I need to find all vertices
>
> * that are in sum 2 edges away
> * whose distance is 0
>
> Both tasks can be done with breadth-first searches but I don't know in
> advance how many edges in depth I have to traverse. That's why I thought
> of Dijkstra's algorithm. But in my case this is overkill as I am not
> interested in the exact distance of a vertex from a given vertex but
> only in if it is not farther than 0 or 2 away. Is it possible to use a
> visitor to alter the colormap to mark vertices as final that are too far
> even thought they are not final yet?
I don't have a suggestion, but I did want to lend weight to your
question since I have exactly the same requirements. I currently use
Dijkstra and accept the overkill, but as my graphs get bigger it's
becoming less acceptable.
--Michael Fawcett
Jeremiah Willcock
> On Fri, Oct 2, 2009 at 9:42 AM, Ralf Goertz
> <R_Go...@usenet.arcornews.de> wrote:
>> Hi,
>>
>> I have some very large undirected graphs (half a million vertices).
>> Edges have weight 0 or 1. For each vertex I need to find all vertices
>>
>> * that are in sum 2 edges away
>> * whose distance is 0
>>
>> Both tasks can be done with breadth-first searches but I don't know in
>> advance how many edges in depth I have to traverse. That's why I thought
>> of Dijkstra's algorithm. But in my case this is overkill as I am not
>> interested in the exact distance of a vertex from a given vertex but
>> only in if it is not farther than 0 or 2 away. Is it possible to use a
>> visitor to alter the colormap to mark vertices as final that are too far
>> even thought they are not final yet?
>
> I don't have a suggestion, but I did want to lend weight to your
> question since I have exactly the same requirements. I currently use
> Dijkstra and accept the overkill, but as my graphs get bigger it's
> becoming less acceptable.
The normal technique for this is to write a visitor that throws an
exception when the distance becomes too large. The task of finding
distance-0 vertices can also be done by BFS with a filtered_graph that
only keeps weight-0 edges; that will automatically stop when all of the
needed vertices are found.
-- Jeremiah Willcock
Michael Fawcett
>> On Fri, Oct 2, 2009 at 9:42 AM, Ralf Goertz
>> <R_Go...@usenet.arcornews.de> wrote:
>>>
>>> Hi,
>>>
>>> I have some very large undirected graphs (half a million vertices).
>>> Edges have weight 0 or 1. For each vertex I need to find all vertices
>>>
>>> * that are in sum 2 edges away
>>> * whose distance is 0
>>>
>>> Both tasks can be done with breadth-first searches but I don't know in
>>> advance how many edges in depth I have to traverse. That's why I thought
>>> of Dijkstra's algorithm. But in my case this is overkill as I am not
>>> interested in the exact distance of a vertex from a given vertex but
>>> only in if it is not farther than 0 or 2 away. Is it possible to use a
>>> visitor to alter the colormap to mark vertices as final that are too far
>>> even thought they are not final yet?
>
> when the distance becomes too large. The task of finding distance-0
> vertices can also be done by BFS with a filtered_graph that only keeps
> weight-0 edges; that will automatically stop when all of the needed vertices
> are found.
Wouldn't throwing an exception when the weight gets too large mean the
search stops at the first vertex when distance > N? The OP wants all
vertices where distance == 2.
Jeremiah Willcock
> On Fri, Oct 2, 2009 at 11:50 AM, Jeremiah Willcock <jewi...@osl.iu.edu> wrote:
>>> On Fri, Oct 2, 2009 at 9:42 AM, Ralf Goertz
>>> <R_Go...@usenet.arcornews.de> wrote:
>>>>
>>>> Hi,
>>>>
>>>> I have some very large undirected graphs (half a million vertices).
>>>> Edges have weight 0 or 1. For each vertex I need to find all vertices
>>>>
>>>> * that are in sum 2 edges away
>>>> * whose distance is 0
>>>>
>>>> Both tasks can be done with breadth-first searches but I don't know in
>>>> advance how many edges in depth I have to traverse. That's why I thought
>>>> of Dijkstra's algorithm. But in my case this is overkill as I am not
>>>> interested in the exact distance of a vertex from a given vertex but
>>>> only in if it is not farther than 0 or 2 away. Is it possible to use a
>>>> visitor to alter the colormap to mark vertices as final that are too far
>>>> even thought they are not final yet?
>>
>> The normal technique for this is to write a visitor that throws an exception
>> when the distance becomes too large. The task of finding distance-0
>> vertices can also be done by BFS with a filtered_graph that only keeps
>> weight-0 edges; that will automatically stop when all of the needed vertices
>> are found.
>
> Wouldn't throwing an exception when the weight gets too large mean the
> search stops at the first vertex when distance > N? The OP wants all
> vertices where distance == 2.
Yes, so stop when the distance is at least 3; vertices are processed in
order of distance.
-- Jeremiah Willcock
Michael Fawcett
Whoops, forgot that Dijkstra uses a priority queue (or similar).
Thanks for the reminder!
Cosimo Calabrese
> Hi,
>
> I have some very large undirected graphs (half a million vertices).
> Edges have weight 0 or 1. For each vertex I need to find all vertices
>
> * that are in sum 2 edges away
> * whose distance is 0
>
> Both tasks can be done with breadth-first searches but I don't know in
> advance how many edges in depth I have to traverse. That's why I thought
> of Dijkstra's algorithm. But in my case this is overkill as I am not
> interested in the exact distance of a vertex from a given vertex but
> only in if it is not farther than 0 or 2 away. Is it possible to use a
> visitor to alter the colormap to mark vertices as final that are too far
> even thought they are not final yet?
>
> Ralf
Hi Ralf,
to write a visitor that throw an exception at the "right moment" is the
official method, I've tried it an it works.
Personally, I don't like very much this way, because I use the
exceptions only when happens special SO condition, like file that
doesn't exists.
I prefer another way: to write a visitor that takes a reference to the
Dijkstra queue. At the right moment, you empty the queue; when you
return from the visitor event, the empty queue naturally terminates the
Dijkstra's algorithm. Sincerely, I've never tried this technique, but if
you want to try it, you can tell us if it works ;)
Best regards,
Cosimo Calabrese.
Ralf Goertz
> Hi,
>
> I have some very large undirected graphs (half a million vertices).
> Edges have weight 0 or 1. For each vertex I need to find all vertices
>
> * that are in sum 2 edges away
> * whose distance is 0
>
> Both tasks can be done with breadth-first searches but I don't know in
> advance how many edges in depth I have to traverse. That's why I
> thought of Dijkstra's algorithm. But in my case this is overkill as I
> am not interested in the exact distance of a vertex from a given vertex
> but only in if it is not farther than 0 or 2 away. Is it possible to
> use a visitor to alter the colormap to mark vertices as final that are
> too far even thought they are not final yet?
>
> Ralf
Thank you for your suggestions. However, I'm afraid I need some more
help. I can't figure out at what event I need to intercept and how I get
the current distance. I must admit that BGL is quite a challenging
library. It seems, generality comes at a high price.
Ralf Goertz
up dijkstra_shortest_paths now runs several orders of magnitudes slower!
I created the visitor according to the bfs_name_printer example in the
BGL User Guide and Reference Book page 11.
-----
class dijkstra_finish : public Exception {
};
template<unsigned maxdist>
class MyVisitor : public default_dijkstra_visitor {
public:
MyVisitor(const vector<unsigned> &d_) : d(d_) {}
template <typename Vertex, typename Graph>
void finish_vertex(Vertex u, Graph g) {
if (d[u]> maxdist) throw dijkstra_finish();
}
private:
const vector<unsigned> &d;
};
struct Distance {
unsigned d;
};
int main() {
vector<unsigned> dists(num_edges(g));
MyVisitor(dists);
try {
dijkstra_shortest_paths(g,source_vertex,weight_map(get(&Distance::d,g)).distance_map(make_iterator_property_map(dists.begin(),get(vertex_index,g))).visitor(vis2));
} catch(const dijkstra_finish&) {}
}
-----
The code seems to do what I want, all dists are either 0,1,2,3 or
numeric_limits<unsigned>::max(). But for a graph with 15000 edges it
takes a few ms to run dijkstra without a visitor but with it it takes 14
seconds. What am I doing wrong?
Andrew Sutton
I managed to create a visitor now, however, instead of speeding things
up dijkstra_shortest_paths now runs several orders of magnitudes slower!
I created the visitor according to the bfs_name_printer example in the
BGL User Guide and Reference Book page 11.
The code seems to do what I want, all dists are either 0,1,2,3 or
numeric_limits<unsigned>::max(). But for a graph with 15000 edges it
takes a few ms to run dijkstra without a visitor but with it it takes 14
seconds. What am I doing wrong?
Are you compiling in debug mode? It can cause dramatic slowdowns with the BGL.
andrew....@gmail.com
Ralf Goertz
No, I use full optimization with g++ version 4.3: "CXXFLAGS=-O3
-Wno-deprecated" is in my Makefile. I also noticed that when I
explicitely use .visitor(default_dijkstra_visitor) or my derived class
without the "void finish_vertex(Vertex u, Graph g)" no harm is done.
In the header files I found the macro BOOST_GRAPH_EVENT_STUB being
applied to the default_bfs_visitor. Do I need to apply it to my derived
class as well?
Andrew Sutton
No, I use full optimization with g++ version 4.3: "CXXFLAGS=-O3> Are you compiling in debug mode? It can cause dramatic slowdowns with
> the BGL.
-Wno-deprecated" is in my Makefile. I also noticed that when I
explicitely use .visitor(default_dijkstra_visitor) or my derived class
without the "void finish_vertex(Vertex u, Graph g)" no harm is done.
In the header files I found the macro BOOST_GRAPH_EVENT_STUB being
applied to the default_bfs_visitor. Do I need to apply it to my derived
class as well?
I see the problem... You're passing your graph by value to the visitor function, meaning you're making a copy of the graph every time you visit a vertex. That should certainly account for the increased time :)
andrew....@gmail.com
Ralf Goertz
Argh, I was so sure that I typed everything correctly. Thanks for
finding the problem.