How to Implement Topological Sorting in Java

1. Topological Sorting in Java
2. Two Real-World Examples of Topological Sort
3. Demonstration of Direct Acyclic Graph
4. Implementation of Topological Sort in Java
5. Topological Sorting in Recursive Order in Java

This in-depth article will teach you how to implement topological sorting on a direct acyclic graph in recursive order. There are two segments in this tutorial.

First, we theoretically unfold the structure, application, scope and sorting of topological order to help our readers build the foundation to then execute the Java code themselves.

As you might have already guessed, the second portion of this article is about the implementation of Directed Acyclic Graphs (DAG).

Topological Sorting in Java

Topological sorting is the ordering of noted (n) in a graph. If there is an edge between (u,v), then u must come before v.

In a real-world scenario, it can be a foundation to build applications that interdepend on each other.

Before we approach topological sorting, you must consider that only Directed Acyclic Graphs (DAG) can be ordered topologically.

Two Real-World Examples of Topological Sort

1. For example, in an integrated development environment (IDE), given the underlying logic to manage the user file system, an IDE may use a topological order to determine the execution and management of the files based on user preferences acquired via GUI.
2. Consider the following example: Two routes can take you to your destination (A and B).

To get there, you can only take one at a time. Assume you take route B. In that situation, you do not travel on road A.

So, it does not create an absolute cycle. Hence, a topological sort is also possible.

There is, on the contrary, only one cycle. The topological order is likely to be ruled out.

Applications of Topological Sorting

1. Scheduling jobs based on interdependence between jobs. This type of sorting is widely performed in research-based applied software engineering, energy efficiency, cloud and networking.
2. Another application of the topo-sorting can be to determine how compilation tasks should be performed in makefiles, data serializations, and symbol dependencies in linkers.
3. Also, it is applicable for manufacturing workflows and context-free grammar.
4. A lot of Build Systems use this kind of algorithm.
5. Migration Systems have long been utilizing this sequential order.

Time Complexity

It’s similar to the Depth-first search (DFS) algorithm but with an extra stack. The time complexity is O(V+E) in generic terms.

Auxiliary Space

O(V) - The additional space is required for the stack.

Demonstration of Direct Acyclic Graph

To begin, you should be clear that topological sorting is the only viable solution if the graph is a Directed Acyclic Graph (DAG). Also, note that there could be several alternative topological orderings for a given directed acyclic graph.

A topological ordering is the arrangement of the vertex in an array.

Consider the following example:

Up to four possible sorting solutions for this DAG:

A B C D E F

A B C D F E

A C B D E F

A C B D F E

If you have understood the initials, we hope you would also comprehend the following hypothetical depiction of a DAG. It is quite significant to mention that our demonstration is only to explain the generic process.

If you are interested in the data structure aspect, consider an alternative. However, the following depiction is enough to sort direct graphs in a recursive and iterative order using Java for all practical purposes.

So, without further ado, follow the following steps.

1. The above graph can also be represented as: C => 0 , D => 0, E => 2
2. Similarly, the execution of this graph may also vary.
3. It is only for the demonstration for your understanding.

Since we got two vertices with the least in-degree, the graph can finally be sorted into the following two n orders.

A B C D E

A B D C E

Implementation of Topological Sort in Java

We will use this graph for the implementation. We aim to determine the appurtenance of u before v based on the graph theory.

Needless to mention that this execution is based on a DAG and DFS. We will sort the graph topologically using an algorithm.

Please, keep reading every step to learn more.

1. Graph:

Let’s use v15 as an example. V15 depends on v10 and v5.

V5 depends on v10 and v20. V10 is dependent on v20.

Based on the dependencies, v5, v10, and v20 should come before v15 in topological sorting.

You should also understand the depth-first search (DFS) to understand this implementation.

2. DFS Algorithm:

Depth-first search, also known as depth-first traversal, is a recursive algorithm for finding all vertices of a graph or tree data structure. Traversing a graph entails visiting all of its nodes.

