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!

Readymix

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).

Eduardo

Sorry for my ignorance, but your code is? An implementation to find the cycle basis for non-spanning tree edges? – Readymix

non-spanning tree edges= edges that are not in minimum spanning tree – Readymix

Also, note that your one half of your code is a duplicate of another half – Readymix

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....

Kingkingbird

I read the minimum spanning tree algorithm (en.wikipedia.org/wiki/Minimum_spanning_tree) and feel like my head is spinning.. you have an online demo that shows how MST works? – Readymix

any intro algorithms text (CLR[S] is of course standard) should have a good discussion of several algorithms. I'm surprsied that the MST discussion on Wikipedia doesn't point to either Prim's or Kruskal's (en.wikipedia.org/wiki/Kruskal%27s_algorithm) algorithms... I like Kruskal, but that could be because I know his nephew B-) – Kingkingbird

Can you please recommend any algorithm text that gives a good explanation on this topic? – Ante

@david.healed: he just did :) CLR refers to "Introduction to algorithms" by Cormen, Leiserson and Rivest (S is Stein from the 2nd ed). – Eduardo

What oggy said. Sorry, I guess I assumed that everyone know what CLRS (nee CLR) is... CLR is also known as "The Big White Book" even though CLRS is now mostly green, it's still TBWB... – Kingkingbird

I thought CLR = Common Language Runtime :-) Now I know what to look for. Thanks everyone! – Ante

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!

Lida

Forgot: HashSet I've used here is not .NET 3.5 compliant as I had to add it myself (the project is still .NET 2.0), so for example it has AddAll() method. This sounds very java like, ahahahah :D – Lida

Can you please post code for FindSpanningTree, GetIncidentEdges and AddAll? Thanks :) – Hayrack

What are incident edges? I've googled but no result. – Hayrack

How do I implement SplitCycle and VerticesInPathSet? – Hayrack

Edza, FindSpanningTree() is Kruskal algorithm simplified for undirected graphs. If you need an implementation I recommend you to open your favourite algorithms book (or look at this) and observe the simplification where all edges have the same weight, so the order is negligible. "Incident edges" is not something to be googled for, it's just base graph theory semantics: edges incident on a vertex. GetIncidentEdges, AddAll and SplitCycle are trivial, you should implement them yourself as well if you need. – Lida

Also, as mentioned above, I don't remember if this code had been eventually properly tested, so check it twice. – Lida

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.

Wojcik

How does it identify the cycle base? – Readymix