[graph-tool] Speeding up graph copy?

Tiago de Paula Peixoto tiago at skewed.de
Tue Jan 21 15:01:53 CET 2020


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 at skewed.de>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: OpenPGP digital signature
URL: <https://lists.skewed.de/pipermail/graph-tool/attachments/20200121/4ead384b/attachment-0001.asc>


More information about the graph-tool mailing list