It categorizes each vertex of the graph into one of two groups.

1. The v is visited.
2. The v is not visited.

Also, note that the DFS algorithm functions as follows:

1. Initially, it arranges the graph’s vertices on top of a stack.
2. Then, it adds the top item from the stack to the visited list.
3. Following that, it lists the nodes adjacent to that vertex.
4. Stack the ones that aren’t on the visited list at the top.

Meanwhile, steps 2 and 3 should be repeated until the stack is empty.

Topological Sorting in Recursive Order in Java

Because topological sorting includes a short stack, we won’t print the vertex right away. Instead, we’ll recursively call topological sorting for all of its neighbors, then push it to a stack.

As of now, let’s break our logical flow into a few easy-to-understand parts.

1. Class TopoSortDAG - contains a stack with all the nodes and determines the visited and not visited nodes.

Code:

public class TopoSortDAG {
  Stack<N> customstack;

  public TopoSortDAG() {
    customstack = new Stack<>();
  }

  static class N {
    int d;
    boolean isVstd;
    List<N> nghbr;

    N(int d) {
      this.d = d;
      this.nghbr = new ArrayList<>();
    }

2. Recursive Topological Sort Algorithm

Code:

public void tpSort(N N) {
  List<N> nghbr = N.getnghbr();
  for (int i = 0; i < nghbr.size(); i++) {
    N n = nghbr.get(i);
    if (n != null && !n.isVstd) {
      tpSort(n);
      n.isVstd = true;
    }
  }
  customstack.push(N);
}

Explanation:

1. This algorithm performs because when we push a v to the stack, we have previously pushed its neighbors (and their dependencies).
2. Henceforth, the v with no dependencies will automatically be at the top of the stack.

Until now, we hope you have understood the basic concept that drives topological sorting so far.

That said, before we run the entire program, you should first understand each step so that you can create your graph next time you approach toposort.

Implementation of Topological Sort in Java Using Recursive Order:

// We will implement a topological sort algorithm on a direct acyclic graph using the depth-first
// search technique.
package delftstack.com.util;

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

/**
 * @author SARWAN
 *
 */
public class TopoSortDAG {
  Stack<N> customstack;

  public TopoSortDAG() {
    customstack = new Stack<>();
  }

  static class N {
    int d;
    boolean isVstd;
    List<N> nghbr;

    N(int d) {
      this.d = d;
      this.nghbr = new ArrayList<>();
    }

    public void adj(N nghbrN) {
      this.nghbr.add(nghbrN);
    }

    public List<N> getnghbr() {
      return nghbr;
    }

    public void setnghbr(List<N> nghbr) {
      this.nghbr = nghbr;
    }

    public String toString() {
      return "" + d;
    }
  }

  public void tpSort(N N) {
    List<N> nghbr = N.getnghbr();
    for (int i = 0; i < nghbr.size(); i++) {
      N n = nghbr.get(i);
      if (n != null && !n.isVstd) {
        tpSort(n);
        n.isVstd = true;
      }
    }
    customstack.push(N);
  }

  public static void main(String arg[]) {
    TopoSortDAG topo = new TopoSortDAG();
    N N20 = new N(20);
    N N5 = new N(5);
    N N10 = new N(10);
    N N15 = new N(15);
    N N30 = new N(30);
    N N25 = new N(25);
    N N35 = new N(35);
    N20.adj(N5);
    N20.adj(N10);
    N5.adj(N15);
    N10.adj(N5);
    N10.adj(N15);
    N10.adj(N30);
    N10.adj(N25);
    N15.adj(N30);
    N30.adj(N35);
    N25.adj(N35);
    System.out.println("Sorting Result Set Based on the Graph:");
    topo.tpSort(N20);

    Stack<N> reS = topo.customstack;
    while (reS.empty() == false) System.out.print(reS.pop() + " ");
  }
}

Output:

Sorting Result Set Based on the Graph:
20 10 25 5 15 30 35

Output Stack: