Practice-It

Write a method isValidBidiPath that accepts two parameters: a Graph<String, String>, and a List of vertices representing a path, and returns true if that path is an actual valid bi-directional path that can be traveled in the graph in both directions, or false if not. A valid bi-directional path is a path where every vertex in the path is found in the graph, and where there is an edge between each neighboring pair of vertices in the path along the way from start to end, and also back from the end to the start.

For example, if your method were passed given the graph below and the path [A, B, F, G], you would return true because all of those vertices are part of the graph and you can travel that path from A to G and back from G to A. If you were passed the same graph and the path [A, E, F, I], you would return false because that path does not go back from I to A. If you were passed the path [A, X, Z, B], you would return false because X and Z are not in the graph. You should not construct any auxiliary data structures while solving this problem, but you can construct as many simple variables as you like. You should not modify the state of the graph passed in. You may assume that the graph, the path, and the path's elements are not null.

A <---> B <---> C
|       ^       |
|       |       |
|       |       |
v       v       v
E ----> F <---> G
|       |
|       |
|       |
v       v
H <---- I

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