Introduction

Cycle detection in directed graphs is an essential problem in computer science, with applications in various domains, such as financial trading, multithreading, and operating systems. Understanding how to detect cycles allows us to optimize systems, prevent deadlocks, and even identify arbitrage opportunities in financial markets.

Applications of Cycle Detection

• Arbitrage Trading in FOREX
  Arbitrage trading involves exploiting inefficiencies in currency exchange rates. In a directed graph , each vertex represents a currency, and each directed edge represents an exchange rate between two currencies. A cycle in this graph can indicate a potential arbitrage opportunity, where a trader can convert currencies along the cycle and end up with more than the initial amount.
• Deadlocks in Multithreading
  In a multithreaded environment, processes may compete for limited resources, and cycles in the resource allocation graph can lead to deadlocks. A deadlock occurs when a group of processes is waiting for resources held by each other in a circular chain, preventing any progress. Identifying cycles in the resource allocation graph is crucial to avoid deadlocks.
• Operating Systems and Resource Allocation
  Operating systems manage multiple processes simultaneously. When a new process starts, the OS allocates resources to it. If cyclic dependencies exist in the allocation graph, processes may end up in a deadlock state. Therefore, detecting cycles in the resource allocation graph is necessary to ensure smooth process execution.

Detecting Cycles in a Directed Graph

To detect cycles in a directed graph, we can use various algorithms:

• Depth-First Search (DFS) with Recursion Stack
  One common approach is to use Depth-First Search (DFS) while keeping track of visited nodes and recursion stack.
  – If a node is revisited while still in the recursion stack, a cycle exists.
  – If no cycle is found after exploring all nodes, the graph is acyclic.
• Kahn’s Algorithm (Topological Sorting)
  Kahn’s algorithm is another approach that works by:
  – Finding nodes with zero in-degree (no incoming edges).
  – Removing them and updating in-degrees of their neighbors.
  – If all nodes are removed successfully, the graph is acyclic; otherwise, a cycle exists.

Example

Let us take an example to understand how to find cycle in a graph. Following is the sample graph. We’ll use Breadth-First Search to detect cycle.

We’ll start with some arbitrary vertex D. Depth First Search explores all the children of the current vertex. For instance, starting with vertex A, the algorithm proceeds by making recursive calls for each of its children. We have vertex C and Vertex E as the children of vertex A. Vertex C has two children, vertex B and Vertex D. Vertex B has no children, so we mark it as visited. Breadth first search will back track and will visit all the children of the parent. Sine vertex D does not have any children, vertex D is marked as visited.
Next, vertex C is considered as visited as all of its children are visited.

Now, we need to visit the remaining children of vertex X, that is vertex E.

We visit Vertex E and then examine its children. Upon analysis, we identify Vertex D as a child of Vertex E. However, since Vertex D has already been visited, it is currently in the “being visited” state.

Revisiting Vertex D at this stage indicates the presence of a cycle in the graph, which is caused by the existence of a backward edge.

Implementation

Vertex.java

import java.util.ArrayList;
import java.util.List;

public class Vertex {
    private String name;
    private boolean visited;
    private boolean isBeingVisited;
    private List<Vertex> adjancencyList;

    public Vertex(String name){
        this.name=name;
        this.adjancencyList=new ArrayList<>();
    }

    public boolean isVisited() {
        return visited;
    }

    public void setVisited(boolean visited) {
        this.visited = visited;
    }

    public boolean isBeingVisited() {
        return isBeingVisited;
    }

    public void setBeingVisited(boolean beingVisited) {
        isBeingVisited = beingVisited;
    }

    public List<Vertex> getNeighbor() {
        return adjancencyList;
    }

    public void addNeighbor(Vertex vertex) {
        this.adjancencyList.add(vertex);
    }

    @Override
    public String toString() {
        return "Vertex{" +
                "name='" + name + '\'' +
                '}';
    }
}

CycleDetection.java

import java.util.List;

public class CycleDetection {
    public void detectCycles(List<Vertex> graph){
        // there are multiple independent clusters
        for(Vertex v: graph){
            if(!v.isVisited()){
                dfs(v);
            }
        }
    }

    private void dfs(Vertex vertex){
        vertex.setBeingVisited(true);
        for(Vertex v: vertex.getNeighbor()){
            if(v.isBeingVisited()){
                System.out.println("Cycle detected");
                return;
            }
            if(!v.isVisited()){
                v.setVisited(true);
                dfs(v);
            }
        }
        vertex.setBeingVisited(false);
        vertex.setVisited(true);
    }
}

App.java

public class App {

    public static void main(String[] args) {

        Vertex v0 = new Vertex("A");
        Vertex v1 = new Vertex("B");
        Vertex v2 = new Vertex("C");
        Vertex v3 = new Vertex("D");
        Vertex v4 = new Vertex("E");
        Vertex v5 = new Vertex("F");

        // we have to handle the connections
        v0.addNeighbor(v2);
        v0.addNeighbor(v4);
        v2.addNeighbor(v1);
        v2.addNeighbor(v5);
        v3.addNeighbor(v0);
        v4.addNeighbor(v3);

        List<Vertex> graph = new ArrayList<>();
        graph.add(v0);
        graph.add(v1);
        graph.add(v2);
        graph.add(v3);
        graph.add(v4);
        graph.add(v5);

        CycleDetection algorithm = new CycleDetection();
        algorithm.detectCycles(graph);
    }
}