Hi, 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.
Just doing: g = Graph() g.add_vertex(10000000) %timeit bfs_search(g, 0, BFSVisitor()) 1 loops, best of 3: 37.6 s per loop Now I have a graph with 350M vertices and some 550M edges. It takes 21 minutes of initialize_vertex calls that I don't need, before doing a few millisecond search :-/ Seems like my only option is to compile a custom version, with initialize_vertex disabled from all search functions, or implement BFS myself in python. Hopefully I'm doing something terribly wrong? 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? I'm not very familiar with graphs :-) - Ilkka _______________________________________________ graph-tool mailing list [email protected] http://lists.skewed.de/mailman/listinfo/graph-tool
