Home » Core Java » Topological Sort Java Example

About Venkat-Raman Nagarajan

Venkat works for a major IT firm in India and has more than a decade of experience working and managing Java projects for a banking client.

Topological Sort Java Example

In this article, we will discuss the Topological sort Java algorithm. We will start with graphs, some common types, and to store graphs.

1. Graph and common types

A graph is a non-linear data structure consisting of a finite set of Vertices (also called nodes) connected by Edges.

Topological Sort Java - Graph
Fig 1. A sample Graph with vertices and edges

In the above example, the graph has vertices V1, V2, V3, V4 with edges E1, E2, E3, E4. Let us look at some classification of graphs

Graphs can be classified as below

  • Directed or Undirected
  • Weighted or Unweighted
  • Cyclic or Acyclic

Directed or Undirected: Directed graphs have edges pointed from one node to another, whereas Undirected graphs do not have any directions.

Weighted or Unweighted: A graph is said to be weighted if it has weight (this could be to indicate either distance or time taken between locations, where each node represents a location) mentioned on the edges.

Cyclic or Acyclic: A graph is said to be cyclic if it contains a cycle (a cycle in a graph is a non-empty trail in which only repeated vertices are the first and last vertices)

2. Store a graph

Topological sort algorithms for graphs can be stored as:

  • Edge list
  • Adjacency matrix
  • Adjacency list

Let us take an example of an undirected graph with 5 vertices and 6 edges to discuss these types. An index is also indicated beside each edge.

Topological Sort Java - Undirected graph
Fig 2. Undirected graph

Edge list: This deals with storing the vertices and edges as a list. So, in our example, it can be represented as {(0,1), (0,2), (0,3), (1,3), (2,4), (3,4)}. As it’s an undirected graph, edge (0,1) is the same as (1,0). Hence (1,0) is not mentioned in the above list. We can note that the time and space complexity, in this case, would be O(E), where E represents Edges.

Adjacency Matrix: This deals with storing the edges between nodes as a matrix representation.

Topological Sort Java - Adjacency Matrix
Fig 3. Adjacency Matrix

In this representation, the index of all vertices is indicated in a matrix format with values 0 and 1, with 1 representing an edge between two vertices. The graph, in this case, would be represented as {(0,1,1,1,0) , (1,0,0,1,0) , (1,0,0,0,1) , (1,1,0,0,1) ,(0,0,1,1,0)}. We can note that time complexity, in this case, would be O(V) and space complexity would be O(V2), where V represents the number of vertices. This representation would be more useful when the graph is dense (i.e. too many edges)

Adjacency List: In this case, the graph is represented as a list, with the index indicating the vertex/ node and the value at that index representing its neighbors. In our example, it can be shown as {(1,2,3) , (0,3) , (0,4) , (0,1,4) , (2,3)}. We can note that space is saved in this representation and is better for sparse graphs (i.e too few edges). Time complexity would be O(V) and space complexity would be O(E), where E and V represent the number of Edges and Vertices.

3. Topological Sort Java example

A Topological sort can work only for directed acyclic graphs (DAG). Let us look at an example to discuss topological sort in java. We will use a similar example as previous but as a directed one.

Topological Sort Java - example
Fig 4. Topological Sort example

The above directed acyclic graph contains 5 nodes and 6 edges. We will use the adjacency list representation as the graph is sparse.

The nodes are {A, B, C, D, E}, and edges are {(A,B) , (A,C) , (A,D) , (B,D) , (C,E),(D,E)}. The sort should always start from the node that does not have any incoming directed edges (Node A in this case). The visited node list at this moment would be {A}. The neighbor nodes for A are B, C, and D. The next neighbor node that can be visited is either C or B. D has another incoming directed edge from an unvisited node (B), so cant be visited at this point. Let us visit C. The visited node list would now be {A, C}. The neighbor node for C is E, but can’t be visited as it has another incoming directed edge from an unvisited node (D). So, let us take up the next neighbor node for A i.e. B. The visited node list would now be {A, C, B}. B’s neighbor node D can also be visited as it no longer has any directed edges from unvisited nodes, thereby making the visited list to {A, C, B, D}. Finally, we can visit the last node E making the visited list as {A, C, B, D, E} and this would be our sorted order. Note that this is not the only solution. {A, B, D, C, E} is also acceptable.

