class TwoApproxMetricTSP implements TSPAlgorithm<V, E> {

    @Override
    public GraphPath<V, E> getTour(Graph<V, E> graph)
    {
        if (!graph.getType().isUndirected()) {
            throw new IllegalArgumentException("Graph must be undirected");
        }
        if (!GraphTests.isComplete(graph)) {
            throw new IllegalArgumentException("Graph is not complete");
        }
        if (graph.vertexSet().isEmpty()) {
            throw new IllegalArgumentException("Graph contains no vertices");
        }

        /*
         * Special case singleton vertex
         */
        if (graph.vertexSet().size() == 1) {
            V start = graph.vertexSet().iterator().next();
            return new GraphWalk<>(
                graph, start, start, Collections.singletonList(start), Collections.emptyList(), 0d);
        }

        /*
         * Create MST
         */
        Graph<V, DefaultEdge> mst = new SimpleGraph<>(DefaultEdge.class);
        for (V v : graph.vertexSet()) {
            mst.addVertex(v);
        }
        for (E e : new KruskalMinimumSpanningTree<>(graph).getSpanningTree().getEdges()) {
            mst.addEdge(graph.getEdgeSource(e), graph.getEdgeTarget(e));
        }

        /*
         * Perform a depth-first-search traversal
         */
        int n = graph.vertexSet().size();
        Set<V> found = new HashSet<>(n);
        List<V> tour = new ArrayList<>(n + 1);
        V start = graph.vertexSet().iterator().next();
        DepthFirstIterator<V, DefaultEdge> dfsIt = new DepthFirstIterator<>(mst, start);
        while (dfsIt.hasNext()) {
            V v = dfsIt.next();
            if (found.add(v)) {
                tour.add(v);
            }
        }
        // repeat the start vertex
        tour.add(start);

        /*
         * Explicitly build the path.
         */
        List<E> tourEdges = new ArrayList<E>(n);
        double tourWeight = 0d;
        Iterator<V> tourIt = tour.iterator();
        V u = tourIt.next();
        while (tourIt.hasNext()) {
            V v = tourIt.next();
            E e = graph.getEdge(u, v);
            tourEdges.add(e);
            tourWeight += graph.getEdgeWeight(e);
            u = v;
        }
        return new GraphWalk<>(graph, start, start, tour, tourEdges, tourWeight);
    }

    public  TwoApproxMetricTSP();

}