How can I find (iterate over) ALL the cycles in a directed graph from/to a given node?

For example, I want something like this:

```
A->B->A
A->B->C->A
```

but not: B->C->B

Start at node X and check for all child nodes (parent and child nodes are equivalent if undirected). Mark those child nodes as being children of X. From any such child node A, mark it's children of being children of A, X', where X' is marked as being 2 steps away.). If you later hit X and mark it as being a child of X'', that means X is in a 3 node cycle. Backtracking to it's parent is easy (as-is, the algorithm has no support for this so you'd find whichever parent has X').

Note: If graph is undirected or has any bidirectional edges, this algorithm gets more complicated, assuming you don't want to traverse the same edge twice for a cycle.

I was given this as an interview question once, I suspect this has happened to you and you are coming here for help. Break the problem into three questions and it becomes easier.

- how do you determine the next valid route
- how do you determine if a point has been used
- how do you avoid crossing over the same point again

Problem 1) Use the iterator pattern to provide a way of iterating route results. A good place to put the logic to get the next route is probably the "moveNext" of your iterator. To find a valid route, it depends on your data structure. For me it was a sql table full of valid route possibilities so I had to build a query to get the valid destinations given a source.

Problem 2) Push each node as you find them into a collection as you get them, this means that you can see if you are "doubling back" over a point very easily by interrogating the collection you are building on the fly.

Problem 3) If at any point you see you are doubling back, you can pop things off the collection and "back up". Then from that point try to "move forward" again.

Hack: if you are using Sql Server 2008 there is are some new "hierarchy" things you can use to quickly solve this if you structure your data in a tree.

The easiest answer to this problem is probably:

Do a Depth-First Search from A. When you visit a node which has a path to A, you have got your cycle.

(If you are not in a directed graph.)

Depth first search with backtracking should work here. Keep an array of boolean values to keep track of whether you visited a node before. If you run out of new nodes to go to (without hitting a node you have already been), then just backtrack and try a different branch.

The DFS is easy to implement if you have an adjacency list to represent the graph. For example adj[A] = {B,C} indicates that B and C are the children of A.

For example, pseudo-code below. "start" is the node you start from.

```
dfs(adj,node,visited):
if (visited[node]):
if (node == start):
"found a path"
return;
visited[node]=YES;
for child in adj[node]:
dfs(adj,child,visited)
visited[node]=NO;
```

Call the above function with the start node:

```
visited = {}
dfs(adj,start,visited)
```

As far as I know, the best way to solve this would be with Tarjans(or Gabows or Kosaraju's --see Wikipedia link below) algorithm for finding strongly connected components of a graph. Strongly connected components and cycles are synonymous (but not exactly the same).

To get a better idea, please see the following links:

Wikipedia on Tarjans algorithm: http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

A rigorous explanation: http://www.ics.uci.edu/~eppstein/161/960220.html

Other interesting links:

http://discuss.joelonsoftware.com/default.asp?design.4.249152.10

http://forums.sun.com/thread.jspa?threadID=597673

http://coding.derkeiler.com/Archive/General/comp.theory/2004-02/0468.htmlSimilar question on SO: Best algorithm for detecting cycles in a directed graph

Now, that I've given the links, let me proceed to explain (after all its good answers and not links that really make stackoverflow such a great place).

**Some points to remember** (Taken from link 1):

1.Two vertices, A and B, are strongly connected if there's a path from A to B and a path from B to A.

2.The set of all vertices that are strongly connected to a given vertex forms a strongly connected component of the graph.

3.Any strongly connected component with more than one vertex in it contains at least one cycle, except components with a self-loop. (Thanks for the help Jens Schauder, bcorso)

4.We want to somehow collapse all the vertices in a cycle into a single node in a 'tree' (See links). Any future cycle involving vertices we've already visited gets folded into the same node. What we end up with is a tree where each node is a strongly connected component.

5.To do this is to store two extra bits of information on each node. The number of steps the depth-first search takes to reach that node and the minimum number of steps the depth-first search takes to reach any node in that node's strongly connected component (from the nodes we've seen so far).

6.As we perform a depth-first search on the main graph, we use the secondary data structure to help us test whether two nodes are "the same" (in the same strongly connected component, as it turns out) and add the current node to that secondary structure correctly.

**Algorithm**

The question you have isn't trivial to solve. Here's how Tarjans algorithm works-

