Traveling Salesperson Problem with Guava. Implements a recursive backtracking solution to solve the TSP using a Guava Network (Graph). git.charlesreid1.com/charlesreid1/tsp

TSP.java

import java.util.Random;
import java.util.Set;
import java.util.Map;
import java.util.TreeMap;
import java.util.List;
import java.util.LinkedList;
import java.util.Arrays;
import com.google.common.graph.Network;
import com.google.common.graph.NetworkBuilder;
import com.google.common.graph.ImmutableNetwork;
import com.google.common.graph.MutableNetwork;

//// Or be lazy:
//import java.util.*;
//import com.google.common.graph.*;

// See https://google.github.io/styleguide/javaguide.html
//
// TODO:
// Breaks when there are large unconnected segments of the graph.
// Breaks when there are non-existent nodes specified.
// Need to figure out a better way to specify the adjacency matrix.

/** This class solves the traveling salesman problem on a graph. */
public class TSP {

	
	public static void main(String[] args) { 
		int N;
		if(args.length==1) {
			N = Integer.decode(args[0]);
		} else {
			N = 5;
		}
		double conn = 1.00;
		TSP t = new TSP(N,conn);

        long start = System.nanoTime();
		t.solve();
        long end = System.nanoTime();
        long duration = end - start;
        System.out.printf("Found solution...?\n");
        System.out.printf("Elapsed time %03f s\n ", (duration/1E9) );
	}


	/**
	 * This class solves the traveling salesman problem on a graph.
	 * It makes use of Google's Guava library.
	 * This implements a recursive backtracking solution
	 * to search for the shortest path.
	 * 
	 * As is, this class hard-codes an adjacency matrix 
	 * for a network of 5 cities.
	 */

	// The actual graph of cities
	ImmutableNetwork<Node,Edge> graph;
	int graphSize;

	// Storage variables used when searching for a solution 
	int[] route;			// store the route
	double this_distance;	// store the total distance
	double min_distance;	// store the shortest path found so far

	/** Default constructor generates the graph and initializes storage variables */
	public TSP(int N, double connectivity) {

		// Build the graph
		this.graph = RandomGraph.buildGraph(N, connectivity);
		this.graphSize = N;
		
		// Initialize route variable, shared across recursive method instances
		this.route = new int[this.graphSize];
		for(int j=0; j<this.graphSize; j++) { 
			// -1 means no node selected
			this.route[j] = -1;
		}
		
		// Initialize distance variable, shared across recursive method instances
		this.this_distance = 0.0;
		this.min_distance = -1.0; // negative min means uninitialized
	}

	
	/** Public solve method will call the recursive backtracking method to search for solutions on the graph */
	public void solve() {
		/** To solve the traveling salesman problem:
		 * Set up the graph, choose a starting node, then call the recursive backtracking method and pass it the starting node.
		 */

		// We need to pass a starting node to recursive backtracking method
		Node startNode = null;
		
		// Grab a node, any node...
		for( Node n : graph.nodes() ) {
			startNode = n;
			break;
		}
		
		// Visit the first node
		startNode.visit();
		
		// Add first node to the route
		this.route[0] = startNode.id;
		
		// Pass the number of choices made
		int nchoices = 1;
		
		// Recursive backtracking
		explore(startNode, nchoices);
	}
	
	/** Recursive backtracking method: explore possible solutions starting at this node, having made nchoices */
	public void explore(Node node, int nchoices) {
		/**
		 * Solution strategy: recursive backtracking.
		 *
		 * Base case:
		 *		- We've visited as many cities as are on the graph.
		 *		- Check if this is a new solution (distance less than the current minimum).
		 *
		 *	Recursive case:
		 *		- Make a choice (mark node as visited, add city to route).
		 *		- Explore the consequences (recursive call).
		 *		- Unmake the choice (mark node as unvisited, remove city from route).
		 *		- Move on to next choice.
		 */

		if(nchoices == graphSize) {
			// 
			// BASE CASE
			//
			if(this.this_distance < this.min_distance || this.min_distance < 0) {
				// Solution base case:
				// if this_distance < min_distance, this is our new minimum distance
				// if min_distance < 0, this is our first minimium distance
				this.min_distance = this.this_distance;
				printSolution();
			} else {
				printFailure();
			}
			
		} else {
			//
			// RECURSIVE CASE
			// 	
			Set<Node> neighbors = graph.adjacentNodes(node);
			for(Node neighbor : neighbors) {
				if(neighbor.visited == false) {
					
					int distance_btwn = -10000;
					
					for( Edge edge : graph.edgesConnecting(node, neighbor) ) {
						distance_btwn = edge.value;
					}

					// Make a choice
					this.route[nchoices] = neighbor.id;
					neighbor.visit();
					this.this_distance += distance_btwn;
					
					// Explore the consequences
					explore(neighbor,nchoices+1);
					
					// Unmake the choice
					this.route[nchoices] = -1;
					neighbor.unvisit();
					this.this_distance -= distance_btwn;
				}
				// Move on to the next choice (continue loop)
			}				
		} // End base/recursive case
	}

