Ryoma Taniyama

view of a hedge maze

Topological Sorting and Cycle Detection

Topological Sorting

Topological sorting arranges the nodes which belong to a directed acyclic graph (DAG) in a linear order so that for every edge from \(v_i\) to \(v_j\) , \(v_i\) appears before \(v_j\). There’re two well-known algorithms to execute topological sorting: Depth-First Search (DFS) approach, and Kahn’s algorithm.

Topological sorting: DFS approach

In DFS approach, we need to add one step into the plain DFS traversal. This algorithm is composed of the following steps.

  1. Choose a node.
  2. Choose an unvisited adjacent node.
  3. If the current node doesn’t have any unvisited adjacent neighbors, add the node to a stack, and backtrack to the last node that has unvisited adjacent neighbors.
  4. When we complete traversing, return the stack, which is arranged in a topological ordering.
Java
public class AdjacencyMatrixGraph {
    private List<Node> nodes;
    private int[][] matrix;
    private int size;
}
Java
public class TopologicalSorting {

    public static List<Node> sortDfs(AdjacencyMatrixGraph graph) {
        Stack<Integer> stack = new Stack<>();
        boolean[] visited = new boolean[graph.getSize()];
        int src = 0;
        sortDfsHelper(graph, src, visited, stack);

        List<Node> sorted = new ArrayList<>();
        while (!stack.isEmpty()) {
            sorted.add(graph.getNodes().get(stack.pop()));
        }
        return sorted;
    }

    private static void sortDfsHelper(AdjacencyMatrixGraph graph, int src, boolean[] visited, Stack<Integer> stack) {
        if (visited[src]) return;

        visited[src] = true;
        for (int dst = 0; dst < graph.getMatrix()[src].length; dst++) {
            if (graph.getMatrix()[src][dst] == 0) continue;
            sortDfsHelper(graph, dst, visited, stack);
        }
        // additional step to plain DFS
        stack.push(src); 
    }

}

Topological sorting: Kahn’s algorithm

On the other hand, Kahn’s algorithm keeps track of the indegree of each node to execute a topological sorting. The indegree of a node represents the number of incomming edge to that node.

  1. Calculate the indegrees of all nodes.
  2. Add zero-indegree nodes to a queue.
  3. Dequeue a node, append it to a list that we’re going to return, decrement the neighbors’ indegrees, and add zero-indegree nodes to the queue.
  4. Repeat those operations as long as the queue is not empty.
Java
public class TopologicalSorting {

    public static List<Node> sortKahn(AdjacencyMatrixGraph dag) {
        Map<Integer, Integer> indegrees = new HashMap<>();
        for (int dst = 0; dst < dag.getSize(); dst++) {
            int indegree = 0;
            for (int src = 0; src < dag.getSize(); src++) {
                indegree += dag.getMatrix()[src][dst];
            }
            indegrees.put(dst, indegree);
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int key : indegrees.keySet()) {
            if (indegrees.get(key) != 0) continue;
            queue.add(key);
        }

        List<Node> sorted = new LinkedList<>();
        while (!queue.isEmpty()) {
            int zeroIndegreeSrc = queue.poll();
            sorted.add(dag.getNodes().get(zeroIndegreeSrc));

            for (int dst = 0; dst < dag.getSize(); dst++) {
                if (dag.getMatrix()[zeroIndegreeSrc][dst] == 0) continue;
                indegrees.put(dst, indegrees.get(dst) - 1);
                if (indegrees.get(dst) == 0) queue.add(dst);
            }
        }

        return sorted;
    }

}

Cycle Detection

Cycle detection: Kahn’s algorithm

Kahn’s algorithm can also be used to detect cycles in a graph. First, if there’re no zero-indegree nodes, there’s a cycle obviously. Additionally, if a graph contains a cycle, Kahn’s topological sorting algorithm won’t encompass all the nodes. That’s because in a cycle such as \(v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_1\) , the indegrees of these nodes won’t reach zero. Consequently, they won’t be added to the queue, and therefore won’t appear in the outcome.

Cycle detection: white-gray-black approach

Suppose that a graph is directed. While DFS traversal, if, before exploring every descendant completely, we find a node which is adjacent to its ancestor, it indicates the presence of a cycle. Therefore, to implement this algorithm, we need to keep track of the nodes that we’re currently exploring.

Java
public class CycleDetection {

    public static boolean existsCycle(AdjacencyMatrixGraph graph) {
        Set<Integer> unvisited = new HashSet<>();
        Set<Integer> visiting = new HashSet<>();
        Set<Integer> visited = new HashSet<>();

        IntStream.range(0, graph.getSize()).forEach(unvisited::add);
        for (int src = 0; src < graph.getSize(); src++) {
            if (!unvisited.contains(src)) continue;
            if (existsCycleHelper(src, graph, unvisited, visiting, visited)) return true;
        }
        return false;
    }

    private static boolean existsCycleHelper(int src, AdjacencyMatrixGraph graph, Set<Integer> unvisited, Set<Integer> visiting, Set<Integer> visited) {
        unvisited.remove(src);
        visiting.add(src);

        for (int dst = 0; dst < graph.getSize(); dst++) {
            if (graph.getMatrix()[src][dst] == 0) continue;
            if (visited.contains(dst)) continue;
            if (visiting.contains(dst)) return true;
            return existsCycleHelper(dst, graph, unvisited, visiting, visited);
        }

        visiting.remove(src);
        visited.add(src);
        return false;
    }

}

Reference

Posted

in

Tags: