How does one implement graph algorithms that require efficient contraction and expansion of connected components?

Question

There are some algorithms, like Edmond's Algorithm, or Boruvka's Algorithm which require the programmer to create a graph which is obtained by contraction of some nodes into a single node, and later expanding it back.

A formal description of contraction is as follows:

Let G be a graph with vertices V and edges E. Let C be a connected component of G. A contraction of G with respect to C is defined as the graph on V - nodes(C) + C*, where C* is a "supernode" representing the contracted component. The edges which do not involve vertices in C are as is. The edges which had an endpoint in C are now connected to C*.

It is not clear to me how to implement such algorithmic primitives using representations like adjacency lists.

What would be an elegant and efficient way to represent graphs so that they can be contracted, while remembering the relevant data for expanding them?

Answer 1

I would use disjoint-set data structure also called a union–find data structure . Imagine each vertex as a set initially. Now the working goes like this:

For contraction: Take the union of all the vertices participating in all the contraction. All the vertices in a set are represented by single vertex called parent of all vertices, which you can call your supernode. The link has all the details of how to do that.

For expansion just do the reverse, in the worst case you would have to make each vertex represent a single set. So basically this approach works for non-overlapping set operations.