Practice-It

Write a method named isCyclic that accepts a Graph<String, String> parameter and returns true if a path can be made from any vertex back to that same vertex (a cycle), or false if there are no cycles in the graph. To figure out whether a graph contains any cycles, use the following pseudo-code algorithm. (You will have to maintain the mapping of vertex to unvisited/partial/visited yourself.)

function isCyclic(graph):
    mark all vertices in the graph as UNVISITED.
    for each vertex v in the graph:
        if visit(graph, v) returns true, then the graph contains a cycle.
    if no vertex v returned true, the graph does not contain a cycle.

function visit(graph, v):
    mark v as being PARTIALLY VISITED.
    for each neighbor v2 of v:
        if v2 is PARTIALLY VISITED, then the graph contains a cycle.
        if v2 is UNVISITED:
            if visit(graph, v2) returns true, then the graph contains a cycle.
    mark v as FULLY VISITED.
    return false.

You are allowed to call methods on the graph but you should not modify its state. The graph passed to your method implements the following interface:

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();
}