Topological Sorting of a Directed Acyclic Graph and Cycle Detection

Introduction

A  topological ordering or sorting of the vertices of a directed acyclic graph is a linear ordering of its vertices such that for every edge uv,  the parent u comes before the child v.  Topological sorting of directed graph with cycles is not possible.  Topological sorting defines the order in which tasks must be done. For example, courses in a college can be taken only after satisfying the prerequisites. We can define a define a directed relationship between the courses, and then order them to know which course can be taken when. Further details about the topological sorting can be obtained from the references.

Program with Examples

Code: Here is a java code to perform topological sorting of a DAG. It also detects if the input directed graph has cycles. TopologicalSorting.java.

Execution Instructions: To execute the program, put the java file and the input file in the same directory. Change the input file path name in the code at the 29th line. Compile the java code and execute it.

Input Files: Below are examples with corresponding input files. Input files represent the graph as parent and its children. A vertex u is called a parent of a vertex v if there is a directed edge from u to v. Each row in the file represent a vertex followed by a list of its children. 

a) Input DAG 1

Input File: DAG_Sort_1.txt

A C

C G F

F H

B D F

D G

E D

E G

Output : E A B C D F G H

b) Input DAG 2

Input File: DAG_Sort_2.txt

A C

C G F

F H

B D F

D G

E D

E G

H G

Output: E A B C D F H G

c)  Input DAG 3

Input File: DAG_Cycle.txt

A C

C G F

F H

B D F

D G

E D

E G

H G

G F

Output: DAG has Cycles

References

1. Wikipedia article.
2.  Algorithm 
3.  Graph algorithm video lecture
4.  The Stony Brook Algorithm Repository