Finding all cycles in a directed graph

by

I found this page in my search and since cycles are not same as strongly connected components, I kept on searching and finally, I found an efficient algorithm which lists all (elementary) cycles of a directed graph. It is from Donald B. Johnson and the paper can be found in the following link:

http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

A java implementation can be found in:

http://normalisiert.de/code/java/elementaryCycles.zip

A Mathematica demonstration of Johnson’s algorithm can be found here, implementation can be downloaded from the right (“Download author code”).

Note: Actually, there are many algorithms for this problem. Some of them are listed in this article:

http://dx.doi.org/10.1137/0205007

According to the article, Johnson’s algorithm is the fastest one.

More Related Contents:

  1. Algorithm to simplify a weighted directed graph of debts
  2. Best algorithm for detecting cycles in a directed graph [closed]
  3. Graph Algorithm To Find All Connections Between Two Arbitrary Vertices
  4. Find all paths between two graph nodes
  5. Cycles in an Undirected Graph
  6. Why doesn’t Dijkstra’s algorithm work for negative weight edges?
  7. Negative weights using Dijkstra’s Algorithm
  8. Find the shortest path in a graph which visits certain nodes
  9. Compute the minimal number of swaps to order a sequence
  10. Find the paths between two given nodes?
  11. What are the practical factors to consider when choosing between Depth-First Search (DFS) and Breadth-First Search (BFS)? [closed]
  12. Why is the time complexity of both DFS and BFS O( V + E )
  13. What are the differences between segment trees, interval trees, binary indexed trees and range trees?
  14. Why DFS and not BFS for finding cycle in graphs
  15. Why does Dijkstra’s algorithm use decrease-key?
  16. Why is depth-first search claimed to be space efficient?
  17. Number of paths between two nodes in a DAG
  18. What is the problem name for Traveling salesman problem(TSP) without considering going back to starting point?
  19. Explanation of Algorithm for finding articulation points or cut vertices of a graph
  20. Finding connected components of adjacency matrix graph
  21. Calculate the sum with minimum usage of numbers
  22. Priority scoring algorithm [closed]
  23. How to count the number of set bits in a 32-bit integer?
  24. What’s the fastest algorithm for sorting a linked list?
  25. Algorithm to generate a crossword [closed]
  26. Check if one integer is an integer power of another
  27. Find 2 numbers in an unsorted array equal to a given sum
  28. Closest point to a given point
  29. Random points inside a parallelogram
  30. What Are High-Pass and Low-Pass Filters?

Leave a Comment