Cycles In Graphs Part 1

Detect if there is a cycle in a graph

Today’s lesson is about detecting if there’s any cycle in a graph. At the beginning, we will answer some questions to put everyone on the same ground.

Cycle Graph from GeeksForGreek

First: What’s the mean of a graph?

A graph represents a non-linear kind of data structure. Which consists of edges and nodes. Nodes represent the elements inside the graph and Edges lead between nodes and each other. We have seen many graphs before in our previous lesson for example lesson 8 we learned BFS and how to go through all of the nodes of a graph to find a certain node.

Second: what’s the mean of a cycle graph?

A cycle graph is a graph in which there is a node that has a path which will return to itself.

Third: what’s the important of detecting it?

Well to answer this question I will give you an example where you want to go out with your friends let’s name them Ziad and Abaker. Abaker waits for his brother Abader to come back home as his brother has no key to enter the home when returns.

The story has not ended yet Ziad will only go out after finishing his homework. He also waits for Abader to help him solve his homework. The surprise is that Abader waiting for Mohamed to return his book.

Mohamed is waiting for Ziad to send him an email with the answer to the homework.

The example is complex I know but the thing that I am sure you realize is that we go to a state like this:

Everyone waits for the other

The sad part of the story is that probably you will not go out with your friends today but the happy part is that you will have time to understand the cycle graph.

Why you probably will not go out the following figure will help you figure out the situation you ran into:

The graph represents our example

In the graph, you will notice that Ziad represents the cycle in our graph. why?

Because if you go from Ziad to Abader and then to Mohamed you will find yourself returning to Ziad.

But Why I will not go out with my friends? because we reach a deadlock state where everyone waits for the other to take a step so he can proceed.

In computers when we reach a state like this we will have a deadlock (if the process gets stuck)or an endless loop (if the process runs endlessly).

In both cases, usually, the program fails to show a reaction and has to be ended from the outside, e.g., by the user. This is why it is important to recognize cycles and, if possible, avoid them.

Now after answering all the questions, you may wonder. We can start to implement an algorithm using depth-first search to detect a cycle in a graph.

Let’s continue with our graph and represent it as follows:

const goOutWithFriendsGraph = {
 YOU:["Ziad","Abaker"],
 Ziad:["Abader"],
 Abaker:["Abader"],
 Mohamed:["Ziad"],
 Abader:["Mohamed"]
}

To detect the cycle we will have an inProgress state which describes the node that has still not finished and we still discover its nodes.

const mark = {} //save the status of nodes

function searchCycle(node,graph){
// check if a node is already still in progress and had been visited again
  if(mark[node] === "inProgress"){
    console.log("cycle has been found")
  }
// check if the node not marked yet
  else if(!mark[node]){
    mark[node] = "inProgress"
// visit every neighbour for the node
    for(let friend of graph[node]){
     searchCycle(friend,graph)
    }
// mark the node with done after finish visiting all his neighbours
    mark[node] = "done"
  }
}

searchCycle("YOU",goOutWithFriendsGraph) 

This code will print out that a cycle has been found in the graph you provide but it will not return to us the path where there is a cycle.

Let’s go step by step through what happens in our implemented code:

First, we will start with YOU and we will find that it’s not inProgress or even in our mark object so we will add it to our mark and make it status inProgress. Looping through YOU neighbours first we found Ziad so we will execute searchCycle(“Ziad”) as he has not added to the mark object yet we will add it and make it status inProgress.

Then, we will loop through Ziad's neighbours finding that he has only one neighbour Abader so we will execute searchCycle(“Abader”). Abader is not marked yet so we will add him and make his status inProgress.

Then, we will loop through Abader's neighbour which is Mohamed only so we will execute searchCycle(“Mohamed”). Mohamed will be marked with inProgress.

Looping in Mohamed's neighbours we will find Ziad so we will execute searchCycle(“Ziad”). Ziad is already marked as inProgress so we will print out that we found a cycle as he has not marked as done yet and we visited him again which means there is a path that goes out from Ziad and returns to him.

We will return to Mohamed and mark him as a Done node as we had visited all his neighbours and reached to dead point where we found that there was a cycle.

Then we return to Abader and mark him as a done node as all his neighbours have been executed.

We will do the same with Ziad also, and then return to the root where we start “YOU” and see that there is one remaining neighbour not visited yet which is Abaker so we will execute searchCycle(“Abaker”).

We will Mark Abaker's node to be inProgress, and visit all his neighbours which is Abader.

Visiting Abader we will execute searchCycle(“Abader”) and find that he marked with done so we will do nothing with him and we will return to Abaker.

Returning to Abaker after visiting all his neighbours we will mark him as a Done node and we will return to the “YOU” node and mark it also with done as we have finished looping through all of its neighbours.

Our function has completed its execution and as we see it returns only that there is a cycle but does not determine the path of the cycle you have to snapshot it by yourself to find out.

So can we implement a depth-first search algorithm which will print out the path which has a cycle yes of course we can and we will implement it now.

All we have to do is simply refactor our previous code adding a stack to save the search path we go through.

const mark = {} //save the status of nodes
const searchPath = [] //stack to save the path 

function searchCycle(node,graph){
// check if a node is already still in progress and had been visited again
  if(mark[node] === "inProgress"){
    // find the index of node where cycle start
    let startCycle = searchPath.findIndex(n=> n === node) 
    let path = "" // intialize our path with node where cycle start
    // loop throught searchPath to determine the cycle path
    for(let i = startCycle ; i < searchPath.length ; i++){
       path+= ` ${searchPath[i]} -` 
    }
    console.log(path + " " + node)
  }
// check if the node not marked yet
  else if(!mark[node]){
    mark[node] = "inProgress"
    searchPath.push(node) 
// visit every neighbour for the node
    for(let friend of graph[node]){
     searchCycle(friend,graph)
    }
// mark the node with done after finish visiting all his neighbours
    mark[node] = "done"
    searchPath.pop()
  }
}

searchCycle("YOU",goOutWithFriendsGraph)

After we do this refactor our code will print out Ziad- Abader- Mohamed-Ziad which is the cycle path.

Note that we have to remove a node from the search path after we mark it as done because it’s already not still in our current search path and it’s not a part of the cycle.

That’s enough for this story we will continue lesson 9 in another one where we will talk about strongly connected components, and searching for cycles with the Breadth-First search so stay tuned.