import java.util.*; public class myWeightedGraph { protected String[] names; // 1-d array to store the vertices protected EdgeLinkList[] Edges; // 1-d array to store adjacencies between vertices, protected int numVertices; protected int numEdges; // Default constructor. Sets aside enough capacity for one vertex public myWeightedGraph( ) { this(1); } // Constructor that sets aside as much capacity as specified by the user public myWeightedGraph(int capacity) { names = new String[capacity]; Edges = new EdgeLinkList[capacity]; for (int i = 0 ; i < capacity ; i ++) { Edges[i] = new EdgeLinkList(); } } public int numberOfVertices() { return numVertices; } public int numberOfEdges() { return numEdges; } // Finds the location at which a vertex is stored in Vertices. // Returns -1 if vertex not found public int getIndex(String vertex) { for(int i = 0; i < numVertices; i++) if(vertex.equals(names[i])) return i; return -1; } // Resizes the array of vertices. Can make it larger or smaller, depending // on what newSize is. protected String[] resize(String[] array, int newSize) { String[] temp = new String[newSize]; int smallerSize = newSize; if(array.length < smallerSize) smallerSize = array.length; for(int i = 0; i < smallerSize; i++) temp[i] = array[i]; return temp; } // Resizes the array of Edges. Can make it larger or smaller, depending // on what newSize is. protected EdgeLinkList[] resize (EdgeLinkList[] array, int newSize) { EdgeLinkList[] temp = new EdgeLinkList[newSize]; int smallerSize = newSize; if(array.length < smallerSize) smallerSize = array.length; for(int i = 0; i < smallerSize; i++) temp[i] = array[i]; for (int i = smallerSize ; i < temp.length ; i ++) temp [i] = new EdgeLinkList(); return temp; } // Adds a new vertex public void addVertex(String newVertex) { if(getIndex(newVertex) != -1) { System.out.print("addVertex: "); System.out.print(newVertex); System.out.println(" failed -- vertex already exists."); return; } // if array of vertices is full, we need to expand it and // also expand Edges if (names.length == numVertices) { names = resize(names, 2*numVertices+1); Edges = resize(Edges, 2*numVertices+1); } names[numVertices++] = newVertex; } // Adds a new edge with default weight 1.0 // The endpoints of the edge are specified by indices public void addEdge(int i, int j) { addEdge(i, j, 1.0); } // Adds a new edge with default weight 1.0 public void addEdge(String vertex1, String vertex2) { addEdge(vertex1, vertex2, 1.0); } // Adds a new edge with weight w. The edge is specified by // indices of endpoints public void addEdge(int i, int j, double w) { if((i < 0) || (i > numVertices-1)) { System.out.print("addEdge failed: "); System.out.print("index " + i); System.out.println(" is out of bounds."); return; } if((j < 0) || (j > numVertices-1)) { System.out.print("addEdge failed: "); System.out.print("index " + j); System.out.println(" is out of bounds."); return; } Edges[i].insertFirst(names[j], w); Edges[j].insertFirst(names[i], w); numEdges++; } // Adds a new edge with weight w public void addEdge(String vertex1, String vertex2, double w) { int i = getIndex(vertex1); if(i == -1) { System.out.print("addEdge failed: "); System.out.print(vertex1); System.out.println(" does not exist."); return; } int j = getIndex(vertex2); if(j == -1) { System.out.print("addEdge failed: "); System.out.print(vertex2); System.out.println(" does not exist."); return; } addEdge(i, j, w); } // Prints the neighbors of the given vertex public void printAdjacencyList (String vertex) { int i = getIndex(vertex); if(i == -1) { System.out.print("addEdge failed: "); System.out.print(vertex); System.out.println(" does not exist."); return; } System.out.print (vertex + " is connected to "); Edges [i].displayList(); } // Prints all the edges of a graph public void printEdges() { for(int i = 0; i < numVertices; i++) { int[] nbrs = getNeighbors(i); for(int j = 0; j < nbrs.length; j++) System.out.println(names[i] + " " + names[nbrs[j]]); } } // returns the names of all the neighbors of a given vertex in a // String array public String[] getNeighbors(String vertex) { int source = getIndex(vertex); if(source == -1) { System.out.print("getNeighbors failed: Vertex "); System.out.print(vertex); System.out.println(" does not exist."); return null; } return Edges[source].copyIntoArray(); } // returns the indices of all the neighbors of a given vertex. The // vertex is specified as an index and the neighbors are returned // in an int array public int[] getNeighbors(int index) { if((index < 0) || (index >= numVertices)) { System.out.print("getNeighbors failed: Index"); System.out.print(index); System.out.println(" is out of bounds."); return null; } // Call the earlier getNeighbors function to get the names of // neighbors String[] nbrNames = getNeighbors(names[index]); // Turn the array of neighbor names into an array // of neighbor indices int[] nbrIndices = new int[nbrNames.length]; for(int i = 0; i < nbrIndices.length; i++) nbrIndices[i] = getIndex(nbrNames[i]); return nbrIndices; } // returns the degree of a vertex with given name public int degree(String vertex) { // Get the index of the vertex int i = getIndex(vertex); if(i == -1) { System.out.print("In degree: "); System.out.print(vertex); System.out.println(" does not exist."); return -1; } // Call the other degree function that returns the degree // of a vertex, given its index return degree(i); } // returns the degree of a vertex with given index public int degree(int index) { return Edges[index].size(); } // Gets the weight of the edge connecting a pair of vertices // whose indices are given public Double getWeight(int i, int j) { if((i < 0) || (i > numVertices-1)) { System.out.print("getWeight failed: "); System.out.print("index " + i); System.out.println(" out of bounds."); return null; } if((j < 0) || (j > numVertices-1)) { System.out.print("getWeight failed: "); System.out.print("index " + j); System.out.println(" out of bounds."); return null; } // Look for vertex j in Edges[i] //System.out.println("Looking for " + names[j] + " in linked list " + i); EdgeLink e = Edges[i].find(names[j]); // If vertex j is found in Edges[i] then return the weight of // the edge, otherwise return null if(e != null) return new Double(e.weight); else return null; } // Gets the weight of the edge connecting a pair of vertices // whose names are given public Double getWeight(String vertex1, String vertex2) { int i = getIndex(vertex1); if(i == -1) { System.out.print("getWeight failed: "); System.out.print(vertex1); System.out.println(" does not exist."); return null; } int j = getIndex(vertex2); if(j == -1) { System.out.print("getWeight failed: "); System.out.print(vertex2); System.out.println(" does not exist."); return null; } return getWeight(i, j); } // Boolean method that tells us if {i, j} is an edge in the graph public boolean isEdge(int i, int j) { if((i < 0) || (i > numVertices-1)) { System.out.print("isEdge failed: "); System.out.print("index " + i); System.out.println(" is out of bounds."); return false; } if((j < 0) || (j > numVertices-1)) { System.out.print("isEdge failed: "); System.out.print("index " + j); System.out.println(" is out of bounds."); return false; } // if vertex2 exists in the adjacency list of // vertex1, then return true return (Edges[i].find(names[j]) != null); } // Boolean method that tells us if {v1, v2} is an edge in the graph public boolean isEdge(String vertex1, String vertex2) { int i = getIndex(vertex1); if(i == -1) { System.out.print("isEdge failed: "); System.out.print(vertex1); System.out.println(" does not exist."); return false; } int j = getIndex(vertex2); if(j == -1) { System.out.print("isEdge failed: "); System.out.print(vertex2); System.out.println(" does not exist."); return false; } return isEdge(i, j); } // Computes the clustering coefficient of a vertex. This is the // version that takes a vertex index as argument. public double clusteringCoefficient(int i) { // Copy the adjacency list into an array, for easy access // copyIntoArray is a new method in the GenericLinkList class String[] temp = Edges[i].copyIntoArray(); // initialize edges-in-neighborhood to 0 int edgesInNbd = 0; // Scan pairs of neighbors and increment counter whenever // there is an edge for(int j = 0; j < temp.length; j++) for(int k = 0; k < j; k++) if(isEdge(temp[j], temp[k])) edgesInNbd++; // if there are no neighbors or one neighbor then, clustering // coefficient is trivially defined to be 1. Otherwise, // compute the ratio of number of edges in neighborhood to // the total number of pairs of neighbors if(temp.length <= 1) return 1; else return edgesInNbd*2.0/(temp.length*(temp.length-1)); } // Computes the clustering coefficient of a vertex. This is the // version that takes a vertex name as argument. public double clusteringCoefficient(String v) { int i = getIndex(v); if(i == -1) { System.out.print("clusteringCoefficient failed: "); System.out.print(v); System.out.println(" does not exist."); return 0; } return clusteringCoefficient(i); } // Computes the clustering coefficient of the entire graph // added on 2/23 public double clusteringCoefficient() { double sum = 0; for(int i = 0; i < numVertices; i++) sum = sum + clusteringCoefficient(i); return sum/numVertices; } // Checks whether the graph is connected or not by calling breadthFirstSearch public boolean isConnected() { // Perform breadth first search int[] bfsTree = breadthFirstSearch(names[0]); // Scan the bfsTree array, looking for -1. The graph // is not connected if there is -1 in this array for(int i = 0; i < bfsTree.length; i++) if(bfsTree[i] == -1) return false; return true; } // Returns a 2-d array of vertex names representing the connected components // of the graph. Each row in the 2-d array is a connected component. public String[][] connectedComponents() { // The maximum number of connected components equals the number // of vertices; so start by allocating this many rows. String[][] cc = new String[numVertices][]; // Keeps track of which vertices have been visited by repeated // calls to bfs boolean[] visited = new boolean[numVertices]; for(int i = 0; i < numVertices; i++) visited[i] = false; // Keeps track of the number of vertices have been visited by repeated // calls to bfs int numVisited = 0; // Keeps track of the number of connected components int numComponents = 0; // Repeat bfs until all vertices have been visited while(numVisited < numVertices) { // Scan visited until an unvisited vertex is found // and start bfs at that source int source; for(source = 0; source < numVisited; source++) if(!visited[source]) break; // Compute the bfsTree starting at this source int[] bfsTree = breadthFirstSearch(names[source]); // Scan bfsTree to count number of newly visited vertices int countNewVisited = 0; for(int i = 0; i < numVertices; i++) if(bfsTree[i] != -1) countNewVisited++; // Allocate a row of size countNewVisited in the current row of // cc to store the new connected component cc[numComponents] = new String[countNewVisited]; // Scan bfsTree again, this time to copy the newly visited // vertices into cc and set them as visited countNewVisited = 0; for(int i = 0; i < numVertices; i++) if(bfsTree[i] != -1) { cc[numComponents][countNewVisited++] = names[i]; visited[i] = true; } // Update numVisited numVisited = numVisited + countNewVisited; // Update numComponents numComponents++; } // end while // Resize cc to have exactly as mamy rows as numComponents String[][] newCC = new String[numComponents][]; for(int i = 0; i < numComponents; i++) newCC[i] = cc[i]; return newCC; } // Computes a shortest path (in hops) from source to destination. Does // this by simply calling breadthFirstSearch and following the parent // pointers in the BFS tree. If the source and destination are not in // the same component, returns null. Otherwise, returns a String array // of vertices in a shortest path public String[] shortestPath(String source, String dest, String attribute) { // Get index of source int sourceIndex = getIndex(source); if(sourceIndex == -1) { System.out.print("breadthFirstSearch failed: "); System.out.print(source); System.out.println(" does not exist."); return null; } // Get index of destination int destIndex = getIndex(dest); if(destIndex == -1) { System.out.print("breadthFirstSearch failed: "); System.out.print(dest); System.out.println(" does not exist."); return null; } // Perform a BFS or a DSP from destination int[] spTree; if(attribute.equals("hops")) spTree = breadthFirstSearch(destIndex); else spTree = DSP(dest); // If source is unreachable from destination if(spTree[sourceIndex] == -1) return null; // Define a String[] for shortest path and place the source vertex // in it String[] path = new String[numVertices]; path[0] = names[sourceIndex]; // Start following parent pointers and store each new vertex // encountered, in the path array. The while-loop executes // until the root of the BFS tree is encountered int currentIndex = sourceIndex; int pathLength = 0; while(currentIndex != spTree[currentIndex]) { currentIndex = spTree[currentIndex]; pathLength++; path[pathLength] = names[currentIndex]; } // Resize the path array to be exactly of the correct size String[] newPath = new String[pathLength + 1]; for(int i = 0; i < newPath.length; i++) newPath[i] = path[i]; return newPath; } public double shortestPathCost(String source, String dest, String attribute) { // Get index of source int sourceIndex = getIndex(source); if(sourceIndex == -1) { System.out.print("breadthFirstSearch failed: "); System.out.print(source); System.out.println(" does not exist."); return Double.MAX_VALUE; } // Get index of destination int destIndex = getIndex(dest); if(destIndex == -1) { System.out.print("breadthFirstSearch failed: "); System.out.print(dest); System.out.println(" does not exist."); return Double.MAX_VALUE; } // Perform a BFS or a DSP from destination int[] spTree; if(attribute.equals("hops")) spTree = breadthFirstSearch(destIndex); else spTree = DSP(dest); // If source is unreachable from destination if(spTree[sourceIndex] == -1) return Double.MAX_VALUE; // Start following parent pointers and store each new vertex // encountered, in the path array. The while-loop executes // until the root of the BFS tree is encountered int currentIndex = sourceIndex; double pathCost = 0; while(currentIndex != spTree[currentIndex]) { pathCost += getWeight(currentIndex, spTree[currentIndex]).doubleValue(); currentIndex = spTree[currentIndex]; } return pathCost; } // Breadth first search function that takes a vertex name as argument; // returns a breadth first search tree // stored in an array of integers with the entry in slot i containing // the index of the parent of the vertex with index i // parent of source is itself; unvisited nodes have parent -1 public int[] breadthFirstSearch(String source) { int sourceIndex = getIndex(source); if(sourceIndex == -1) { System.out.print("breadthFirstSearch failed: "); System.out.print(source); System.out.println(" does not exist."); return null; } return breadthFirstSearch(sourceIndex); } // Breadth first search function that takes a vertex index as argument; // returns a breadth first search tree // stored in an array of integers with the entry in slot i containing // the index of the parent of the vertex with index i // parent of source is itself; unvisited nodes have parent -1 public int[] breadthFirstSearch(int sourceIndex) { // Initialize the bfsTree array; the entry -1 means // not yet visited. int[] bfsTree = new int[numVertices]; for(int i = 0; i < numVertices; i++) bfsTree[i] = -1; // The parent of the tree root is itself bfsTree[sourceIndex] = sourceIndex; // Then initialize the visited array boolean[] visited = new boolean[numVertices]; for(int i = 0; i < numVertices; i++) visited[i] = false; visited[sourceIndex] = true; // Then initialize the queue Queue Q = new Queue(numVertices); Q.enqueue(sourceIndex); while(!Q.isEmpty()) { // get the index of the vertex first in line int current = Q.dequeue(); // Get the indices of the neighbors of the current vertex int[] neighbors = getNeighbors(current); // Scan the neighbors for(int i = 0; i < neighbors.length; i++) { // Get the index of the current neighbor int currentNeighbor = neighbors[i]; // Check if the neighbor is new, i.e., not visited // If so, mark the neighbor as visited, enqueue the neighbor, and // set the neighbor's parent in bfsTree if(!visited[currentNeighbor]) { visited[currentNeighbor] = true; Q.enqueue(currentNeighbor); bfsTree[currentNeighbor] = current; } } // end-scanning neighbors } // end-while Q is not empty return bfsTree; } // Computes the MST of this edge-weighted tree. Returns the tree in an int[] with parent // pointers and rooted at vertex 0 int[] MST() { // Initialize the list of vertices in the tree // Initially, no one except vertex 0 is in the tree boolean[] visited = new boolean[numVertices]; for(int i = 0; i < numVertices; i++) visited[i] = false; visited[0] = true; // Initialize the int[] that maintains the tree to default values // No vertices have parents set, except vertex 0 whose parent is itself int[] tree = new int[numVertices]; for(int i = 0; i < numVertices; i++) tree[i] = -1; tree[0] = 0; for(int i = 1; i <= numVertices-1; i++) { double minWeight = Double.MAX_VALUE; int bestVertex = -1; int bestParent = -1; for(int j = 0; j < numVertices; j++) { for(int k = 0; k < numVertices; k++) { if((visited[j]) && (!visited[k]) && (isEdge(j, k))) { if(getWeight(j, k).doubleValue() < minWeight) { minWeight = getWeight(j, k).doubleValue(); bestVertex = k; bestParent = j; } // end if better distance is found } // end if an edge between a visited and an unvisited is found } // end for-k } // end for-j // Update visited and tree visited[bestVertex] = true; tree[bestVertex] = bestParent; } // end for-i return tree; } // Computes an MST and returns it as a weighted graph myWeightedGraph MSTGraph() { int[] tree = MST(); myWeightedGraph g = new myWeightedGraph(); // Add all the vertices of this graph to g for(int i = 0; i < numVertices; i++) g.addVertex(names[i]); // Scan the int[] returned by MST, pick out the edges, and add these to g for(int i = 0; i < numVertices; i++) if(tree[i] != i) g.addEdge(i, tree[i], getWeight(i, tree[i]).doubleValue()); return g; } // Computes an MST and returns its total weight double costMST() { int[] tree = MST(); // A variable that accumulates the cost of the minimum spanning tree double cost = 0; // Scan the int[] returned by MST, pick out the edges, and add these to g for(int i = 0; i < numVertices; i++) if(tree[i] != i) cost += getWeight(i, tree[i]); return cost; } // Implementation of Dijkstra's shortest path algorithm int[] DSP(String source) { int sourceIndex = getIndex(source); // Declarations double[] dist = new double[numVertices]; int[] previous = new int[numVertices]; VertexHeap Q = new VertexHeap(numVertices); // Initializations for(int i = 0; i < numVertices; i++) // Initializations { dist[i] = Double.MAX_VALUE; // Unknown distance function from s to v previous[i] = -1; // the array previous stores parent info. // Create a Vertex object corresponding to vertex i and insert into VertexHeap Node v = new Node(dist[i], i, previous[i]); Q.insert(v); } dist[sourceIndex] = 0; // Distance from source to source is set to 0 previous[sourceIndex] = sourceIndex; // parent of sourceIndex is itself Q.change(Q.getIndex(sourceIndex), 0, sourceIndex); // and this is updated in the priority queue as well // The main loop while(!Q.isEmpty()) { Node u = Q.delete(); // Remove best vertex from priority queue; returns source on first iteration int uIndex = u.getIdentity(); // get the neighbors of u int[] nbrs = getNeighbors(uIndex); for(int j = 0; j < nbrs.length; j++) { int vIndex = nbrs[j]; int heapVIndex = Q.getIndex(vIndex); double alt = dist[uIndex] + getWeight(uIndex, vIndex); if(alt < dist[vIndex]) // Relax (u,v) { dist[vIndex] = alt; previous[vIndex] = uIndex; Q.change(heapVIndex, dist[vIndex], uIndex) ; } // end of if alt < dist[vIndex] } // end of for-loop that scans the neighbors } // end of while-Q-is-not-empty return previous; } // end of function // Uses a greedy algorithm to compute a TSP. Returns the TSP in an int[] containing the indices // of the vertices int[] greedyTSP() { //-------------------------BEGIN INITIALIZATION-------------------------------------------- // Find a cheapest triangle // Load triangle 0-1-2 into the the first 3 slots of the greedy array int[] greedy = new int[numVertices]; // Keeps track of lengths of TSPs double currentDistance; double currentBestDistance; greedy[0] = 0; greedy[1] = 1; greedy[2] = 2; // Computes the length of the triangle 0-1-2 if((getWeight(0, 1) == null) || (getWeight(1, 2) == null) || (getWeight(2, 0) == null)) currentBestDistance = Double.MAX_VALUE; else currentBestDistance = getWeight(0, 1).doubleValue() + getWeight(1, 2).doubleValue() + getWeight(2, 0).doubleValue(); // Picks the best triangle for(int i = 0; i < numVertices; i++) for(int j = 0; j < i; j++) for(int k = 0; k < j; k++) { if((getWeight(i, j) != null) && (getWeight(j, k) != null) && (getWeight(i, k) != null)) { currentDistance = getWeight(i, j).doubleValue() + getWeight(j, k).doubleValue() + getWeight(i, k).doubleValue(); if(currentDistance < currentBestDistance) { greedy[0] = i; greedy[1] = j; greedy[2] = k; currentBestDistance = currentDistance; } } } // Set the size of the partial tour constructed thus far int partialTourSize = 3; // Set up the array of visited vertices boolean[] visited = new boolean[numVertices]; for(int i = 0; i < numVertices; i++) visited[i] = false; visited[greedy[0]] = true; visited[greedy[1]] = true; visited[greedy[2]] = true; //System.out.println("The starting triangle is " + names[greedy[0]] + " " + names[greedy[1]] + " " + names[greedy[2]]); //------------------------- END INITIALIZATION-------------------------------------------- // Try greedily to add a city that yields the smallest increase // in the cost of the tour // Main loop: keep repeating until partial tour covers all cities while(partialTourSize < numVertices) { double smallestIncrease = Double.MAX_VALUE; double increase = 0; int bestInsertionPoint = 0; int bestVertex = 0; // Scan through all vertices, stopping at unvisited vertices for(int i = 0; i < numVertices; i++) { if(!visited[i]) { // Consider all possible positions of inserting vertex i into the tour // and record the smallest increase for(int j = 0; j < partialTourSize; j++) { // Compute the increase from inserting vertex i between positions j and j+1 in the // partial TSP array if((getWeight(greedy[j], i) == null) || (getWeight(i, greedy[(j+1)%partialTourSize]) == null)) increase = Double.MAX_VALUE; else if (getWeight(greedy[j], greedy[(j+1)%partialTourSize]) == null) increase = getWeight(greedy[j], i).doubleValue() + getWeight(i, greedy[(j+1)%partialTourSize]).doubleValue() - Double.MAX_VALUE; else increase = getWeight(greedy[j], i).doubleValue() + getWeight(i, greedy[(j+1)%partialTourSize]).doubleValue() - getWeight(greedy[j], greedy[(j+1)%partialTourSize]).doubleValue(); // If the increase is at least as good as the best increase thus far if(increase <= smallestIncrease) { smallestIncrease = increase; bestVertex = i; bestInsertionPoint = j; } // end of if we have found a smaller increase } // end of for-j } // end of if not visited } // end of for-i // Now we are ready to insert the bestVertex at the bestInsertionPoint for(int j = partialTourSize-1; j > bestInsertionPoint; j--) greedy[j+1] = greedy[j]; greedy[bestInsertionPoint+1] = bestVertex; visited[bestVertex] = true; partialTourSize++; } // end-while return greedy; } // Prints a greedy TSP void printGreedyTSP() { int[] greedyTSP = greedyTSP(); for(int i = 0; i < numVertices; i++) System.out.println(names[greedyTSP[i]]); } // Computes the cost of a greedy TSP double costGreedyTSP() { int[] greedyTSP = greedyTSP(); double cost = 0; for(int i = 0; i < numVertices; i++) if(getWeight(greedyTSP[i], greedyTSP[(i+1)%numVertices]) == null) return Double.MAX_VALUE; else cost += getWeight(greedyTSP[i], greedyTSP[(i+1)%numVertices]).doubleValue(); return cost; } // Prints the brute-force TSP void printTSP() { int[] TSP = TSP(); for(int i = 0; i < numVertices; i++) System.out.println(names[TSP[i]]); } // Computes the cost of the brute-force TSP double costTSP() { int[] TSP = TSP(); double cost = 0; for(int i = 0; i < numVertices; i++) if(getWeight(TSP[i], TSP[(i+1)%numVertices]) == null) return Double.MAX_VALUE; else cost += getWeight(TSP[i], TSP[(i+1)%numVertices]).doubleValue(); return cost; } void copy(int[] source, int[] dest) { for(int i = 0; i < dest.length; i++) dest[i] = source[i]; } // A wrapper function for TSP. This returns an optimal TSP as // an integer array int[] TSP() { // Set up the partial TSP int[] R = new int[numVertices]; R[0] = 0; // Set partial tour size to 1 int partialTourSize = 1; // Vertex 0 has been visited. No other vertex has. boolean[] visited = new boolean[numVertices]; for(int i = 0; i < numVertices; i++) visited[i] = false; visited[0] = true; // Call greedy TSP int[] T = greedyTSP(); // Call TSP TSP(R, partialTourSize, visited, T); return T; } void TSP(int[] R, int partialTourSize, boolean[] visited, int[] T) { // Base case: we have discovered a tour better than T if((partialTourSize == numVertices)&&(cost(R) < cost(T))) { System.out.println("Base case. Tour cost is " + cost(R)); copy(R, T); return; } // Another base case: In this base case, we check whether the TSP is // worth completing. We do this by computing the MST of the rest of the // vertices boolean[] unvisited = new boolean[numVertices]; for(int i = 0; i < numVertices; i++) unvisited[i] = !visited[i]; myWeightedGraph g = makeInducedSubGraph(unvisited); if (cost(R, partialTourSize) + g.costMST() >= cost(T)) return; // Recursive case: R is not complete and is currently better than T // and is therefore worth completing for(int i = 0; i < numVertices; i++) { if(!visited[i]) { //System.out.println("Appending " + i); visited[i] = true; R[partialTourSize++] = i; TSP(R, partialTourSize, visited, T); partialTourSize--; visited[i] = false; //System.out.println("Deleting " + i); } } // end of for-loop } // end of TSP double cost(int[] tour) { return cost(tour, tour.length); } double cost(int[] tour, int tourSize) { double c = 0; for(int i = 0; i < tourSize; i++) { Double temp = getWeight(tour[i], tour[(i+1)%tourSize]); if(temp == null) return Double.MAX_VALUE; c = c + temp.doubleValue(); } return c; } // Method to compute average degree of the graph // added on 11/24/2007 public double averageDegree() { double sum = 0; for(int i = 0; i < numVertices; i++) sum = sum + degree(i); return sum/numVertices; } // Method to compute maximum degree of the graph // added on 11/24/2007 public int maximumDegree() { int maxDegree = -1; int temp; for(int i = 0; i < numVertices; i++) { temp = degree(i); if(temp > maxDegree) maxDegree = temp; } return maxDegree; } // Method to compute minimum degree of the graph // added on 11/24/2007 public int minimumDegree() { int minDegree = numVertices; int temp; for(int i = 0; i < numVertices; i++) { temp = degree(i); if(temp < minDegree) minDegree = temp; } return minDegree; } // Computes the average path lenth of the graph // by repeatedly calling BFS and getting the distance // array. Added on 11/24/2007 public double averagePathLength() { // The average path length is infinity if the // graph is disconnected if(!isConnected()) return -1; // For connected graphs, just compute a shortest path distance between each // pair of vertices, add all distances, and finally divide by // number of ordered pairs, i.e., n(n-1)/2 double distanceSum = 0; for(int i = 0; i < numVertices; i++) for(int j = 0; j < i; j++) { int currentDistance = shortestPath(names[i], names[j], "hops").length-1; distanceSum = distanceSum + currentDistance; } return 2*distanceSum/(numVertices*(numVertices - 1)); } // Constructs a weighted graph, induced by a bunch of selected vertices // These selected vertices are represented by a boolean array myWeightedGraph makeInducedSubGraph(boolean[] selectedVertices) { myWeightedGraph g = new myWeightedGraph(); for(int i = 0; i < numVertices; i++) if(selectedVertices[i]) g.addVertex(names[i]); for(int i = 0; i < numVertices; i++) for(int j = 0; j < i; j++) if((selectedVertices[i]) && (selectedVertices[j])) { Double d = getWeight(i, j); if(d != null) g.addEdge(names[i], names[j], d.doubleValue()); } return g; } } // end of class