On Fri, 2 Oct 2009, Michael Fawcett wrote:

On Fri, Oct 2, 2009 at 9:42 AM, 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?

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, 2 Oct 2009, Michael Fawcett wrote:

On Fri, Oct 2, 2009 at 11:50 AM, Jeremiah Willcock wrote:

...

...

On Fri, Oct 2, 2009 at 9:42 AM, 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?

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

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 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 wrote:

On Tue, Oct 6, 2009 at 10:38 AM, Ralf Goertz 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?

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.