How to perform edge contraction?

classic Classic list List threaded Threaded
2 messages Options
jms
Reply | Threaded
Open this post in threaded view
|

How to perform edge contraction?

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?



--
Sent from: https://nabble.skewed.de/
_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: How to perform edge contraction?

Tiago Peixoto
Administrator
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 <[hidden email]>

_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool

OpenPGP_0x612DEFB798507F25.asc (40K) Download Attachment
OpenPGP_signature (849 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>