Java Program to Check Whether Topological Sorting can be Performed in a Graph

This is a java program to check if topological sorting can be performed on graph or not. Topological sort exists only if there is not cycle in directed graph. In short this problem can be reduced to check if the given graph is Directed Acyclic Graph. If it is topological sort can be performed, not otherwise.

Here is the source code of the Java Program to Check Whether Topological Sorting can be Performed in a Graph. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1.  
  2. package com.sanfoundry.graph;
  3.  
  4. import java.util.HashMap;
  5. import java.util.Iterator;
  6. import java.util.LinkedList;
  7. import java.util.List;
  8. import java.util.Map;
  9. import java.util.Scanner;
  10.  
  11. class GraphLinkedList
  12. {
  13.     private Map<Integer, List<Integer>> adjacencyList;
  14.  
  15.     public GraphLinkedList(int v)
  16.     {
  17.         adjacencyList = new HashMap<Integer, List<Integer>>();
  18.         for (int i = 1; i <= v; i++)
  19.             adjacencyList.put(i, new LinkedList<Integer>());
  20.     }
  21.  
  22.     public void setEdge(int from, int to)
  23.     {
  24.         if (to > adjacencyList.size() || from > adjacencyList.size())
  25.             System.out.println("The vertices does not exists");
  26.         /*
  27.          * List<Integer> sls = adjacencyList.get(to);
  28.          * sls.add(from);
  29.          */
  30.         List<Integer> dls = adjacencyList.get(from);
  31.         dls.add(to);
  32.     }
  33.  
  34.     public List<Integer> getEdge(int to)
  35.     {
  36.         if (to > adjacencyList.size())
  37.         {
  38.             System.out.println("The vertices does not exists");
  39.             return null;
  40.         }
  41.         return adjacencyList.get(to);
  42.     }
  43.  
  44.     public boolean checkDAG()
  45.     {
  46.         Integer count = 0;
  47.         Iterator<Integer> iteratorI = this.adjacencyList.keySet().iterator();
  48.         Integer size = this.adjacencyList.size() - 1;
  49.         while (iteratorI.hasNext())
  50.         {
  51.             Integer i = iteratorI.next();
  52.             List<Integer> adjList = this.adjacencyList.get(i);
  53.             if (count == size)
  54.             {
  55.                 return true;
  56.             }
  57.             if (adjList.size() == 0)
  58.             {
  59.                 count++;
  60.                 System.out.println("Target Node - " + i);
  61.                 Iterator<Integer> iteratorJ = this.adjacencyList.keySet()
  62.                         .iterator();
  63.                 while (iteratorJ.hasNext())
  64.                 {
  65.                     Integer j = iteratorJ.next();
  66.                     List<Integer> li = this.adjacencyList.get(j);
  67.                     if (li.contains(i))
  68.                     {
  69.                         li.remove(i);
  70.                         System.out.println("Deleting edge between target node "
  71.                                 + i + " - " + j + " ");
  72.                     }
  73.                 }
  74.                 this.adjacencyList.remove(i);
  75.                 iteratorI = this.adjacencyList.keySet().iterator();
  76.             }
  77.         }
  78.         return false;
  79.     }
  80.  
  81.     public void printGraph()
  82.     {
  83.         System.out.println("The Graph is: ");
  84.         for (int i = 1; i <= this.adjacencyList.size(); i++)
  85.         {
  86.             List<Integer> edgeList = this.getEdge(i);
  87.             if (edgeList.size() != 0)
  88.             {
  89.                 System.out.print(i);
  90.                 for (int j = 0; j < edgeList.size(); j++)
  91.                 {
  92.                     System.out.print(" -> " + edgeList.get(j));
  93.                 }
  94.                 System.out.println();
  95.             }
  96.         }
  97.     }
  98. }
  99.  
  100. public class TopologicalSortPossible
  101. {
  102.     public static void main(String args[])
  103.     {
  104.         int v, e, count = 1, to, from;
  105.         Scanner sc = new Scanner(System.in);
  106.         GraphLinkedList glist;
  107.         try
  108.         {
  109.             System.out.println("Enter the number of vertices: ");
  110.             v = sc.nextInt();
  111.             System.out.println("Enter the number of edges: ");
  112.             e = sc.nextInt();
  113.             glist = new GraphLinkedList(v);
  114.             System.out.println("Enter the edges in the graph : <from> <to>");
  115.             while (count <= e)
  116.             {
  117.                 to = sc.nextInt();
  118.                 from = sc.nextInt();
  119.                 glist.setEdge(to, from);
  120.                 count++;
  121.             }
  122.             glist.printGraph();
  123.             System.out
  124.                     .println("--Processing graph to check whether it is DAG--");
  125.             if (glist.checkDAG())
  126.             {
  127.                 System.out
  128.                         .println("Result: \nGiven graph is DAG (Directed Acyclic Graph).");
  129.             }
  130.             else
  131.             {
  132.                 System.out
  133.                         .println("Result: \nGiven graph is not DAG (Directed Acyclic Graph).");
  134.             }
  135.         }
  136.         catch (Exception E)
  137.         {
  138.             System.out
  139.                     .println("You are trying to access empty adjacency list of a node.");
  140.         }
  141.         sc.close();
  142.     }
  143. }

Output:

$ javac TopologicalSortPossible.java
$ java TopologicalSortPossible
 
Enter the number of vertices: 
6
Enter the number of edges: 
7
Enter the edges in the graph : <from> <to>
1 2
2 3
2 4
4 5
5 6
6 1
6 3
The Graph is: 
1 -> 2
2 -> 3 -> 4
4 -> 5
5 -> 6
6 -> 1 -> 3
--Processing graph to check whether it is DAG--
Target Node - 3
Deleting edge between target node 3 - 2 
Deleting edge between target node 3 - 6 
Result: 
Given graph is not DAG (Directed Acyclic Graph).
 
Enter the number of vertices: 
6
Enter the number of edges: 
7
Enter the edges in the graph : <from> <to>
1 2
2 3
2 4
4 5
4 6
5 6
6 3
The Graph is: 
1 -> 2
2 -> 3 -> 4
4 -> 5 -> 6
5 -> 6
6 -> 3
--Processing graph to check whether it is DAG--
Target Node - 3
Deleting edge between target node 3 - 2 
Deleting edge between target node 3 - 6 
Target Node - 6
Deleting edge between target node 6 - 4 
Deleting edge between target node 6 - 5 
Target Node - 5
Deleting edge between target node 5 - 4 
Target Node - 4
Deleting edge between target node 4 - 2 
Target Node - 2
Deleting edge between target node 2 - 1 
Result: 
Given graph is DAG (Directed Acyclic Graph).

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.