Write the program to show the ordering of vertices produced

Write the program to show the ordering of vertices produced by topological ordering when it is run on the following graph. Assume that the DFS procedure considers the vertices in alphabetical order, and assume that each adjacency list is ordered alphabetically.

Solution

The Java Program and the Input File

--------------------------------------------------------------------------------------------------------------------------------------------------------------------

package feb;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.TreeMap;

public class Chegg_7_2_2017_1 {

   public static void topologicalSort(Graph g) {
       Set<Character> visited = new HashSet<>();
       Stack<Node> sol = new Stack<>();

       for (Entry<Character, Node> e : g.nodeMap.entrySet()) {
           if (!visited.contains(e.getKey())) {
               topologicalSort(g, e.getValue(), visited, sol);
           }
       }
       // Printing the Final Solution
       while (!sol.isEmpty()) {
           System.out.print(sol.pop().symbol + \"->\");
       }
   }

   public static void topologicalSort(Graph g, Node parent, Set<Character> visited, Stack<Node> sol) {

       visited.add(parent.symbol);

       for (Node child : g.nodeMap.get(parent.symbol).adjList) {
           if (!visited.contains(child.symbol)) {
               topologicalSort(g, child, visited, sol);
           }
       }
       sol.add(parent);
   }

   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       Graph g = new Graph();
       int choice;
       boolean flag = true;
       while (flag) {
           System.out.println(\"1.Add Node(u) 2.Link Node(u->v) 3:Exit\");
           choice = Integer.parseInt(sc.nextLine());
           switch (choice) {
           case 1:
               System.out.println(\"Node Symbol = \");
               char c = sc.nextLine().charAt(0);
               g.nodeMap.put(c, new Node(c));
               break;
           case 2:
               System.out.println(\"Enter source/From = \");
               char u = sc.nextLine().charAt(0);
               System.out.println(\"Enter Destination/to = \");
               char v = sc.nextLine().charAt(0);
               if (!g.nodeMap.containsKey(u)) {
                   g.nodeMap.put(u, new Node(u));
               }
               if (!g.nodeMap.containsKey(v)) {
                   g.nodeMap.put(v, new Node(v));
               }

               g.nodeMap.get(u).adjList.add(g.nodeMap.get(v));
               break;
           case 3:
               flag = false;
               break;
           }
       }
       System.out.println(\"--------------------- Topological Order Is\");
       topologicalSort(g);
       sc.close();
   }
}

class Graph {
   Map<Character, Node> nodeMap;

   public Graph() {
       this.nodeMap = new TreeMap<>(new Comparator<Character>() {
           @Override
           public int compare(Character o1, Character o2) {
               // TODO Auto-generated method stub
               return o1 - o2;
           }
       });
   }
}

class Node {
   char symbol;
   List<Node> adjList;

   Node(char symbol) {
       this.symbol = symbol;
       this.adjList = new ArrayList<Node>();
   }
}

---------------------------------------------------------------------------------------------------------------------------------------- INPUT FILE

1
m
2
m
q
2
m
x
2
m
r
2
n
q
2
n
u
2
q
t
2
u
t
2
r
u
2
r
y
2
n
o
2
o
r
2
o
s
2
p
o
2
p
s
2
v
w
2
v
x
2
y
v
2
w
z
2
p