[graph-tool] How to perform edge contraction?

Tiago de Paula Peixoto tiago at skewed.de
Mon Nov 30 12:18:06 CET 2020


Am 21.11.20 um 02:25 schrieb jms:
> Hi, I came across this library looking for an efficiently implemented graph
> library and it looks awesome. One of the tasks I'd like to perform is
> efficient edge contraction, where I remove an edge from the graph and merge
> the two nodes joined by that edge, and then merge all the incident edges to
> those nodes.
> 
> I'd like to do this "dynamically", where I may iterate through a list of
> edges and selectively collapse some of them (skipping ones which have
> already been merged).
> 
> Any suggestions on how to perform this with graph-tools?

You can achieve this by using the condensation_graph() function:

https://graph-tool.skewed.de/static/doc/generation.html#graph_tool.generation.condensation_graph

You need only to mark the vertices that need to be merged with the same 
property map value.

Best,
Tiago

-- 
Tiago de Paula Peixoto <tiago at skewed.de>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: OpenPGP_0x612DEFB798507F25.asc
Type: application/pgp-keys
Size: 38960 bytes
Desc: not available
URL: <https://lists.skewed.de/pipermail/graph-tool/attachments/20201130/843fd100/attachment-0001.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: OpenPGP_signature
Type: application/pgp-signature
Size: 833 bytes
Desc: OpenPGP digital signature
URL: <https://lists.skewed.de/pipermail/graph-tool/attachments/20201130/843fd100/attachment-0001.sig>


More information about the graph-tool mailing list