1.The first thing to know is that you have to do a DFS. I am assuming that a stack is used to implement it. The DFS has to cover ** all** vertices in the graph.

2.Each vertex v, has to be labeled with two values, the index and the lowval. The index is simply the order in which DFS visits the node. The lowval is the minimum of the v's index and the index of the vertex that is nearest to v in the DFS. This vertex is then pushed onto the stack.

3.For each vertex accessible from v, recurse if it isn't already in the stack.

4.For a vertex v, whose lowval == index, pop off all elements on the stack upto v itself and print them as one strongly connected component (cycle).

I am going to try and implement this algorithm. I'll post it here if I succeed and if you want it at that time.

**Edit**

This question is still puzzling me - This algorithm is linear in V+E. However, the number of cycles may be exponential in V. I am quite puzzled as to how this can be possible? I haven't been able to figure it out myself.

See this link: http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf given by ShuggyCoUk and unknown(yahoo) for more details about the no. of cycles.

can't you make a little recursive function to traverse the nodes?

```
readDiGraph( string pathSoFar, Node x)
{
if(NoChildren) MasterList.add( pathsofar + Node.name ) ;
foreach( child )
{
readDiGraph( pathsofar + "->" + this.name, child)
}
}
```

if you have a ton of nodes you will run out of stack

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://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.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.

I stumbled over the following algorithm which seems to be more efficient than Johnson's algorithm (at least for larger graphs). I am however not sure about its performance compared to Tarjan's algorithm.

