Detecting circular references in Directed acyclic graph

Question

Currently I'm using sample from this for topological sorting with some modification https://www.geeksforgeeks.org/topological-sorting/

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Stack;

public class CalcGraph {

    private int V; // No. of vertices

    private LinkedList<Integer> adj[]; // Adjacency List

    private ArrayList<Integer> result;

    // Constructor
    public CalcGraph(int v) {
        V = v;
        result = new ArrayList<>();
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    public ArrayList<Integer> getResult() {
        return result;
    }

    public void setResult(ArrayList<Integer> result) {
        this.result = result;
    }

    // Function to add an edge into the graph
    public void addEdge(int v, int w) {
        adj[v].add(w);
    }

    // A recursive function used by topologicalSort
    public void topologicalSortUtil(int v, boolean visited[], Stack<Integer> stack) {
        // Mark the current node as visited.
        visited[v] = true;
        Integer i;

        // Recur for all the vertices adjacent to this
        // vertex
        Iterator<Integer> it = adj[v].iterator();
        while (it.hasNext()) {
            i = it.next();
            if (!visited[i])
                topologicalSortUtil(i, visited, stack);
        }

        // Push current vertex to stack which stores result
        stack.push(new Integer(v));
    }

    public void topologicalSort() {
        Stack<Integer> stack = new Stack<Integer>();

        // Mark all the vertices as not visited
        boolean visited[] = new boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;

        // Call the recursive helper function to store
        // Topological Sort starting from all vertices
        // one by one
        for (int i = 0; i < V; i++)
            if (visited[i] == false)
                topologicalSortUtil(i, visited, stack);

        // Print contents of stack
        while (stack.empty() == false) {
            int graphId = stack.pop();
            result.add(graphId);
        }
    }
}

I'm using it to sort the order of variable to solve.

Sample,

a = b + c
b = c + d
c = 7
d = c + 1

Each variable has a unique integer assign to it and stored in a map

{
    "1" : { "id" : "a", "child": [b, c]},
    "2" : { "id" : "b", "child": [c, d]},
    "3" : { "id" : "c", "child": []},
    "4" : { "id" : "d", "child": [c]}
}

When creating graph and add edges, There are total of 4 vertices So my code will construct the graph like this as a result

CalcGraph g = new CalcGraph(6);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.addEdge(2, 4);
g.addEdge(4, 3);

After sorting and get the result in reverse order, it is correct c > d > b > a

Everything is fine but I need to detect circular reference in the graph. Let's say the variables are

a = b + c + d
b = c + d
c = 7
d = c + e
e = a + 1

There's a circular reference, which "e" needs "a" to be completed, but "a" requires "b", "c", "d", and "e" to first be completed.

I'm not sure how to check for circular reference using Directed acyclic graph.

Or is it better to use a different data structure to check for circular reference? i.e tree

Thanks

Answer 1

Instead of the boolean visited[] array, you can use a int state[] array, where 0 means 'not yet visited, 1 means 'in progress', and 2 means 'done'. Then when the current node depends on one that is 'in progress', you know you have found a cycle.

I prefer to do topological sort with Kahn's algorithm, which uses less stack space and detects cycles automatically (it will add less than all the nodes to the result).

Kahn's algorithm on your graph would look like this:

public void topologicalSort() {
    result.clear();

    // calculate in-degrees

    int in_degree = new int[V]; //initialized to zeros
    for (int i = 0; i < V; ++i) {
        for(Integer target: adj[i]) {
          ++in_degree[target];
        }
    }

    // add start nodes to result

    for (int i = 0; i < V; ++i) {
        if (in_degree[i]==0) {
            result.add(i);
        }
    }

    // uncount edges from added nodes to find new nodes to add

    for (int scanpos=0; scanpos < result.size(); ++scanpos) {
        for(Integer target: adj[result.get(scanpos)]) {
            if (--in_degree[target] == 0) {
                result.add(target);
            }
        }
    }
    
    //done
    if (result.size() < V) {
        throw new RuntimeException("Ack! a cycle!");
    }
}