MetroMadridCPP

import org.jgrapht.Graph;
import org.jgrapht.GraphPath;
import org.jgrapht.alg.cycle.ChinesePostman;
import org.jgrapht.graph.*;

import java.io.*;
import java.util.*;

/**
 * Obtaining a closed walk of minimum length that visits every station of Metro Madrid at least once.
 *
 * @author Raúl Balanzá
 */
public final class MetroMadridCPP
{
    private MetroMadridCPP()
    { } // ensure non-instantiability.

    /**
     * Creates a graph model to represent Metro Madrid and executes the Chinese Postman Algorithm.
     *
     * @param args ignored.
     */
    public static void main(String[] args) throws FileNotFoundException
    {

        // Create the required graph
        Graph<String, DefaultWeightedEdge> metroMadridNetwork = createGraph();

        // Execute the Chinese Postman algorithm with complexity O(N^3), being N the number of vertices
        // It is guaranteed that the previously created graph is strongly connected
        ChinesePostman<String, DefaultWeightedEdge> cp = new ChinesePostman<>();
        GraphPath<String, DefaultWeightedEdge> path = cp.getCPPSolution(metroMadridNetwork);

        // Obtain total path cost
        double totalWeight = 0.0;
        List<DefaultWeightedEdge> edges = path.getEdgeList();

        for (DefaultWeightedEdge e : edges){ totalWeight += metroMadridNetwork.getEdgeWeight(e); }

        // Print the path
        System.out.println("Total weight is " + totalWeight + " minutes (approx.)");
        System.out.println("\nPath is: " + path.toString());

    }

    /**
     * Creates a non-directed and weighted graph that represents Metro Madrid's network.
     *
     * @return a graph based on String objects (names of stops).
     */
    private static Graph<String, DefaultWeightedEdge> createGraph() throws FileNotFoundException
    {
        Graph<String, DefaultWeightedEdge> g = new SimpleWeightedGraph(DefaultWeightedEdge.class);

        File f = new File("stops.txt");
        Scanner s = new Scanner(f);

        while (s.hasNextLine()){
            String name = s.nextLine();
            boolean added = g.addVertex(name);
            if (!added) System.err.println("ERROR: Duplicated vertex detected -> " + name);
        }

        System.out.println("Loaded " + g.vertexSet().size() + " vertices (stops)");

        f = new File("connections.txt");
        s = new Scanner(f);

        while (s.hasNextLine()){
            String [] edge = s.nextLine().split(",");
            addEdgeW(g, edge[0], edge[1], Double.parseDouble(edge[2]));
        }

        System.out.println("Loaded " + g.edgeSet().size() + " edges (connections)");

        return g;
    }

    private static void addEdgeW(Graph<String, DefaultWeightedEdge> g, String source, String dest, double weight){

        DefaultWeightedEdge e = g.addEdge(source, dest);
        if (e != null) g.setEdgeWeight(e, weight);
        else System.err.println("ERROR: Duplicated edge detected -> " + source + " <-> " + dest);

    }

}