Additionally, I only checked it out for triangles so far. If interested, please see "Arboricity and Subgraph Listing Algorithms" by Norishige Chiba and Takao Nishizeki (http://dx.doi.org/10.1137/0214017)

If what you want is to find all elementary circuits in a graph you can use the EC algorithm, by JAMES C. TIERNAN, found on a paper since 1970.

The **very original** EC algorithm as I managed to implement it in php (hope there are no mistakes is shown below). It can find loops too if there are any. The circuits in this implementation (that tries to clone the original) are the non zero elements. Zero here stands for non-existence (null as we know it).

Apart from that below follows an other implementation that gives the algorithm more independece, this means the nodes can start from anywhere even from negative numbers, e.g -4,-3,-2,.. etc.

In both cases it is required that the nodes are sequential.

You might need to study the original paper, James C. Tiernan Elementary Circuit Algorithm

```
<?php
echo "<pre><br><br>";
$G = array(
1=>array(1,2,3),
2=>array(1,2,3),
3=>array(1,2,3)
);
define('N',key(array_slice($G, -1, 1, true)));
$P = array(1=>0,2=>0,3=>0,4=>0,5=>0);
$H = array(1=>$P, 2=>$P, 3=>$P, 4=>$P, 5=>$P );
$k = 1;
$P[$k] = key($G);
$Circ = array();
#[Path Extension]
EC2_Path_Extension:
foreach($G[$P[$k]] as $j => $child ){
if( $child>$P[1] and in_array($child, $P)===false and in_array($child, $H[$P[$k]])===false ){
$k++;
$P[$k] = $child;
goto EC2_Path_Extension;
} }
#[EC3 Circuit Confirmation]
if( in_array($P[1], $G[$P[$k]])===true ){//if PATH[1] is not child of PATH[current] then don't have a cycle
$Circ[] = $P;
}
#[EC4 Vertex Closure]
if($k===1){
goto EC5_Advance_Initial_Vertex;
}
//afou den ksana theoreitai einai asfales na svisoume
for( $m=1; $m<=N; $m++){//H[P[k], m] <- O, m = 1, 2, . . . , N
if( $H[$P[$k-1]][$m]===0 ){
$H[$P[$k-1]][$m]=$P[$k];
break(1);
}
}
for( $m=1; $m<=N; $m++ ){//H[P[k], m] <- O, m = 1, 2, . . . , N
$H[$P[$k]][$m]=0;
}
$P[$k]=0;
$k--;
goto EC2_Path_Extension;
#[EC5 Advance Initial Vertex]
EC5_Advance_Initial_Vertex:
if($P[1] === N){
goto EC6_Terminate;
}
$P[1]++;
$k=1;
$H=array(
1=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
2=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
3=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
4=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
5=>array(1=>0,2=>0,3=>0,4=>0,5=>0)
);
goto EC2_Path_Extension;
#[EC5 Advance Initial Vertex]
EC6_Terminate:
print_r($Circ);
?>
```

then this is the other implementation, more independent of the graph, without goto and without array values, instead it uses array keys, the path, the graph and circuits are stored as array keys (use array values if you like, just change the required lines). The example graph start from -4 to show its independence.

```
<?php
$G = array(
-4=>array(-4=>true,-3=>true,-2=>true),
-3=>array(-4=>true,-3=>true,-2=>true),
-2=>array(-4=>true,-3=>true,-2=>true)
);
$C = array();
EC($G,$C);
echo "<pre>";
print_r($C);
function EC($G, &$C){
$CNST_not_closed = false; // this flag indicates no closure
$CNST_closed = true; // this flag indicates closure
// define the state where there is no closures for some node
$tmp_first_node = key($G); // first node = first key
$tmp_last_node = $tmp_first_node-1+count($G); // last node = last key
$CNST_closure_reset = array();
for($k=$tmp_first_node; $k<=$tmp_last_node; $k++){
$CNST_closure_reset[$k] = $CNST_not_closed;
}
// define the state where there is no closure for all nodes
for($k=$tmp_first_node; $k<=$tmp_last_node; $k++){
$H[$k] = $CNST_closure_reset; // Key in the closure arrays represent nodes
}
unset($tmp_first_node);
unset($tmp_last_node);
# Start algorithm
foreach($G as $init_node => $children){#[Jump to initial node set]
#[Initial Node Set]
$P = array(); // declare at starup, remove the old $init_node from path on loop
$P[$init_node]=true; // the first key in P is always the new initial node
$k=$init_node; // update the current node
// On loop H[old_init_node] is not cleared cause is never checked again
do{#Path 1,3,7,4 jump here to extend father 7
do{#Path from 1,3,8,5 became 2,4,8,5,6 jump here to extend child 6
$new_expansion = false;
foreach( $G[$k] as $child => $foo ){#Consider each child of 7 or 6
if( $child>$init_node and isset($P[$child])===false and $H[$k][$child]===$CNST_not_closed ){
$P[$child]=true; // add this child to the path
$k = $child; // update the current node
$new_expansion=true;// set the flag for expanding the child of k
break(1); // we are done, one child at a time
} } }while(($new_expansion===true));// Do while a new child has been added to the path
# If the first node is child of the last we have a circuit
if( isset($G[$k][$init_node])===true ){
$C[] = $P; // Leaving this out of closure will catch loops to
}
# Closure
if($k>$init_node){ //if k>init_node then alwaya count(P)>1, so proceed to closure
$new_expansion=true; // $new_expansion is never true, set true to expand father of k
unset($P[$k]); // remove k from path
end($P); $k_father = key($P); // get father of k
$H[$k_father][$k]=$CNST_closed; // mark k as closed
$H[$k] = $CNST_closure_reset; // reset k closure
$k = $k_father; // update k
} } while($new_expansion===true);//if we don't wnter the if block m has the old k$k_father_old = $k;
// Advance Initial Vertex Context
}//foreach initial
}//function
?>
```

I have analized and documented the EC but unfortunately the documentation is in Greek.

First of all - you do not really want to try find literally all cycles because if there is 1 then there is an infinite number of those. For example A-B-A, A-B-A-B-A etc. Or it may be possible to join together 2 cycles into an 8-like cycle etc., etc... The meaningful approach is to look for all so called simple cycles - those that do not cross themselves except in the start/end point. Then if you wish you can generate combinations of simple cycles.

One of the baseline algorithms for finding all simple cycles in a directed graph is this: Do a depth-first traversal of all simple paths (those that do not cross themselves) in the graph. Every time when the current node has a successor on the stack a simple cycle is discovered. It consists of the elements on the stack starting with the identified successor and ending with the top of the stack. Depth first traversal of all simple paths is similar to depth first search but you do not mark/record visited nodes other than those currently on the stack as stop points.

The brute force algorithm above is terribly inefficient and in addition to that generates multiple copies of the cycles. It is however the starting point of multiple practical algorithms which apply various enhancements in order to improve performance and avoid cycle duplication. I was surprised to find out some time ago that these algorithms are not readily available in textbooks and on the web. So I did some research and implemented 4 such algorithms and 1 algorithm for cycles in undirected graphs in an open source Java library here : http://code.google.com/p/niographs/ .

BTW, since I mentioned undirected graphs : The algorithm for those is different. Build a spanning tree and then every edge which is not part of the tree forms a simple cycle together with some edges in the tree. The cycles found this way form a so called cycle base. All simple cycles can then be found by combining 2 or more distinct base cycles. For more details see e.g. this : http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf .

There are two steps (algorithms) involved in finding all cycles in DAG.

The first step is to use Tarjan's algorithm to find set of strongly connected components.

- Start from any arbitrary vertex.
- DFS from that vertex. For each node x, keep two numbers, dfs_index[x] and dfs_lowval[x]. dfs_index[x] stores when that node is visited, while dfs_lowval[x] = min( dfs_low[k]) where k is all the children of x that is not the directly parent of x in the dfs-spanning tree.
- All nodes with the same dfs_lowval[x] are in the same strongly connected component.

The second step is find cycles (paths) within the connected components. My suggestion is to use modified Hierholzer's algorithm.

The idea is:

- Choose any starting vertex v, and follow a trail of edges from that vertex until returning to v. It is not possible to get stuck at any vertex other than v, because the even degree of all vertices ensures that, when the trail enters another vertex w there must be an unused edge leaving w. The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.
- As long as there exists a vertex v that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from v, following unused edges until returning to v, and join the tour formed in this way to the previous tour.

Here is the link for the Java implementation with a test case:

http://stones333.blogspot.com/2013/12/find-cycles-in-directed-graph-dag.html

In the case of **undirected** graph, a paper recently published (*Optimal listing of cycles and st-paths in undirected graphs*) offers an asymptotically optimal solution. You can read it here http://arxiv.org/abs/1205.2766 or here http://dl.acm.org/citation.cfm?id=2627951 I know it doesn't answer your question, but since the title of your question doesn't mention direction, it might still be useful for Google search

Javascript solution using disjoint set linked lists. Can be upgraded to disjoint set forests for faster run times.

```
var input = '5\nYYNNN\nYYYNN\nNYYNN\nNNNYN\nNNNNY'
console.log(input);
//above solution should be 3 because the components are
//{0,1,2}, because {0,1} and {1,2} therefore {0,1,2}
//{3}
//{4}
//MIT license, authored by Ling Qing Meng
//'4\nYYNN\nYYYN\nNYYN\nNNNY'
//Read Input, preformatting
var reformat = input.split(/\n/);
var N = reformat[0];
var adjMatrix = [];
for (var i = 1; i < reformat.length; i++) {
adjMatrix.push(reformat[i]);
}
//for (each person x from 1 to N) CREATE-SET(x)
var sets = [];
for (var i = 0; i < N; i++) {
var s = new LinkedList();
s.add(i);
sets.push(s);
}
//populate friend potentials using combinatorics, then filters
var people = [];
var friends = [];
for (var i = 0; i < N; i++) {
people.push(i);
}
var potentialFriends = k_combinations(people,2);
for (var i = 0; i < potentialFriends.length; i++){
if (isFriend(adjMatrix,potentialFriends[i]) === 'Y'){
friends.push(potentialFriends[i]);
}
}
//for (each pair of friends (x y) ) if (FIND-SET(x) != FIND-SET(y)) MERGE-SETS(x, y)
for (var i = 0; i < friends.length; i++) {
var x = friends[i][0];
var y = friends[i][1];
if (FindSet(x) != FindSet(y)) {
sets.push(MergeSet(x,y));
}
}
for (var i = 0; i < sets.length; i++) {
//sets[i].traverse();
}
console.log('How many distinct connected components?',sets.length);
//Linked List data structures neccesary for above to work
function Node(){
this.data = null;
this.next = null;
}
function LinkedList(){
this.head = null;
this.tail = null;
this.size = 0;
// Add node to the end
this.add = function(data){
var node = new Node();
node.data = data;
if (this.head == null){
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
this.size++;
};
this.contains = function(data) {
if (this.head.data === data)
return this;
var next = this.head.next;
while (next !== null) {
if (next.data === data) {
return this;
}
next = next.next;
}
return null;
};
this.traverse = function() {
var current = this.head;
var toPrint = '';
while (current !== null) {
//callback.call(this, current); put callback as an argument to top function
toPrint += current.data.toString() + ' ';
current = current.next;
}
console.log('list data: ',toPrint);
}
this.merge = function(list) {
var current = this.head;
var next = current.next;
while (next !== null) {
current = next;
next = next.next;
}
current.next = list.head;
this.size += list.size;
return this;
};
this.reverse = function() {
if (this.head == null)
return;
if (this.head.next == null)
return;
var currentNode = this.head;
var nextNode = this.head.next;
var prevNode = this.head;
this.head.next = null;
while (nextNode != null) {
currentNode = nextNode;
nextNode = currentNode.next;
currentNode.next = prevNode;
prevNode = currentNode;
}
this.head = currentNode;
return this;
}
}
/**
* GENERAL HELPER FUNCTIONS
*/
function FindSet(x) {
for (var i = 0; i < sets.length; i++){
if (sets[i].contains(x) != null) {
return sets[i].contains(x);
}
}
return null;
}
function MergeSet(x,y) {
var listA,listB;
for (var i = 0; i < sets.length; i++){
if (sets[i].contains(x) != null) {
listA = sets[i].contains(x);
sets.splice(i,1);
}
}
for (var i = 0; i < sets.length; i++) {
if (sets[i].contains(y) != null) {
listB = sets[i].contains(y);
sets.splice(i,1);
}
}
var res = MergeLists(listA,listB);
return res;
}
function MergeLists(listA, listB) {
var listC = new LinkedList();
listA.merge(listB);
listC = listA;
return listC;
}
//access matrix by i,j -> returns 'Y' or 'N'
function isFriend(matrix, pair){
return matrix[pair[0]].charAt(pair[1]);
}
function k_combinations(set, k) {
var i, j, combs, head, tailcombs;
if (k > set.length || k <= 0) {
return [];
}
if (k == set.length) {
return [set];
}
if (k == 1) {
combs = [];
for (i = 0; i < set.length; i++) {
combs.push([set[i]]);
}
return combs;
}
// Assert {1 < k < set.length}
combs = [];
for (i = 0; i < set.length - k + 1; i++) {
head = set.slice(i, i+1);
tailcombs = k_combinations(set.slice(i + 1), k - 1);
for (j = 0; j < tailcombs.length; j++) {
combs.push(head.concat(tailcombs[j]));
}
}
return combs;
}
```

DFS from the start node s, keep track of the DFS path during traversal, and record the path if you find an edge from node v in the path to s. (v,s) is a back-edge in the DFS tree and thus indicates a cycle containing s.

To clarify:

Strongly Connected Components will find all subgraphs that have at least one cycle in them, not all possible cycles in the graph. e.g. if you take all strongly connected components and collapse/group/merge each one of them into one node (i.e. a node per component), you'll get a tree with no cycles (a DAG actually). Each component (which is basically a subgraph with at least one cycle in it) can contain many more possible cycles internally, so SCC will NOT find all possible cycles, it will find all possible groups that have at least one cycle, and if you group them, then the graph will not have cycles.

to find

*all*simple cycles in a graph, as others mentioned, Johnson's algorithm is a candidate.

Regarding your question about the *Permutation Cycle*, read more here: https://www.codechef.com/problems/PCYCLE

You can try this code (enter the size and the digits number):

```
# include<cstdio>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
int num[1000];
int visited[1000]={0};
int vindex[2000];
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
int t_visited=0;
int cycles=0;
int start=0, index;
while(t_visited < n)
{
for(int i=1;i<=n;i++)
{
if(visited[i]==0)
{
vindex[start]=i;
visited[i]=1;
t_visited++;
index=start;
break;
}
}
while(true)
{
index++;
vindex[index]=num[vindex[index-1]];
if(vindex[index]==vindex[start])
break;
visited[vindex[index]]=1;
t_visited++;
}
vindex[++index]=0;
start=index+1;
cycles++;
}
printf("%d\n",cycles,vindex[0]);
for(int i=0;i<(n+2*cycles);i++)
{
if(vindex[i]==0)
printf("\n");
else
printf("%d ",vindex[i]);
}
}
```

The simplest choice I found to solve this problem was using the python lib called `networkx`

.

It implements the Johnson's algorithm mentioned in the best answer of this question but it makes quite simple to execute.

In short you need the following:

```
import networkx as nx
import matplotlib.pyplot as plt
# Create Directed Graph
G=nx.DiGraph()
# Add a list of nodes:
G.add_nodes_from(["a","b","c","d","e"])
# Add a list of edges:
G.add_edges_from([("a","b"),("b","c"), ("c","a"), ("b","d"), ("d","e"), ("e","a")])
#Return a list of cycles described as a list o nodes
list(nx.simple_cycles(G))
```

**Answer:** [['a', 'b', 'd', 'e'], ['a', 'b', 'c']]

The DFS-based variants with back edges will find cycles indeed, but in many cases it will NOT be *minimal* cycles. In general DFS gives you the flag that there is a cycle but it is not good enough to actually find cycles. For example, imagine 5 different cycles sharing two edges. There is no simple way to identify cycles using just DFS (including backtracking variants).

Johnson's algorithm is indeed gives all unique simple cycles and has good time and space complexity.

But if you want to just find MINIMAL cycles (meaning that there may be more then one cycle going through any vertex and we are interested in finding minimal ones) AND your graph is not very large, you can try to use the simple method below. It is VERY simple but rather slow compared to Johnson's.

So, one of the **absolutely** easiest way to find MINIMAL cycles is to use Floyd's algorithm to find minimal paths between all the vertices using adjacency matrix. This algorithm is nowhere near as optimal as Johnson's, but it is so simple and its inner loop is so tight that for smaller graphs (<=50-100 nodes) it absolutely makes sense to use it. Time complexity is O(n^3), space complexity O(n^2) if you use parent tracking and O(1) if you don't. First of all let's find the answer to the question if there is a cycle. The algorithm is dead-simple. Below is snippet in Scala.

```
val NO_EDGE = Integer.MAX_VALUE / 2
def shortestPath(weights: Array[Array[Int]]) = {
for (k <- weights.indices;
i <- weights.indices;
j <- weights.indices) {
val throughK = weights(i)(k) + weights(k)(j)
if (throughK < weights(i)(j)) {
weights(i)(j) = throughK
}
}
}
```

Originally this algorithm operates on weighted-edge graph to find all shortest paths between all pairs of nodes (hence the weights argument). For it to work correctly you need to provide 1 if there is a directed edge between the nodes or NO_EDGE otherwise. After algorithm executes, you can check the main diagonal, if there are values less then NO_EDGE than this node participates in a cycle of length equal to the value. Every other node of the same cycle will have the same value (on the main diagonal).

To reconstruct the cycle itself we need to use slightly modified version of algorithm with parent tracking.

```
def shortestPath(weights: Array[Array[Int]], parents: Array[Array[Int]]) = {
for (k <- weights.indices;
i <- weights.indices;
j <- weights.indices) {
val throughK = weights(i)(k) + weights(k)(j)
if (throughK < weights(i)(j)) {
parents(i)(j) = k
weights(i)(j) = throughK
}
}
}
```

Parents matrix initially should contain source vertex index in an edge cell if there is an edge between the vertices and -1 otherwise. After function returns, for each edge you will have reference to the parent node in the shortest path tree. And then it's easy to recover actual cycles.

All in all we have the following program to find all minimal cycles

```
val NO_EDGE = Integer.MAX_VALUE / 2;
def shortestPathWithParentTracking(
weights: Array[Array[Int]],
parents: Array[Array[Int]]) = {
for (k <- weights.indices;
i <- weights.indices;
j <- weights.indices) {
val throughK = weights(i)(k) + weights(k)(j)
if (throughK < weights(i)(j)) {
parents(i)(j) = parents(i)(k)
weights(i)(j) = throughK
}
}
}
def recoverCycles(
cycleNodes: Seq[Int],
parents: Array[Array[Int]]): Set[Seq[Int]] = {
val res = new mutable.HashSet[Seq[Int]]()
for (node <- cycleNodes) {
var cycle = new mutable.ArrayBuffer[Int]()
cycle += node
var other = parents(node)(node)
do {
cycle += other
other = parents(other)(node)
} while(other != node)
res += cycle.sorted
}
res.toSet
}
```

and a small main method just to test the result

```
def main(args: Array[String]): Unit = {
val n = 3
val weights = Array(Array(NO_EDGE, 1, NO_EDGE), Array(NO_EDGE, NO_EDGE, 1), Array(1, NO_EDGE, NO_EDGE))
val parents = Array(Array(-1, 1, -1), Array(-1, -1, 2), Array(0, -1, -1))
shortestPathWithParentTracking(weights, parents)
val cycleNodes = parents.indices.filter(i => parents(i)(i) < NO_EDGE)
val cycles: Set[Seq[Int]] = recoverCycles(cycleNodes, parents)
println("The following minimal cycle found:")
cycles.foreach(c => println(c.mkString))
println(s"Total: ${cycles.size} cycle found")
}
```

and the output is

```
The following minimal cycle found:
012
Total: 1 cycle found
```

Similar Questions

I have a directed graph represented like this: arc(1, 2). arc(1, 4). arc(1, 5). arc(3, 2). arc(3, 7). arc(4, 3). arc(5, 6). arc(6, 8). arc(7, 6). arc(9, 8). What I need is a predicate that will put i

Is there any easy way to enumerate all spanning trees of a indirected graph? This can have O(2^n) complexity. The number of nodes on the graph is always lower than 10. I know Knuth has an algorithm on

I am interested in computing total number of simple paths(no node repeated) between two nodes in a graph(sparse, directed and contains cycles). The graph is a strongly connected component. I initially

We are developing one APP to sync Facebook friends to phone contact, and we try to gain contacts via Graph API according the API Reference: Friends: https://graph.facebook.com/me/friends?access_toke

I am trying to find a solution for the next problem with help of Java. I have a graph, this is a good example of how it could look: There is its notation: [{A = {C = 0.7}, {D = 0.3}}, {C = {out = 0.2

I need a working algorithm for finding all simple cycles in an undirected graph. I know the cost can be exponential and the problem is NP-complete, but I am going to use it in a small graph (up to 20-

I'm trying to list all the paths in an undirected graph, and my question is similar to this question. I've tried to run this code, but it loops indefinitely -- I ran it with 60 nodes. Any ideas on how

How to find all chordless cycles in an undirected graph? For example, given the graph 0 --- 1 | | \ | | \ 4 --- 3 - 2 the algorithm should return 1-2-3 and 0-1-3-4, but never 0-1-2-3-4. (Note: [1] Th

I have graph and somehow I need to find all closed contours in graph that doesn't contains any other edges of the graph. I was searching google but only gives me charts :) Is there any library or if

taking imdb.com for example. imdb.com has hundreds of pages with a FB graph ID (one per each movie) I want to fetch ALL FB graph ID's belonging to imdb.com. for example: the FB graph ID for http://www

I'm looking for an implementation preferably in Java of an algorithm for finding a Minimum Equivalent Graph of a Digraph (http://portal.acm.org/citation.cfm?id=321526.321534). Even better would be an

I have a non-weighted DAG graph. What I want to do is to find all the paths in a greedy way and the path should contain at least K nodes, and a given starting node. Is there any existing algorithm/imp

By now, I have used the following algorithm for finding the strongly connected components of a graph. call DFS(G) to compute the finishing time f[v] for every vertex v, sort the vertices of G in decr

I have a directed graph and I want to find all existing eulerian paths (in my graph I actually know that those will be circuits). I have done some research so I can use for example Hierholzer's algor

Is there a way to find all classes participating in the given application, or under the same namespace?

Given a Facebook user id and a Facebook page id, is there any way to get find all interaction that user has done on the page (posting comments, liking posts etc) without first downloading the entire f

Given a directed graph G=(V,E), two vertices s, t and two weight functions w1, w2, I need to find the shortest path from s to t by w2 among all the shortest paths between s to t by w1. First of all ,

Please see Image: http://i.stack.imgur.com/NPUmR.jpg I have an undirected graph which contains one or more connected sub graphs. The graph is defined by a set of ordered pairs of connected vertices. T

Suppose I have a bag which contains 6 balls (3 white and 3 black). I want to find all possible subsets of a given length, disregarding the order. In the case above, there are only 4 combinations of 3

I'm working for finding all permutations of three numbers 1,2,3 using backtracking I defined a,b,c as the following: static int a=1; static int b=2; static int c=3; static int aCount; static int bCou

I'm trying to find all the pages on a domain with Node. I was searching on Stackoverflow, but all i found is this thread for Ruby: Find all the web pages in a domain and its subdomains - I have the sa

I'm following Skiena's algorithm design manual. Implementation that I'm working on is for finding Strongly connected components. However There is one statement in the book which I do not understand th

This code is given in python official essays on graph theory. Here's the code: def find_all_paths(graph, start, end, path=[]): path = path + [start] if start == end: return [path] if not graph.has_key

If I wanted to select all checkboxes that are selected, I could do this. $('#mydiv input[type=checkbox]:checked') Is there a similarly simple syntax that lets me select all the checkboxes that are N

I have an undirected graph. One edge in that graph is special. I want to find all other edges that are part of a even cycle containing the first edge. I don't need to enumerate all the cycles, that wo

I am writing a simple program in SWI-Prolog to run through a directed graph, from one node to the next. I'm having trouble avoiding cycles though and would like some help. Each edge has a cost associa

I need a regular expression (dubbed SOME_EXPRESSION below) that allows finding all namespaces for resources used as subject in a SPARQL 1.1 endpoint. The query should look like the following. How can

Hello and thanks again for reading this. I need to know now if the problem of finding the simple path with maximum cost in a weighted undirected graph with the same number of vertex and edges is NP-Co

Is it feasible to find all simple paths between two nodes by using dijkstra algorithm on an unweighted graph. If yes, how?

I am working on a problem which requires finding all paths between two nodes in a directed graph. The graph may have cycles. Notice that this particular implementation approach is an iterative DFS. S

Given a graph, how can we determine whether or not there exists a vertex v, from which all other vertices are reachable. the algorithm should be as efficient as possible. I know how to do it if we are

I'd like to find all functions in my current workspace and thought about using is.function for that purpose. The problem is that is.function expects a true R object, not the character string name of

I'm trying to write an abstract algorithm using graph theory. Given an undirected and unweighted graph G=(V,E), two vertices: m,n∈V and a specific edge e∈E. I want to check if edge e is a part of all

First of all I'm quite a Java beginner, so I'm not sure if this is even possible! Basically I have a huge (3+million) data source of relational data (i.e. A is friends with B+C+D, B is friends with D+

I have an undirected graph. For now, assume that the graph is complete. Each node has a certain value associated with it. All edges have a positive weight. I want to find a path between any 2 given no

First, a little background: I'm working on building a simple graph class with basic graph algorithms (Dijkstra, Floyd-Warshall, Bellman-Ford, etc) to use as a reference sheet for an upcoming programin

I have recently discovered graphs and algorithms and am trying to solve a specific problem involving two different types of vertices: Users and Entities. Details are as follows: The graph is directed

Consider the following graph: Represented by the following array structure: $graph = array ( 'a' => array(), 'b' => array('a'), 'c' => array('a', 'b'), 'd' => array('a'), 'e' => array(

I'm back with another similar question. I am currently working on a Java program that will check if a graph is 2-colorable, i.e. if it contains no odd cycles (cycles of odd number length). The entire

I can't seem to find more than one error that would cause an infinite loop within this code. Any help anyone could provide me with in finding these errors would be greatly appreciated. Thank you all v

Does anyone have a demo of a jQuery accordion that cycles through content automatically with an option to set the number of loops or cycles?

I was wondering if you are aware of an algorithm to enumerate all possible simple paths in a graph from a single source, without repeating any of the vertices. keep in mind that the graph will be very

Suppose we have a DIRECTED, WEIGHTED and CYCLIC graph. Suppose we are only interested in paths with a total weight of less than MAX_WEIGHT What is the most appropriate (or any) algorithm to find the n

I am dealing with undirected graph. I need to find all possible acyclic paths within a graph: with G(V,E) find all subsets of V that are acyclic paths I am using either python scipy or matlab - which

With XPath (.NET), I'm trying to select all nodes that don't contain any text node. Given this document: <root> <node1> <node1a>Node 1A</node1a> </node1> <node2>Nod

Is there a method to find all functions that were defined in a python environment? For instance, if I had def test: pass some_command_here would return test

Is a tournament graph the same thing as a directed complete graph? And, do all vertices in a tournament graph have the same number of edges?

The city in my game is randomly generated but is a graph of roads and intersections that can only form rectangles: As can be seen, my terrain is pretty empty. What I want to do is find each empty rec

I am fairly new to java and I have been struggling with this exercise for two weeks now(It's an homework exercise in my school). I need to create a topological sort and print out all of the possible c

How would you write something that selects all possible combinations of triples from an array {1, 2, 3, ..., N-1, N} without duplicates? This is from a recently-held programming competition. N is a mu