How to Perform Topological Sort for Dependency Resolution in Java

Question

What is the process for implementing topological sort in Java to handle dependency resolution?

import java.util.*;

public class TopologicalSort {
    private int vertices; // Number of vertices
    private LinkedList<Integer>[] adjList; // Adjacency List

    // Constructor
    public TopologicalSort(int v) {
        vertices = v;
        adjList = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    // Method to add edge to the graph
    public void addEdge(int source, int destination) {
        adjList[source].add(destination);
    }

    // Method to perform topological sort
    public void topologicalSort() {
        Stack<Integer> stack = new Stack<>();
        boolean[] visited = new boolean[vertices];

        // Call the recursive helper function for all vertices
        for (int i = 0; i < vertices; i++) {
            if (!visited[i]) {
                topologicalSortUtil(i, visited, stack);
            }
        }

        // Print the elements in topological order
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
    }

    // A recursive helper function to perform DFS and keep track of visited vertices
    private void topologicalSortUtil(int v, boolean[] visited, Stack<Integer> stack) {
        visited[v] = true;
        
        // Recur for all the vertices adjacent to this vertex
        for (Integer neighbor : adjList[v]) {
            if (!visited[neighbor]) {
                topologicalSortUtil(neighbor, visited, stack);
            }
        }

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

    // Example usage
    public static void main(String[] args) {
        TopologicalSort graph = new TopologicalSort(6);
        graph.addEdge(5, 2);
        graph.addEdge(5, 0);
        graph.addEdge(4, 0);
        graph.addEdge(4, 1);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);

        System.out.println("Topological Sort:");
        graph.topologicalSort();
    }
}

Answer

Topological sorting is an essential method in computer science used to solve problems related to dependency resolution in directed acyclic graphs (DAGs). This guide demonstrates how to implement topological sort in Java, facilitating dependency management in scenarios such as task scheduling and compilation order.

import java.util.*;

public class TopologicalSort {
    private int vertices;
    private LinkedList<Integer>[] adjList;
    
    public TopologicalSort(int v) {
        vertices = v;
        adjList = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adjList[i] = new LinkedList<>();
        }
    }
    
    public void addEdge(int source, int destination) {
        adjList[source].add(destination);
    }
    
    public void topologicalSort() {
        Stack<Integer> stack = new Stack<>();
        boolean[] visited = new boolean[vertices];
        
        for (int i = 0; i < vertices; i++) {
            if (!visited[i]) {
                topologicalSortUtil(i, visited, stack);
            }
        }
        
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
    }
    
    private void topologicalSortUtil(int v, boolean[] visited, Stack<Integer> stack) {
        visited[v] = true;
        
        for (Integer neighbor : adjList[v]) {
            if (!visited[neighbor]) {
                topologicalSortUtil(neighbor, visited, stack);
            }
        }
        stack.push(v);
    }
    
    public static void main(String[] args) {
        TopologicalSort graph = new TopologicalSort(6);
        graph.addEdge(5, 2);
        graph.addEdge(5, 0);
        graph.addEdge(4, 0);
        graph.addEdge(4, 1);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);
        
        System.out.println("Topological Sort:");
        graph.topologicalSort();
    }
}

Causes

Understanding the structure of directed acyclic graphs (DAGs) is crucial for implementing topological sort effectively.
Recognizing situations where topological sort is applicable, such as project task scheduling, is necessary.

Solutions

Utilize Depth First Search (DFS) to explore the graph and track visited vertices for topological sorting.
Use a stack to collect the vertices in topological order by pushing them after all their dependencies have been processed.

Common Mistakes

Mistake: Directly modifying the graph while iterating can lead to unexpected behavior.

Solution: Ensure that you do not change the graph structure during the sort process.

Mistake: Failing to check for cycles in the graph can lead to infinite loops.

Solution: Since topological sort is only applicable to DAGs, implement cycle detection methods to validate the graph before sorting.

Helpers

Topological Sort Java
Dependency Resolution in Java
Graph Traversal Java
DFS for Topological Sort
Java Programming Questions