[BGL] premature termination in dijkstra using visitor
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
On Fri, Oct 2, 2009 at 9:42 AM, Ralf Goertz <R_Goertz@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
On Fri, 2 Oct 2009, Michael Fawcett wrote:
On Fri, Oct 2, 2009 at 9:42 AM, Ralf Goertz <R_Goertz@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
On Fri, Oct 2, 2009 at 11:50 AM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Fri, Oct 2, 2009 at 9:42 AM, Ralf Goertz <R_Goertz@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. --Michael Fawcett
On Fri, 2 Oct 2009, Michael Fawcett wrote:
On Fri, Oct 2, 2009 at 11:50 AM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Fri, Oct 2, 2009 at 9:42 AM, Ralf Goertz <R_Goertz@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
On Fri, Oct 2, 2009 at 11:59 AM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Fri, 2 Oct 2009, Michael Fawcett wrote:
On Fri, Oct 2, 2009 at 11:50 AM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Fri, Oct 2, 2009 at 9:42 AM, Ralf Goertz <R_Goertz@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.
Whoops, forgot that Dijkstra uses a priority queue (or similar). Thanks for the reminder! --Michael Fawcett
Ralf Goertz ha scritto:
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 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?
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
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. ----- 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?
On Tue, Oct 6, 2009 at 10:38 AM, Ralf Goertz <R_Goertz@usenet.arcornews.de>wrote:
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 Sutton andrew.n.sutton@gmail.com
Andrew Sutton wrote:
On Tue, Oct 6, 2009 at 10:38 AM, Ralf Goertz <R_Goertz@usenet.arcornews.de>wrote:
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.
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?
Are you compiling in debug mode? It can cause dramatic slowdowns with the BGL.
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?
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 Sutton andrew.n.sutton@gmail.com
Andrew Sutton wrote:
Are you compiling in debug mode? It can cause dramatic slowdowns with the BGL.
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?
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 :)
Argh, I was so sure that I typed everything correctly. Thanks for finding the problem.
participants (5)
-
Andrew Sutton -
Cosimo Calabrese -
Jeremiah Willcock -
Michael Fawcett -
Ralf Goertz