Practice-It

Write a method named topologicalSort that could be added to the SearchableGraph class, that returns a List of vertices representing a topological sort of the graph. (Note that this problem is asking you to add a method to SearchableGraph that would be placed inside the graph class itself, not an external method that accepts a graph as a parameter.)

Recall that a topological sort ordering is an arrangement of the vertices such that for every directed edge (v, w), vertex v appears before vertex w in the list. So for the graph in the diagram below, one valid order to return would be the list [B, A, C, D, E, F]. Another valid order would be [A, B, D, C, F, E]. The exact order of the list you return does not matter as long as it satisfies the topological sort property described previously. If the graph does not have any valid topological sort orderings, your method should return null. If the graph is empty, return an empty list. If the graph contains only a single vertex, return a list containing only that vertex.

       B ---> C ----+
       |      |     |
       |      |     |
       |      v     v
       |      E     F
       |      ^     ^
       |      |     |
       v      |     |
A ---> D -----+     |
       |            |
       +------------+

You should not modify the contents of the graph (such as by adding or removing vertices or edges from the graph). A solution that does so can receive partial credit but will receive a significant deduction. You may assume that the graph and its vertices are not null. You may construct auxiliary collections as needed to solve this problem. Recall that the SearchableGraph class has the following methods that you may call as needed to solve the problem:

public interface Graph<V, E> {
    public void addEdge(V v1, V v2);
    public void addEdge(V v1, V v2, E e);
    public void addEdge(V v1, V v2, int weight);
    public void addEdge(V v1, V v2, E e, int weight);
    public void addVertex(V v);
    public void clear();
    public void clearEdges();
    public boolean containsEdge(E e);
    public boolean containsEdge(V v1, V v2);
    public boolean containsPath(List<V> path);
    public boolean containsVertex(V v);
    public int cost(List<V> path);
    public int degree(V v);
    public E edge(V v1, V v2);
    public int edgeCount();
    public Collection<E> edges();
    public int edgeWeight(V v1, V v2);
    public int inDegree(V v);
    public Set<V> inverseNeighbors(V v);
    public boolean isDirected();
    public boolean isEmpty();
    public boolean isReachable(V v1, V v2);         // depth-first search
    public boolean isWeighted();
    public List<V> minimumWeightPath(V v1, V v2);   // Dijkstra's algorithm
    public Set<V> neighbors(V v);
    public int outDegree(V v);
    public void removeEdge(E e);
    public void removeEdge(V v1, V v2);
    public void removeVertex(V v);
    public List<V> shortestPath(V v1, V v2);        // breadth-first search
    public String toString();
    public int vertexCount();
    public Set<V> vertices();
}