Cycle detection in a Multigraph

Question

I would like to list all the cycles in an undirected multigraph.

Tarjan's strongly connected components algorithm was written for a directed graph. Will it work for multigraphs? If not, is there an cycle listing algorithm for undirected multigraphs?

Answer 1

There are a few ways to reduce your problem to Tarjan, depending on how you want to count cycles.

First, apply two transformations to your graph:

1. Convert to a directed graph by replacing each undirected edge with a pair of opposing directed edges.
2. For each pair of nodes, collapse edges pointing the same direction into a single edge.

You'll be left with a directed graph. Apply Tarjan's algorithm.

Now, depending on what you consider a cycle, you may or may not be done. If a cycle is set of nodes (that happen to posses the required edges), then you can read the cycles directly off the transformed graph.

If a cycle is a set of edges (sharing the required nodes), then you need to "uncollapse" the edges introduced in step 2 above. For each collapsed edge, enumerate along the set of real edges it replaced. Doing so for each edge in each collapsed cycle will yield all actual cycles in a combinatorial explosion. Note that this will generate spurious two-cycles which you'll need to prune.

To illustrate, suppose the original graph has three nodes A, B and C, with two edges between A and B, one between B and C and one between A and C. The collapsed graph will be a triangle, with one cycle.

Having found a cycle between the three nodes, walk each combination of edges to recover the full set of cycles. Here, there are two cycles: both include the A to C and B to C edges. They differ in which A to B edge they choose.

If the original graph also had two edges between B and C, then there would be four expanded graphs. The total number of expanded cycles is the product of the edge counts: 4 == 2 * 2 * 1.