When implementing this algorithm programmatically, we shall use Stack, HashMap, and ArrayList. We’ll implement this recursively, and hence the last visited node would be the first on the stack. After all the nodes are visited, we will have our topological sort in the stack in reverse order.Graph.java

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

/*
* Graph class holds nodes and their edges. 
* The class also contains the logic to sort
*/

public class Graph{
	// a list to hold all the edges for each node/ vertex
	private HashMap<Character, ArrayList> edges;
	// a list of hold all the nodes
	private List nodes;
	// a list to indicate nodes that were visited/ traversed
	private List nodeVisited;
	// a list to hold all the edges
	private ArrayList edgeList;
	
	// a public constructor to set the nodes and intialize edge list
	public Graph(List vertices){
		nodes = vertices;
		edges = new HashMap();
		nodeVisited = new ArrayList();
	}
	
	// method to add edge to a node. i.e. adding edges for given nodes.
	public void addEdge(Character x, Character y){
		
		// If the node (key) and edge (value) are being added for first time
		if(!edges.containsKey(x)){
			edgeList = new ArrayList();
		} else {
			// if the node already has edges added
			edgeList = edges.get(x);
		}
		edgeList.add(y);
		edges.put(x,edgeList);
	}
	
	// method containing the logic to sort the given nodes recursively
	public void topologicalSort(){
		Stack stack = new Stack();
		// iterate through all the nodes and their neighbours if not already visited.
		for (Character c : nodes){
			if(!nodeVisited.contains(c)){
				sort(c, stack);
			}
		}
		// print all the elements in the stack in reverse order
		while(!stack.empty()){
			System.out.print(stack.pop()+ " ");
		}
	}
	
	// this recursive method iterates through all the nodes and neighbours. 
	// Pushes the visited items to stack
	public void sort(Character ch, Stack stack){
		// add the visited node to list, so we don't repeat this node again
		nodeVisited.add(ch);
		// the leaf nodes wouldn't have neighbors. A check added to avoid null pointer
		if(edges.get(ch)!=null){
			// get all the neighbor nodes , by referring its edges
			Iterator iter = edges.get(ch).iterator();
			Character neighborNode;
			// if an edge exists for the node, then visit that neighbor node
			while(iter.hasNext()){
				neighborNode = iter.next();
				if(!nodeVisited.contains(neighborNode)){
					sort(neighborNode,stack);
				}
			}
		}
		// push the latest node on to the stack
		stack.push(new Character(ch));
	}
}
TopologicalSort.java
import java.util.ArrayList;
import java.util.Arrays;

public class TopologicalSort{
	public static void main(String args[]){
	// define the array with nodes
	ArrayList list = new ArrayList(Arrays.asList('A','B','C','D','E'));

	// defining the edges for nodes
	Graph charGraph = new Graph(list);
	charGraph.addEdge('A','B');
	charGraph.addEdge('A','C');
	charGraph.addEdge('A','D');
	charGraph.addEdge('B','D');
	charGraph.addEdge('C','E');
	charGraph.addEdge('D','E');
	charGraph.topologicalSort();
	}
}

The output of the above code would be {A C B D E}.

These were the topological sort algorithms.

4. Download source code

Download
You can download the full source code of this example here: Topological Sort Java Example

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you our best selling eBooks for FREE!

 

1. JPA Mini Book

2. JVM Troubleshooting Guide

3. JUnit Tutorial for Unit Testing

4. Java Annotations Tutorial

5. Java Interview Questions

6. Spring Interview Questions

7. Android UI Design

 

and many more ....

 

Receive Java & Developer job alerts in your Area

I have read and agree to the terms & conditions

 

Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Inline Feedbacks
View all comments