How to perform edge contraction?

graph-tool
1

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?

2

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