Am 20.01.20 um 19:43 schrieb Zouhair:
Hi,
I'm using graph-tool in my project, and my use case is as follows: 1) build an undirected graph with vertices and edges (~1e5 vtx and ~5e6 edges) 2) attach some properties to the vertices 3) for about ~5000 sets of *new* candidate vertices (each set has about 2-30 vertices) 3.a - add new vertices to graph 3.b - add edges as necessary between new vertices and old ones 3.c - update the properties 3.d - run an algorithm which depends on properties and edges, save result to a list 3.e - remove new vertices from graph and restore properties (i.e. undo 3.a-c)
Steps 1) and 2) are going well. For step 3), the algorithm in step 3.d runs fast, 3.b and 3.c are also fast, however, the bottleneck I'm facing is 3.a and 3.e (about 80% of runtime is spent there)
How are you doing steps 3.a and 3.e exactly? Are you calling g.add_vertex() and g.remove_vertex() repeatedly?
iii- use GraphView but only filter on the original vertices in the graph: this avoids having to delete the vertices, but making GraphView with a filter function is still slow (doing `gt.GraphView(g, lambda v: v < n_nodes_orig)` takes 75% of runtime, and the number of vertices in the original graph keeps growing...
This can be improved by passing a boolean-valued vertex property map instead of a lambda function. In this way the GraphView creation becomes O(1) instead of O(N). Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>