	/** Print out solution */
	public void printSolution() {
		System.out.print("!!!!!YAY!!!!!!\tNEW SOLUTION\t");
		System.out.println("Route: "+Arrays.toString(this.route)
						  +"\tDistance: "+this.min_distance);
	}
	/** Print out failed path */
	public void printFailure() { }
}

/** Node class to represent cities */
class Node {
	public int id;
	public boolean visited; // Helps us to keep track of where we've been on the graph
	public Node(int id){
		this.id = id;
		this.visited = false;
	}
	public void visit(){
		this.visited = true;
	}
	public void unvisit() {
		this.visited = false;
	}
}

/** Node class to represent roads connecting cities */
class Edge {
	public int value;
	public Edge(int value) {
		this.value = value;
	}
}

/** Static class to generate random graphs.
 * 
 * We are interested in profiling code as a function of 
 * number of nodes N and number of edges E,
 * so this class takes arguments N and E.
 */
class RandomGraph { 

	private RandomGraph(){};
	
	public static ImmutableNetwork<Node,Edge> buildGraph(int nodes) { 
		// If connectivity not specified, set it to 1.
		return buildGraph(nodes, (nodes*(nodes-1))/2);
	}

	public static ImmutableNetwork<Node,Edge> buildGraph(int nodes, double connectivity) { 
		// If connectivity not specified, set it to 1.
		return buildGraph(nodes,(int)connectivity*(nodes*(nodes-1))/2);
	}
		
	public static ImmutableNetwork<Node,Edge> buildGraph(int N, int E) {

		Random r = new Random(150);

		/** Make a NetworkBuilder object for an undirected network and call build().
         *
         * https://github.com/google/guava/wiki/GraphsExplained#building-graph-instances
		 *
		 * This will load an adjacency matrix from a file.
		 *
		 * nodes is the number of nodes on the graph.
		 * connectivity is a number between 0 (totally disconnected) and 1 (fully connected).
		 */

		// MutableNetwork is an interface requiring a type for nodes and a type for edges
		MutableNetwork<Node,Edge> roads = NetworkBuilder.undirected().build();

		// Add nodes to graph
		List<Node> all_nodes = new LinkedList<Node>();
		for(int n=0; n<N; n++) {
			Node thenode = new Node(n);
			all_nodes.add(thenode);
			roads.addNode(thenode);
		}

		// Adding random edges to graph
		// between n_i and n_j
		//
		// If i != j, and edges are single and symmetric, 
		// N nodes have N! possible connections.
		//
		// start with a sequence enumerating all possible edges of the graph:
		// j = 1 ... N!
		// Now we can convert each enumeration to its corresponding pair 
		//
		//
		class Pair {
			int left;
			int right;
			public Pair(int left, int right) { 
				this.left = left;
				this.right = right;
			}
		}
		// Make 2 arrays: 
		// one integers ix = 1 .. E
		// one pairs P(i,j), i != j
		// we will make all possible pairs,
		// then shuffle indexes to pick pairs at random.
		Pair[] all_edges = new Pair[(N*(N-1))/2];
		int[] index = new int[(N*(N-1))/2];
		int c = 0;
		for(int i=0;i<N;i++){ 
			for(int j=i+1;j<N;j++){
				// make the pair and increment the index
				all_edges[c] = new Pair(i,j);
				index[c] = c;
				c++;
			}
		}
		// mix up the pair indexes
		RandomArray.shuffle(index);
		for(int e : index) { 
			Pair p = all_edges[e];

			// now we have our random pair.
			// create a random distance and add to the graph.
			int distance = 10 + r.nextInt(100);
			Edge egg = new Edge(distance);
			roads.addEdge(all_nodes.get(p.left),all_nodes.get(p.right),egg);
		}

		// freeze the network
		ImmutableNetwork<Node,Edge> frozen_roads = ImmutableNetwork.copyOf(roads);
		
		return frozen_roads;
	}
}

class RandomArray { 
	public static void shuffle(int[] arr) { 
		Random r = new Random(150);
		for(int i=(arr.length-1); i>0; i--) { 
			int j = r.nextInt(i+1);
			// swap arr[i] and arr[j]
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
}