Add a topological sort to the Graph/Vertex classes provided. Calculate the Big-O notation for this method.

import java.util.LinkedList; import java.util.Map; import java.util.PriorityQueue; import java.util.Queue; import java.util.TreeMap; public class Graph { private TreeMap graph; public Graph() { graph = new TreeMap<>(); } public void addEdge(String v1, String v2, Integer w) { //ensure vertex exist in graph addVertex(v1); addVertex(v2); //get vertex object from graph for v1, add an adjacent edge to v2 graph.get(v1).addEdge(v2, w); } public void addEdge(String v1, String v2) { addEdge(v1, v2, 1); } public void addEdgeUndirected(String v1, String v2, Integer w) { //ensure vertex exist in graph addVertex(v1); addVertex(v2); //get vertex object from graph for v1, add an adjacent edge to v2 graph.get(v1).addEdge(v2, w); graph.get(v2).addEdge(v1, w); } public void addEdgeUndirected(String v1, String v2) { addEdgeUndirected(v1, v2, 1); } private void addVertex(String v) { if(!graph.containsKey(v)) { graph.put(v, new Vertex(v)); } } public String toString() { String output = ""; for(Map.Entry e : graph.entrySet()) { output += e.getValue()+" "; } return output; } public void printPath(String vs, String ve, String type) { if(graph.containsKey(vs) && graph.containsKey(ve)) { System.out.println(type.toUpperCase()); Vertex s = graph.get(vs); if(type.toLowerCase().equals("unweighted")) { unweighted(s); } else if(type.toLowerCase().equals("weighted")) { weighted(s); } else if(type.toLowerCase().equals("negative")) { negative(s); } Vertex e = graph.get(ve); /* * Pseudocode if(e.dist != INFINITY){ String path = ""; Vertex curr = e; while(curr.path != null){ path += curr; curr = curr.path; } path = s + path; print(path) print(dist) }else{ print("can not reach end"); } */ if(e.dist != Integer.MAX_VALUE) { String path = ""; Vertex curr = e; while(curr.path != null){ path = curr.getName()+", " + path; curr = curr.path; } path = s.getName()+", " + path; System.out.println(path); System.out.println(e.dist); } else { System.out.println("can not reach end"); } } } public void unweighted(Vertex s) { /* * Pseudocode from textbook PG 372 Queue q = new Queue(); for each Vertex v{ v.dist = INFINITY; v.path = null;//added to make sure we clear the path between runs of pathing methods } s.dist = 0; q.enqueue(s); while(!q.isEmpty()){ Vertex v = q.dequeue(); for each Vertex w adjacent to v{ if(w.dist == INFINITY){ w.dist = v.dist + 1; w.path = v; q.enqueue(w); } } } */ Queue q = new LinkedList<>(); for(Map.Entry e : graph.entrySet()) { Vertex v = e.getValue(); v.dist = Integer.MAX_VALUE;//max int is around 2 billion, basically Infinity v.path = null; } s.dist = 0; q.offer(s); while(!q.isEmpty()) { Vertex v = q.poll(); for(Map.Entry temp : v.adjacent.entrySet()) { Vertex w = graph.get(temp.getKey()); if(w.dist == Integer.MAX_VALUE){ w.dist = v.dist + 1; w.path = v; q.offer(w); } } } } public void weighted(Vertex s) { /* * Pseudocode PriorityQueue q = new PriorityQueue(); //implement Comparable based on distance for PriorityQueue for each Vertex v{ v.dist = INFINITY; v.path = null;//added to make sure we clear the path between runs of pathing methods v.known = false; } s.dist = 0; q.enqueue(s); while(!q.isEmpty()){ Vertex v = q.dequeue();//smallest distance in queue v.known = true; for each Vertex w adjacent to v{ if(w.dist > v.dist + w.weight){ w.dist = v.dist + w.weight; w.path = v; } if(!w.known){ q.enqueue(w); } } } */ PriorityQueue q = new PriorityQueue<>(); for(Map.Entry e : graph.entrySet()) { Vertex v = e.getValue(); v.dist = Integer.MAX_VALUE;//max int is around 2 billion, basically Infinity v.path = null; v.known = false; } s.dist = 0; q.offer(s); while(!q.isEmpty()) { Vertex v = q.poll(); v.known = true; for(Map.Entry temp : v.adjacent.entrySet()) { Vertex w = graph.get(temp.getKey()); Integer weight = temp.getValue(); if(w.dist > v.dist + weight){ w.dist = v.dist + weight; w.path = v; } if(!w.known){ q.offer(w); } } } } public void negative(Vertex s) { /* * Pseudocode Queue q = new Queue(); for each Vertex v{ v.dist = INFINITY; v.path = null;//added to make sure we clear the path between runs of pathing methods } s.dist = 0; q.enqueue(s); while(!q.isEmpty()){ Vertex v = q.dequeue(); for each Vertex w adjacent to v{ if(w.dist > v.dist + w.weight){ w.dist = v.dist + w.weight; w.path = v; if(!q.contains(w)){ q.enqueue(w); } } } } */ Queue q = new LinkedList<>(); for(Map.Entry e : graph.entrySet()) { Vertex v = e.getValue(); v.dist = Integer.MAX_VALUE;//max int is around 2 billion, basically Infinity v.path = null; } s.dist = 0; q.offer(s); while(!q.isEmpty()) { Vertex v = q.poll(); for(Map.Entry temp : v.adjacent.entrySet()) { Vertex w = graph.get(temp.getKey()); Integer weight = temp.getValue(); if(w.dist > v.dist + weight){ w.dist = v.dist + weight; w.path = v; if(!q.contains(w)){ q.offer(w); } } } } } public void printMaxDistance() { int maxDist = 0; String vert = ""; for(Map.Entry vertex : graph.entrySet()) if(vertex.getValue().dist != Integer.MAX_VALUE && vertex.getValue().dist > maxDist) { maxDist = vertex.getValue().dist; vert = vertex.getKey(); } System.out.println("MAX:"+vert+":"+maxDist); } } ___________________________________________________________

import java.util.Map; import java.util.TreeMap; public class Vertex implements Comparable { private String name; public TreeMap adjacent; public Integer dist; public Vertex path; public boolean known; public Vertex(String n) { name = n; adjacent = new TreeMap<>(); } public void addEdge(String e, Integer i) { adjacent.put(e, i);//will overwrite existing edge with same name } public void addEdge(String e) { addEdge(e, 1);//use weight of 1 for unweighted } public String getName() { return name; } public TreeMap getAdjacent() { return adjacent; } public String toString() { String output = "Name:"+name+" Dist:"+dist; output += " Adjacent List:"; for(Map.Entry e :adjacent.entrySet()) { output += ","+e.getKey()+":"+e.getValue(); } return output; } @Override public int compareTo(Vertex arg0) { return dist.compareTo(arg0.dist); } }