/* Programmer: Sriram Pemmaraju. Oct 24th, 2007 */ import java.util.StringTokenizer; import java.util.Arrays; import java.io.*; public class City{ // Arrays to keep track of info. related to each city private String[] cityName; private String[] cityState; private int[] cityLat; private int[] cityLong; private int[] cityPop; // 2-D array to keep track of pairwise distances between cities private int[][] distances; // boolean 1-D array to keep track of selected cities private boolean[] currentCities; // boolean 2-D array to keep track of selected edges private boolean[][] currentEdges; // number of cities private static int numCities = 128; public City() { //Allotting the space for each 1-D array cityName = new String[numCities]; cityState = new String[numCities]; cityLat = new int[numCities]; cityLong = new int[numCities]; cityPop = new int[numCities]; currentCities = new boolean[numCities]; // Select all cities initially for(int i = 0; i < numCities; i++) currentCities[i] = true; // Allocate space for each 2-D array. These arrays have 0 elements in row 0, // 1 element in row 1, 2 elements in row 2, etc. distances = new int[numCities][]; currentEdges = new boolean[numCities][]; for(int i = 0; i < numCities; i++) { distances[i] = new int[i]; currentEdges[i] = new boolean[i]; // Select all edges initially for(int j = 0; j < i; j++) currentEdges[i][j] = true; } try{ // Construct a buffered reader object and connect it to the files "miles.dat" BufferedReader in = new BufferedReader(new FileReader("miles.dat")); // A counter that keeps track of the index of the current city being read int cityNumber = 0; // While-loop for reading in data from "miles.dat." At the beginning of the while-loop // the expectation is that we'll be reading a line containing the city name. Instead, // if we encounter a line that starts with "*" then we skip to the next line while(cityNumber < numCities) { // Read in a line String line = in.readLine(); // Skip the rest of the loop if line starts with a "*" if(line.charAt(0) == '*') continue; // Otherwise tokenize the line StringTokenizer tokenizedLine= new StringTokenizer(line, ",[]"); //Putting actual data into correct position in the array cityName[cityNumber] = tokenizedLine.nextToken(); cityState[cityNumber]= (tokenizedLine.nextToken()).trim(); // trim() gets rid of leading/trailing blanks cityLat[cityNumber] = Integer.parseInt(tokenizedLine.nextToken()); cityLong[cityNumber] = Integer.parseInt(tokenizedLine.nextToken()); cityPop[cityNumber] = Integer.parseInt(tokenizedLine.nextToken()); //while loop to put distances in the array; this may need to read several lines int mileNumber = 0; while (mileNumber < cityNumber) { // Read a mileage line and tokenize it String mileage = in.readLine(); StringTokenizer tokenizedMileage = new StringTokenizer(mileage, " "); // Read all the mileage data in this line into row cityNumber; increment // mileNumber after each read while(tokenizedMileage.hasMoreTokens()) { distances[cityNumber][cityNumber-mileNumber-1] = Integer.parseInt(tokenizedMileage.nextToken()); //distances[cityNumber][mileNumber] = Integer.parseInt(tokenizedMileage.nextToken()); mileNumber++; } } // end of while reading distances cityNumber++; } // end of while reading cities } // end of try catch (IOException e) {System.out.println("File not found.");} } // end of City() constructor // Constructs a String array of all distinct state names of selected cities String[] getStates() { String[] states = new String[numCities]; int count = 0; for(int i = 0; i < numCities; i++) states[count++] = cityState[i]; // Sort the states array Arrays.sort(states); // Get rid of duplicates and create a new String array with // only distinct states String[] distinctStates = new String[count]; int distinctCount = 0; String previousState = null; for(int i = 0; i < count; i++) if(!states[i].equals(previousState)) { distinctStates[distinctCount++] = states[i]; previousState = states[i]; } // Resize the distinctStates array so that it has exactly the right size String[] newDistinctStates = new String[distinctCount]; for(int i = 0; i < distinctCount; i++) newDistinctStates[i] = distinctStates[i]; return newDistinctStates; } // Selects all cities void selectAllCities() { for(int i = 0; i < numCities; i++) currentCities[i] = true; } // Unselects all cities void unselectAllCities() { for(int i = 0; i < numCities; i++) currentCities[i] = false; } // Select cities: This version of the method allows us to select cities by name or by state name // This method only selects from among those cities that have already been selected void selectCities(String attribute, String lowerBound, String upperBound) { if(attribute.equals("name")) { // Scan all cities and unselect those select cities whose latitude is out of bounds for(int i = 0; i < numCities; i++) if((currentCities[i])&&((cityName[i].compareTo(lowerBound) < 0) || (cityName[i].compareTo(upperBound) > 0))) currentCities[i] = false; } if(attribute.equals("state")) { // Scan all cities and unselect those select cities whose latitude is out of bounds for(int i = 0; i < numCities; i++) if((currentCities[i])&&((cityState[i].compareTo(lowerBound) < 0) || (cityState[i].compareTo(upperBound) > 0))) currentCities[i] = false; } } // Select cities: This version of the method allows us to select cities by latitude or longitude // This method only selects from among those cities that have already been selected void selectCities(String attribute, int lowerBound, int upperBound) { if(attribute.equals("latitude")) { // Scan all cities and unselect those select cities whose latitude is out of bounds for(int i = 0; i < numCities; i++) if((currentCities[i])&&((cityLat[i] < lowerBound) || (cityLat[i] > upperBound))) currentCities[i] = false; } if(attribute.equals("longitude")) { // Scan all cities and unselect those select cities whose latitude is out of bounds for(int i = 0; i < numCities; i++) if((currentCities[i])&&((cityLong[i] < lowerBound) || (cityLong[i] > upperBound))) currentCities[i] = false; } if(attribute.equals("population")) { // Scan all cities and unselect those select cities whose latitude is out of bounds for(int i = 0; i < numCities; i++) if((currentCities[i])&&((cityPop[i] < lowerBound) || (cityPop[i] > upperBound))) currentCities[i] = false; } } // Selects edges whose distance lies in-between the specified lower and upper bounds, // inclusive of the bounds. This function pays no attention to past edge selections void selectEdges(int lowerBound, int upperBound) { for(int i = 0; i < numCities; i++) for(int j = 0; j < i; j++) if((distances[i][j] >= lowerBound) && (distances[i][j] <= upperBound)) currentEdges[i][j] = true; else currentEdges[i][j] = false; } // Constructs and returns a graph whose vertices are the set of selected cities and whose // edges are selected edges that connected pairs of selected cities myWeightedGraph makeGraph() { // Create an empty graph myWeightedGraph g = new myWeightedGraph(); // Add all selected cities to it for(int i = 0; i < numCities; i++) if(currentCities[i]) g.addVertex(cityName[i]+" "+cityState[i]); // Add all selected edges between pairs of selected cities for(int i = 0; i < numCities; i++) for(int j = 0; j < i; j++) if((currentEdges[i][j]) && (currentCities[i]) && (currentCities[j])) g.addEdge(cityName[i]+" "+cityState[i], cityName[j]+" "+cityState[j], distances[i][j]); // return the constructed graph return g; } // Prints the selected cities void printCities() { // Scan the list of all cities and print out those that are selected for(int i = 0; i < numCities; i++) if(currentCities[i]) System.out.println(cityName[i]+" "+cityState[i]); } // Gets the populations of selected cities in an int array int[] getPopulations() { // First count the number of selected cities int count = 0; for(int i = 0; i < numCities; i++) if(currentCities[i]) count++; // Use this count to define an array of the correct size to hold the // populations int[] popArray = new int[count]; // Fill this array with the populations of the selected cities count = 0; for(int i = 0; i < numCities; i++) if(currentCities[i]) popArray[count++] = cityPop[i]; return popArray; } // A simple getIndex method to help test the constructor int getIndex(String city, String state) { int location; for(location = 0; location < numCities; location++) if((cityName[location].equals(city)) && (cityState[location].equals(state))) return location; return -1; } // Print information about a city, given a city index void printCityInfo(int index) { System.out.println(cityName[index] + " " + cityState[index] + " " + cityLat[index] + " " + cityLong[index] + " " + cityPop[index]); } // Print distance information between a given pair of cities void printDistanceInfo(int i, int j) { if(i < j) System.out.println(distances[j][i]); else System.out.println(distances[i][j]); } // Returns the array of selected cities: each city, identified by its index int[] getSelectedCities() { int count = 0; // keeps track of the number of selected cities // First count the number of selected cities for(int i = 0; i < numCities; i++) if(currentCities[i]) count++; // Allocate just enough space to store this many cities int[] selectedCities = new int[count]; // Pick out the selected cities (and their states) and store in the array count = 0; for(int i = 0; i < numCities; i++) if(currentCities[i]) selectedCities[count++] = i; return selectedCities; } // Returns the array of unselected cities: each city, identified by its index int[] getUnSelectedCities() { int count = 0; // keeps track of the number of unselected cities // First count the number of unselected cities for(int i = 0; i < numCities; i++) if(!currentCities[i]) count++; // Allocate just enough space to store this many cities int[] unselectedCities = new int[count]; // Pick out the selected cities (and their states) and store in the array count = 0; for(int i = 0; i < numCities; i++) if(!currentCities[i]) unselectedCities[count++] = i; return unselectedCities; } // Returns the distance between a pair of cities, each city identified by its index int getDistance(int sourceCityIndex, int destCityIndex) { if(sourceCityIndex == destCityIndex) return 0; if(sourceCityIndex < destCityIndex) return distances[destCityIndex][sourceCityIndex]; else return distances[sourceCityIndex][destCityIndex]; } // Returns the name of a city, given its index String getCity(int i) { return cityName[i]; } // Returns the name of the state of a city whose index is given String getState(int i) { return cityState[i]; } //Main method public static void main(String[] args) { City newCity = new City(); myWeightedGraph g, h; String[] path; System.out.println("---------------------------------------------------------------------------------------"); System.out.println("EXPERIMENT 1: This is just a test"); System.out.println("Computes and prints the MST of all 128 cities."); newCity.selectAllCities(); g = newCity.makeGraph(); h = g.MSTGraph(); h.printEdges(); System.out.println("The cost of this MST is " + g.costMST()); System.out.println("---------------------------------------------------------------------------------------"); System.out.println("---------------------------------------------------------------------------------------"); System.out.println("EXPERIMENT 2. This is just a test."); System.out.println("Computes and prints a greedy TSP of all 128 cities."); newCity.selectAllCities(); g = newCity.makeGraph(); g.printGreedyTSP(); System.out.println("The cost of this TSP is " + g.costGreedyTSP()); System.out.println("---------------------------------------------------------------------------------------"); System.out.println("---------------------------------------------------------------------------------------"); System.out.println("EXPERIMENT 3: This is just a test."); // Select cities in the upper midwest newCity.selectCities("latitude", 4000, 5000); newCity.selectCities("longitude", 8500, 10000); // Print these out System.out.println("Cities in the upper mid-west 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 upper midwest is " + g.costMST()); System.out.println("A Greedy TSP of these cities is:"); g.printGreedyTSP(); System.out.println("The cost of this TSP is " + g.costGreedyTSP()); System.out.println("---------------------------------------------------------------------------------------"); } }