Algorithms to Identify All the Cycle Bases in a UnDirected Graph

Question

I have an undirected graph with Vertex V and Edge E. I am looking for an algorithm to identify all the cycle bases in that graph.

I think Tarjans algorithm is a good start. But the reference I have is about finding all of the cycles, not cycle base ( which, by definition is the cycle that cannot be constructed by union of other cycles).

For example, take a look at the below graph:

So, an algorithm would be helpful. If there is an existing implementation (preferably in C#), it's even better!

Answer 1

From what I can tell, not only is Brian's hunch spot on, but an even stronger proposition holds: each edge that's not in the minimum spanning tree adds exactly one new "base cycle".

To see this, let's see what happens when you add an edge E that's not in the MST. Let's do the favorite math way to complicate things and add some notation ;) Call the original graph G, the graph before adding E G', and the graph after adding E G''. So we need to find out how does the "base cycle count" change from G' to G''.

Adding E must close at least one cycle (otherwise E would be in the MST of G in the first place). So obviously it must add at least one "base cycle" to the already existing ones in G'. But does it add more than one?

It can't add more than two, since no edge can be a member of more than two base cycles. But if E is a member of two base cycles, then the "union" of these two base cycles must've been a base cycle in G', so again we get that the change in the number of cycles is still one.

Ergo, for each edge not in MST you get a new base cycle. So the "count" part is simple. Finding all the edges for each base cycle is a little trickier, but following the reasoning above, I think this could do it (in pseudo-Python):

for v in vertices[G]:
    cycles[v] = []

for e in (edges[G] \ mst[G]):
    cycle_to_split = intersect(cycles[e.node1], cycles[e.node2])
    if cycle_to_split == None:
        # we're adding a completely new cycle
        path = find_path(e.node1, e.node2, mst[G])
        for vertex on path:
            cycles[vertex].append(path + [e]) 
        cycles
    else:
        # we're splitting an existing base cycle
        cycle1, cycle2 = split(cycle_to_split, e)
        for vertex on cycle_to_split:
            cycles[vertex].remove(cycle_to_split)
            if vertex on cycle1:
                cycles[vertex].append(cycle1)
            if vertex on cycle2:
                cycles[vertex].append(cycle2)

base_cycles = set(cycles)

Edit: the code should find all the base cycles in a graph (the base_cycles set at the bottom). The assumptions are that you know how to:

• find the minimum spanning tree of a graph (mst[G])
• find the difference between two lists (edges \ mst[G])
• find an intersection of two lists
• find the path between two vertices on a MST
• split a cycle into two by adding an extra edge to it (the split function)

And it mainly follows the discussion above. For each edge not in the MST, you have two cases: either it brings a completely new base cycle, or it splits an existing one in two. To track which of the two is the case, we track all the base cycles that a vertex is a part of (using the cycles dictionary).

Answer 2

off the top of my head, I would start by looking at any Minimum Spanning Tree algorithm (Prim, Kruskal, etc). There can't be more base cycles (If I understand it correctly) than edges that are NOT in the MST....

Answer 3

The following is my actual untested C# code to find all these "base cycles":

public HashSet<List<EdgeT>> FindBaseCycles(ICollection<VertexT> connectedComponent)
{
   Dictionary<VertexT, HashSet<List<EdgeT>>> cycles =
       new Dictionary<VertexT, HashSet<List<EdgeT>>>();

   // For each vertex, initialize the dictionary with empty sets of lists of
   // edges
   foreach (VertexT vertex in connectedComponent)
       cycles.Add(vertex, new HashSet<List<EdgeT>>());

   HashSet<EdgeT> spanningTree = FindSpanningTree(connectedComponent);

   foreach (EdgeT edgeNotInMST in
           GetIncidentEdges(connectedComponent).Except(spanningTree)) {
       // Find one cycle to split, the HashSet resulted from the intersection
       // operation will contain just one cycle
       HashSet<List<EdgeT>> cycleToSplitSet =
           cycles[(VertexT)edgeNotInMST.StartPoint]
               .Intersect(cycles[(VertexT)edgeNotInMST.EndPoint]);

       if (cycleToSplitSet.Count == 0) {
           // Find the path between the current edge not in ST enpoints using
           // the spanning tree itself
           List<EdgeT> path =
               FindPath(
                   (VertexT)edgeNotInMST.StartPoint,
                   (VertexT)edgeNotInMST.EndPoint,
                   spanningTree);

           // The found path plus the current edge becomes a cycle
           path.Add(edgeNotInMST);

           foreach (VertexT vertexInCycle in VerticesInPathSet(path))
               cycles[vertexInCycle].Add(path);
       } else {
            // Get the cycle to split from the set produced before
            List<EdgeT> cycleToSplit = cycleToSplitSet.GetEnumerator().Current;
            List<EdgeT> cycle1 = new List<EdgeT>();
            List<EdgeT> cycle2 = new List<EdgeT>();
            SplitCycle(cycleToSplit, edgeNotInMST, cycle1, cycle2);

            // Remove the cycle that has been splitted from the vertices in the
            // same cicle and add the results from the split operation to them 
            foreach (VertexT vertex in VerticesInPathSet(cycleToSplit)) {
                cycles[vertex].Remove(cycleToSplit);
                if (VerticesInPathSet(cycle1).Contains(vertex))
                     cycles[vertex].Add(cycle1);
                     if (VerticesInPathSet(cycle2).Contains(vertex))
                         cycles[vertex].Add(cycle2); ;
            }
       }
   }
   HashSet<List<EdgeT>> ret = new HashSet<List<EdgeT>>();
   // Create the set of cycles, in each vertex should be remained only one
   // incident cycle
       foreach (HashSet<List<EdgeT>> remainingCycle in cycles.Values)
           ret.AddAll(remainingCycle);

       return ret;
}

Oggy's code was very good and clear but i'm pretty sure it contains an error, or it's me that don't understand your pseudo python code :)

cycles[v] = []

can't be a vertex indexed dictionary of lists of edges. In my opinion, it have to be a vertex indexed dictionary of sets of lists of edges.

And, to add a precisation:

for vertex on cycle_to_split:

cycle-to-split is probably an ordered list of edges so to iterate it through vertices you have to convert it in a set of vertices. Order here is negligible, so it's a very simple alghoritm.

I repeat, this is untested and uncomplete code, but is a step forward. It still requires a proper graph structure (i use an incidency list) and many graph alghoritms you can find in text books like Cormen. I wasn't able to find FindPath() and SplitCycle() in text books, and are very hard to code them in linear time of number of edges+vertices in the graph. Will report them here when I will test them.

Thanks a lot Oggy!

Answer 4

The standard way to detect a cycle is to use two iterators - for each iteration, one moves forward one step and the other two. Should there be a cycle, they will at some point point to each other.

This approach could be extended to record the cycles so found and move on.