Implement methods for the cycle detection and the topological sort algorithms for the digraph Java generic Digraph.java. Then, using your modified generic, build a Java application that advises a UD student in which order to take courses in their major (e.g., Computer Science).

Your program should first build a digraph with each course and its pre-requisites. Your program should then display the courses in topological order, as long as the digraph has no cycles.

Digraph.java

// Digraph.java import java.util.*; /** * Digraph generic based on adjacency list representation * * @param E vertex (node) type parameter * * @author nbashias1@udayton.edu */ public class Digraph { private Map> lists; // adjacency list: map of ArrayLists of Vertices public Digraph() { lists = new HashMap>(); } /* * add the vertex (and its new list) to the lists, * if it's not already there * indicates if vertex actually added (if not already there) */ public boolean addVertex(E vertex) { if (!lists.containsKey(vertex)) { ArrayList vList = new ArrayList(); lists.put(vertex, vList); return true; } return false; } /* * uniquely add the arc from vertex1 to vertex2 */ public void addArc(E vertex1, E vertex2) { ArrayList vList1 = lists.get(vertex1); if (vList1 != null) { if (!vList1.contains(vertex2)) { vList1.add(vertex2); } } } /* * add the arc by adding the 2nd vertex to the 1st vertex's * adjacency list */ public void addMultiArc(E vertex1, E vertex2) { ArrayList vList1 = lists.get(vertex1); if (vList1 != null) { vList1.add(vertex2); } } /* * retrieve the graph vertices as a set */ public Set getVertices() { return lists.keySet(); } /* * return the digraph (adjacency list) in format: * * node1 -> node2, node3, ... * node2 -> node4, node5, ... * ... */ @Override public String toString() { StringBuilder sb = new StringBuilder(); Set vertexSet = lists.keySet(); for (E vertex : vertexSet) { sb.append(vertex.toString()); sb.append(" -> "); ArrayList nextList = lists.get(vertex); for (E vertex2 : nextList) { sb.append(vertex2.toString()); sb.append(", "); } sb.append(" "); } return sb.toString(); } private Set visited = null; // set of visited (marked) nodes private StringBuilder dft = null; // result of dft /* * recursive depth-first traversal on given source node (start) */ private void dft(E source) { visited.add(source); dft.append(source); dft.append("; "); ArrayList adjList = lists.get(source); for (E adjNode : adjList) { if (!visited.contains(adjNode)) { dft(adjNode); } } } // end dft(E) /* * recursive depth-first traversal (dft) on the entire digraph * perform a dft for each unvisited vertex */ public String dft() { visited = new HashSet(); StringBuilder sb = new StringBuilder(); for (E vertex : lists.keySet()) { if (!visited.contains(vertex)) { sb.append("dfs("); sb.append(vertex.toString()); sb.append("): "); dft = new StringBuilder(); dft(vertex); sb.append(dft.toString()); sb.append(" "); } } return sb.toString(); } // end dft /* * (non-recursive) breadth-first traversal */ public String bft(E start) { Queue queue = new LinkedList(); StringBuilder result = new StringBuilder(); visited = new HashSet(); queue.add(start); while (!queue.isEmpty()) { E current = queue.remove(); visited.add(current); result.append(current); result.append("; "); ArrayList currentList = lists.get(current); for (E next : currentList) { if (!visited.contains(next) && !queue.contains(next)) { queue.add(next); } } } return result.toString(); } // end bft } // end class Digraph 

Finding Cycles

You can implement the following algorithms as overloaded methods in the Digraph class to determine whether the digraph has a cycle:

let vStack be a global Stack variable let visited be a global Set variable (already declared in Digraph.java) // is there a cycle in the digraph starting at any vertex? Algorithm hasCycle(): for each vertex nextVertex in the digraph: let vStack be a new Stack let visited by a new Set if (hasCycle(nextVertex)): return true end if end for loop return false end hasCycle()

// is there a cycle in the digraph starting from the given vertex? Algorithm hasCycle(vertex v): let result be a boolean variable, initialized to false vStack.push(v) visited.add(v) for each vertex w adjacent to v: if (visited.contains(w) && vStack.contains(w)): result = true; else if (!visited.contains(w)): result = hasCycle(w) end if end for vStack.pop(); // remove v return result end hasCycle(v)