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 <[email protected]>
signature.asc
Description: OpenPGP digital signature
_______________________________________________ graph-tool mailing list [email protected] https://lists.skewed.de/mailman/listinfo/graph-tool
