00001 00005 package edu.mit.csail.sdg.squander.examples.graph; 00006 00007 import java.util.ArrayList; 00008 import java.util.Iterator; 00009 import java.util.List; 00010 00011 import edu.mit.csail.sdg.squander.examples.graph.Graph.Node; 00012 00019 public class HamiltonianMan { 00020 00021 private static ArrayList<Integer> solution; 00022 00023 public static Node[] hp(Graph g) { 00024 int n = g.size(); 00025 int[][] adj = new int[n][n]; 00026 for (Graph.Edge e : g.edges()) { 00027 adj[e.src.label][e.dst.label] = 1; 00028 } 00029 solution = null; 00030 hp(adj); 00031 if (solution == null) 00032 solution = new ArrayList<Integer>(); 00033 Node[] nPath = new Node[solution.size()]; 00034 int i = 0; 00035 for (Integer l : solution) 00036 nPath[i++] = new Node(l); 00037 return nPath; 00038 } 00039 00040 public static void hp(int[][] adjacency) { 00041 hp(new ArrayList<Integer>(), adjacency); 00042 } 00043 00044 public static void hp(List<Integer> pathSoFar, int[][] adjacency) { 00045 if (solution != null) 00046 return; 00047 int n = adjacency.length; 00048 if (pathSoFar.size() == n) { 00049 printSolution(pathSoFar); 00050 return; 00051 } else if (pathSoFar.size() == 0) { 00052 for (int i = 0; i < n; i++) { 00053 pathSoFar.add(i); 00054 hp(pathSoFar, adjacency); 00055 pathSoFar.remove(pathSoFar.size() - 1); 00056 } 00057 } else { 00058 int currentNode = pathSoFar.get(pathSoFar.size() - 1); 00059 for (int i = 0; i < n; i++) { 00060 if (!pathSoFar.contains(i) && adjacency[currentNode][i] != 0) { 00061 pathSoFar.add(i); 00062 hp(pathSoFar, adjacency); 00063 pathSoFar.remove(pathSoFar.size() - 1); 00064 } 00065 } 00066 } 00067 } 00068 00069 public static void printSolution(List<Integer> pathSoFar) { 00070 Iterator<Integer> it = pathSoFar.iterator(); 00071 solution = new ArrayList<Integer>(); 00072 while (it.hasNext()) { 00073 Integer val = it.next(); 00074 System.err.print(val + " "); 00075 solution.add(val); 00076 } 00077 System.err.println(" got it"); 00078 } 00079 00080 public static void main(String[] args) { 00081 int[][] adjacency = { 00082 { 0, 1, 0, 0, 0 }, 00083 { 1, 0, 1, 1, 0 }, 00084 { 0, 1, 0, 1, 1 }, 00085 { 0, 1, 1, 0, 0 }, 00086 { 0, 0, 1, 0, 0 } }; 00087 hp(adjacency); 00088 System.out.println(solution); 00089 } 00090 }