raulbalanza

MetroMadridCPP

Jun 14th, 2020
98
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import org.jgrapht.Graph;
  2. import org.jgrapht.GraphPath;
  3. import org.jgrapht.alg.cycle.ChinesePostman;
  4. import org.jgrapht.graph.*;
  5.  
  6. import java.io.*;
  7. import java.util.*;
  8.  
  9. /**
  10.  * Obtaining a closed walk of minimum length that visits every station of Metro Madrid at least once.
  11.  *
  12.  * @author Raúl Balanzá
  13.  */
  14. public final class MetroMadridCPP
  15. {
  16.     private MetroMadridCPP()
  17.     { } // ensure non-instantiability.
  18.  
  19.     /**
  20.      * Creates a graph model to represent Metro Madrid and executes the Chinese Postman Algorithm.
  21.      *
  22.      * @param args ignored.
  23.      */
  24.     public static void main(String[] args) throws FileNotFoundException
  25.     {
  26.  
  27.         // Create the required graph
  28.         Graph<String, DefaultWeightedEdge> metroMadridNetwork = createGraph();
  29.  
  30.         // Execute the Chinese Postman algorithm with complexity O(N^3), being N the number of vertices
  31.         // It is guaranteed that the previously created graph is strongly connected
  32.         ChinesePostman<String, DefaultWeightedEdge> cp = new ChinesePostman<>();
  33.         GraphPath<String, DefaultWeightedEdge> path = cp.getCPPSolution(metroMadridNetwork);
  34.  
  35.         // Obtain total path cost
  36.         double totalWeight = 0.0;
  37.         List<DefaultWeightedEdge> edges = path.getEdgeList();
  38.  
  39.         for (DefaultWeightedEdge e : edges){ totalWeight += metroMadridNetwork.getEdgeWeight(e); }
  40.  
  41.         // Print the path
  42.         System.out.println("Total weight is " + totalWeight + " minutes (approx.)");
  43.         System.out.println("\nPath is: " + path.toString());
  44.  
  45.     }
  46.  
  47.     /**
  48.      * Creates a non-directed and weighted graph that represents Metro Madrid's network.
  49.      *
  50.      * @return a graph based on String objects (names of stops).
  51.      */
  52.     private static Graph<String, DefaultWeightedEdge> createGraph() throws FileNotFoundException
  53.     {
  54.         Graph<String, DefaultWeightedEdge> g = new SimpleWeightedGraph(DefaultWeightedEdge.class);
  55.  
  56.         File f = new File("stops.txt");
  57.         Scanner s = new Scanner(f);
  58.  
  59.         while (s.hasNextLine()){
  60.             String name = s.nextLine();
  61.             boolean added = g.addVertex(name);
  62.             if (!added) System.err.println("ERROR: Duplicated vertex detected -> " + name);
  63.         }
  64.  
  65.         System.out.println("Loaded " + g.vertexSet().size() + " vertices (stops)");
  66.  
  67.         f = new File("connections.txt");
  68.         s = new Scanner(f);
  69.  
  70.         while (s.hasNextLine()){
  71.             String [] edge = s.nextLine().split(",");
  72.             addEdgeW(g, edge[0], edge[1], Double.parseDouble(edge[2]));
  73.         }
  74.  
  75.         System.out.println("Loaded " + g.edgeSet().size() + " edges (connections)");
  76.  
  77.         return g;
  78.     }
  79.  
  80.     private static void addEdgeW(Graph<String, DefaultWeightedEdge> g, String source, String dest, double weight){
  81.  
  82.         DefaultWeightedEdge e = g.addEdge(source, dest);
  83.         if (e != null) g.setEdgeWeight(e, weight);
  84.         else System.err.println("ERROR: Duplicated edge detected -> " + source + " <-> " + dest);
  85.  
  86.     }
  87.  
  88. }
RAW Paste Data