Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Algorithms to Identify All the Cycle Bases in a UnDirected Graph

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!

like image 685
Graviton Avatar asked Oct 22 '09 13:10

Graviton


People also ask

Which of the algorithms can be used to detect cycles in a graph?

Depth First Traversal can be used to detect a cycle in a Graph. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is indirectly joining a node to itself (self-loop) or one of its ancestors in the tree produced by DFS.

How will you identify a cycle in an undirected graph?

To detect if there is any cycle in the undirected graph or not, we will use the DFS traversal for the given graph. For every visited vertex v, when we have found any adjacent vertex u, such that u is already visited, and u is not the parent of vertex v. Then one cycle is detected.

Which algorithm is used for undirected graph?

We can use a traversal algorithm, either depth-first or breadth-first, to find the connected components of an undirected graph.

Can BFS and DFS detect cycle?

Like directed graphs, we can use DFS to detect a cycle in an undirected graph in O(V+E) time. We have discussed DFS based solution for cycle detection in an undirected graph. In this article, the BFS based solution is discussed. We do a BFS traversal of the given graph.


2 Answers

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

like image 144
oggy Avatar answered Oct 16 '22 02:10

oggy


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

like image 44
Brian Postow Avatar answered Oct 16 '22 02:10

Brian Postow