Menu
I'm looking for an algorithm that given a graph it returns all the minimal cycles in it.
To make clear what I want, I need the algorithm to return exactly the following cycles from this graph:
(1,3,6,1), (1,6,4,1), (1,4,2,1), (6,4,7,6), (2,4,7,2), (2,7,5,2) 
I've been searching alot and I still can't figure out even the name of this problem. Is it the cycle basis problem or the fundamental cycles problem or are those two the same?
I found solutions involving MST or All-Pairs Shortest Paths but I can't understand any of them.
I tried to implement Horton's algorithm which I found here: Horton's Algorithm but I got stuck at the 4th step in page 5 trying to actually find out the cycles.
Can somebody either explain to me what exactly needs to be done in step 4 of Horton's algorithm or give me another algorithm to solve my problem?
412
The idea is to use shortest path algorithm. We one by one remove every edge from the graph, then we find the shortest path between two corner vertices of it. We add an edge back before we process the next edge.
Approach: Depth First Traversal can be used to detect a cycle in a Graph. DFS for a connected graph produces a tree. 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 from a node to itself (self-loop) or one of its ancestors in the tree produced by DFS.
Here for finding the number of cycles in the undirected graph, the time complexity is the same as DFS traversal, i.e., O(V+E), where V is the number of vertices and E is the number of edges in the graph.
BFS wont work for a directed graph in finding cycles. Consider A->B and A->C->B as paths from A to B in a graph. BFS will say that after going along one of the path that B is visited.
This paper describes algorithm used in geometric tools library (written ic C++ i think). It's basically a modified DFS algorithm with addition of some algebra. The pseudocode is to big to post it here, so here is the link:
http://www.geometrictools.com/Documentation/MinimalCycleBasis.pdf
I'm currently working on javascript implementation. If you're interested you can view it here:
http://jsbin.com/igujuz/8/edit
112
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
