class GraphWalk implements GraphPath<V, E> {

    public void verify()
    {

        if (isEmpty()) // Empty path
            return;

        if (vertexList != null && !vertexList.isEmpty()) {
            if (!startVertex.equals(vertexList.get(0)))
                throw new InvalidGraphWalkException(
                    "The start vertex must be the first vertex in the vertex list");
            if (!endVertex.equals(vertexList.get(vertexList.size() - 1)))
                throw new InvalidGraphWalkException(
                    "The end vertex must be the last vertex in the vertex list");
            // All vertices and edges in the path must be contained in the graph
            if (!graph.vertexSet().containsAll(vertexList))
                throw new InvalidGraphWalkException(
                    "Not all vertices in the path are contained in the graph");

            if (edgeList == null) {
                // Verify sequence
                Iterator<V> it = vertexList.iterator();
                V u = it.next();
                while (it.hasNext()) {
                    V v = it.next();
                    if (graph.getEdge(u, v) == null)
                        throw new InvalidGraphWalkException(
                            "The vertexList does not constitute to a feasible path. Edge (" + u
                                + "," + v + " does not exist in the graph.");
                    u = v;
                }
            }
        }

        if (edgeList != null && !edgeList.isEmpty()) {
            if (!Graphs.testIncidence(graph, edgeList.get(0), startVertex))
                throw new InvalidGraphWalkException(
                    "The first edge in the edge list must leave the start vertex");
            if (!graph.edgeSet().containsAll(edgeList))
                throw new InvalidGraphWalkException(
                    "Not all edges in the path are contained in the graph");

            if (vertexList == null) {
                V u = startVertex;
                for (E edge : edgeList) {
                    if (!Graphs.testIncidence(graph, edge, u))
                        throw new InvalidGraphWalkException(
                            "The edgeList does not constitute to a feasible path. Conflicting edge: "
                                + edge);
                    u = Graphs.getOppositeVertex(graph, edge, u);
                }
                if (!u.equals(endVertex))
                    throw new InvalidGraphWalkException(
                        "The path defined by the edgeList does not end in the endVertex.");
            }
        }

        if (vertexList != null && edgeList != null) {
            // Verify that the path is an actual path in the graph
            if (edgeList.size() + 1 != vertexList.size())
                throw new InvalidGraphWalkException(
                    "VertexList and edgeList do not correspond to the same path (cardinality of vertexList +1 must equal the cardinality of the edgeList)");

            for (int i = 0; i < vertexList.size() - 1; i++) {
                V u = vertexList.get(i);
                V v = vertexList.get(i + 1);
                E edge = getEdgeList().get(i);

                if (graph.getType().isDirected()) { // Directed graph
                    if (!graph.getEdgeSource(edge).equals(u)
                        || !graph.getEdgeTarget(edge).equals(v))
                        throw new InvalidGraphWalkException(
                            "VertexList and edgeList do not form a feasible path");
                } else { // Undirected or mixed
                    if (!Graphs.testIncidence(graph, edge, u)
                        || !Graphs.getOppositeVertex(graph, edge, u).equals(v))
                        throw new InvalidGraphWalkException(
                            "VertexList and edgeList do not form a feasible path");
                }
            }
        }
    }

    public  GraphWalk(Graph<V, E> graph, V startVertex, V endVertex, List<E> edgeList, double weight);
    public  GraphWalk(Graph<V, E> graph, List<V> vertexList, double weight);
    public  GraphWalk(
        Graph<V, E> graph, V startVertex, V endVertex, List<V> vertexList, List<E> edgeList,
        double weight);

}