On 15.05.2015 09:11, Ilkka Rajala wrote:
I stumbled on a bit of a performance bottleneck when trying bfs_search on a big graph. The problem is with initialize_vertex function, which is called for every vertex of the graph. Even if the function itself is empty, there's a bunch of work that's done for each vertex in VisitorWrapper.__getattr__, before that empty function is even called.
Indeed. In bfs_search the visitor is a Python class, and hence can be very slow.
What I'm trying to do, is find all vertices reachable from a given root vertex. Graph is undirected and not fully connected. I thought BFS would be a convenient way to do that, but maybe there's a better way to get that information?
BFS is correct, but the bfs_search() function is intended to be used when one wants to do something special with the visitor class to implement some more elaborate algorithm. If you just want to obtain reachability, you can use the shortest_distance() function. Any vertex with a distance larger than N is not reachable... For example: dist = shortest_distance(g, source=g.vertex(10)) u = GraphView(g, vfilt=dist.a < g.num_vertices()) The graph view u contains only the vertices reachable by the source vertex 10. One can also use the label_out_component() function, which is algorithmically equivalent (and maybe even slightly faster): comp = label_out_component(g, g.vertex(10)) u = GraphView(g, vfilt=comp) Both of these approaches should be much faster than bfs_search(). (Note that both these functions use BFS internally, but without Python interference.) Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>