How should I find cycle in the directed graph and list out the nodes which are forming the cycle?

Question

I have the array of objects in javascript i am trying to draw the directed graph how should i find whether it contains cycle or not if contains what are the elements forming the cycle Graph is not strongly connected and nodes can be isolated like "f"

 array = {};
//operations   parents
    array[a] = [b,c]
    array[b] = [d,c]
    array[e] = [a,b]
    array[d] = [e]
    array[f] = []

I want to find the cycle between the operations like here we have cycle from e-d-b-e? How should i find the cycle? I am using javascript.

Answer 1

Here is a BFS solution that will find one cycle (if there are any), which will be (one of) the shortest one(s).

function getCycle(graph) {
    // Copy the graph, converting all node references to String
    graph = Object.assign(...Object.keys(graph).map( node =>
                ({ [node]: graph[node].map(String) }) 
    ));

    let queue = Object.keys(graph).map( node => [node] );
    while (queue.length) {
        const batch = [];
        for (const path of queue) {
            const parents = graph[path[0]] || [];
            for (const node of parents) {
                if (node === path[path.length-1]) return [node, ...path];
                batch.push([node, ...path]);
            }
        }
        queue = batch;
    }
}

// First example
var graph = {
    a: ['b', 'c'],
    b: ['d', 'c'],
    e: ['a', 'b'],
    d: ['e']
};
var result = getCycle(graph);
console.log(result);

// Second example (numeric node references)
var graph = {
    0: [4],
    1: [4,0],
    2: [0,1],
    3: [1],
    4: [3]
};
var result = getCycle(graph);
console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

NB: If you define your graph with number references, a type conversion is needed since object properties are always of type string. We could use == instead of ===, but then the output will still be a mix of string and numbers; I think it is nicer to first convert every node reference to string.

Answer 2

So as I commented, you need to basically traverse through the whole graph and keep a visited array to keep track of nodes that you have visited till now and if you reach any already visited node, then there exists a cycle in the provided directed graph.

To make your work easier here is a running code, you can use it as reference to build your algorithm on it.

Improved my answer little bit, iterating through all nodes, so that it covers some unreachable paths as well. Thank you all :)

array = {};

/*
Assuming 
a = 0
b=  1
c = 2
d = 3
e = 4
*/

// Here I am forming an adjacency list of directed nodes based on the diagram
array[0] = [4];
array[1] = [4,0];
array[2] = [0,1];
array[4] = [3];
array[3] = [1];
visited = {};
visited[0] = 0;
visited[1] = 0;
visited[2] = 0;
visited[3] = 0;
visited[4] = 0;

list_for_cycle_nodes = [];

for(var node = 0; node<5; node++) {
   if (dfs(node)) {
    for (var index = 0; index < list_for_cycle_nodes.length; index++) {
      console.log(list_for_cycle_nodes[index]+" ");
    }
    console.log('There is a cycle');
  } else {
    console.log('Yipee, there is no cycle');
  } 
}

function dfs(s) {
  if(visited[s] == 1) {
    return true;
  }
  list_for_cycle_nodes.push(s);
  visited[s] = 1;
  var flag = false;
  if(array[s].length <= 0) {
    return false;
  }
  for(var index = 0; index<array[s].length; index++) {
    flag = flag | dfs(array[s][index]);
    if(flag) {
      return true;
    }
  }
  return flag;
}

Hope this helps!

Answer 3

After referring to the comments on @zenwraigts solution I infer that this is a problem of Strongly Connected Components. You can find a good tutorial here, you can find javascript implementations here and here.

How is this a problem of SCC ?

all vertices which form a strongly connected component for a cycle, the problem reduces to finding all SCC's and print them

Answer 4

Depth-First Search. If DFS finds an edge that points to an already discovered ancestor of the current node, the graph contains a cycle.