/* Programmer: Sriram Pemmaraju. Nov 24th, 2007

*/
import java.io.*;

public class CityTester4{

	//Main method
	public static void main(String[] args) {
		City newCity = new City();
		myWeightedGraph g, h;
		String[] path;

		System.out.println("---------------------------------------------------------------------------------------");
		System.out.println("EXPERIMENT 4.");
		// Select cities with high population 
		newCity.selectCities("population", 200000, Integer.MAX_VALUE);
		// Print these out
		System.out.println("Cities with population, at least 200,000 are:");
		newCity.printCities();
		System.out.println(" ");
		System.out.println("The MST of these cities is:");
		g = newCity.makeGraph();
		h = g.MSTGraph();
		h.printEdges();
		System.out.println("The cost of the MST of the high population cities is " + g.costMST());

		int[] hubs = newCity.getSelectedCities(); // these are the high population cities
		int[] spokes = newCity.getUnSelectedCities(); // these are the low population cities

		System.out.println("Connecting the spokes to the hubs...");
		// Scan each spoke and find the hub closest to it
		// Then add to the graph h, the edge between the spoke and the closest hub
		for(int i = 0; i < spokes.length; i++)
		{
			int minDistance = Integer.MAX_VALUE;
			int bestHub = -1;
			
			for(int j = 0; j < hubs.length; j++)
			{
				if(newCity.getDistance(spokes[i], hubs[j]) < minDistance)
				{
					minDistance = newCity.getDistance(spokes[i], hubs[j]);		
					bestHub = hubs[j];
				}
			}

			String city1 = newCity.getCity(spokes[i]) + " " + newCity.getState(spokes[i]);
			String city2 = newCity.getCity(bestHub) + " " + newCity.getState(bestHub);
		
			System.out.println("Connecting spoke " + city1 + " to hub " + city2);

			h.addVertex(city1);
			h.addEdge(city1, city2, newCity.getDistance(spokes[i], bestHub));

		}

		// Now h is a spanning tree of g
		System.out.println("Number of cities visited by the airline " + h.numberOfVertices());
		System.out.println("Number of routes used the airline " + h.numberOfEdges());
		System.out.println("Average number of airline routes that visit a city is " + h.averageDegree());
		System.out.println("Minimum number of airline routes that visit a city is " + h.minimumDegree());
		System.out.println("Maximum number of airline routes that visit a city is " + h.maximumDegree());
		System.out.println("Average number of hops to get from one city to another is " + h.averagePathLength());


		System.out.println("---------------------------------------------------------------------------------------");





	}
}