//package teneyck.backtrackstuff;
import java.util.*;

class TSPBandB {
  private final double INFINITY = 1E10;
  private double minTour;
  private Graph g;       //an adjacency matrix rep of the graph
  private int N;              //number of vertices
  private Vector bestList;
  private boolean [ ] mark;
  private double [ ] minEdge;
  private BinaryHeap q;

  class TSPNode implements Comparable{
    int level;
    double length, bound;
    Vector path;
    Object lastVertex;
    protected TSPNode(Object vert) {
      level = 0;
      length = 0.0;
      bound = 0.0;
      lastVertex = vert;
      path = new Vector( );
    }
    protected void copyList(Vector v) {
      if (v == null || v.isEmpty( ) )
        path = new Vector( );
      else
        path = new Vector(v);
    }
    protected void add(Object vtx) {
      path.add(vtx);
    }
    public int compareTo(Object obj) {
      TSPNode n = (TSPNode)obj;
      return (int)(n.bound - this.bound);
    }
  }  

  public TSPBandB(Graph G) {
    g = G;
    N = g.size( );
    minTour = INFINITY;
    q = new BinaryHeap( );
    mark = new boolean[N+1];
    minEdge = new double[N+1];
  }

  private void tsp( ) throws HeapUnderflowException {
    while (!q.isEmpty( ) ) {
      TSPNode temp = (TSPNode)q.deleteMin( );
      if (temp.bound < minTour) {
        Iterator itr = g.neighbors(temp.lastVertex);
        while (itr.hasNext( )) {
          Object nextVert = itr.next( );
          if (!temp.path.contains(nextVert) ) {
            TSPNode u = new TSPNode(nextVert);
            u.level = temp.level+1;
            u.length = temp.length + length(temp.lastVertex, nextVert);
            u.copyList(temp.path);
            u.add(nextVert);
            if (u.level == N - 2) {
              Iterator ntr = g.neighbors(nextVert);
              while (ntr.hasNext( ) ) {
                Object x = ntr.next( );
                if (!u.path.contains(x) ) {
                  u.add(x);
                  u.length += length(nextVert, x);
                  u.add(u.path.get(0) );
                  u.length += length(x, u.path.get(0));
                  if (u.length < minTour) {
                    minTour = u.length;
                    bestList = new Vector(u.path);
                  }
                  break;
                }
              }
            }
            else {
              u.bound = bound(u);
              if (u.bound < minTour) 
                q.add(u);
            }
          }
        }
      }
    }
  }
        
  private double length(Object v1, Object v2) {
    Edge e = g.getEdge(v1, v2);
    Object hold = e.label( );
    return ((Double)hold).doubleValue( );
  }
  private double bound (TSPNode n) {
    //keep an array of vertices -- with minimum outgoing distance for each
    //vertices are labeled by number
    for (int i = 0; i <= N; i++) 
      mark[i] = false;
    Iterator itr = n.path.iterator( );
    while (itr.hasNext( ) ) {
      Integer hold = (Integer)itr.next( );
      int num = hold.intValue( );
      mark[num] = true;
    }
    //unmark the last vertex in the path
    Integer lastv = (Integer)n.lastVertex;
    mark[lastv.intValue( )] = false;
    double bnd = n.length;
    for (int i = 0; i <= N; i++) {
      if (!mark[i]) 
        bnd += minEdge[i];
    }
    return bnd;
  }
  private void init( ) {
    for (int i = 0; i <= N; i++) {
      mark[i] = false;
    }
    Iterator itr = g.iterator( );
    while (itr.hasNext( ) ) {
      Object obj = itr.next( );
      GraphListVertex v = (GraphListVertex)obj;
      Iterator jtr = g.neighbors(v.label( ));
      double cost = INFINITY;
      while (jtr.hasNext( ) ) {
        Object w = jtr.next( );
        double len = length(v.label( ), w);
        if (len < cost)
          cost = len;
      }
      minEdge[((Integer)v.label( )).intValue( )] = cost;
    }
  }

  public void tspPath( ) throws HeapUnderflowException{
    init( );
    Integer v1 = new Integer(1);
    TSPNode root = new TSPNode(v1);
    root.add(v1);
    root.bound = bound(root);
    q.add( root );
    tsp( );
    System.out.print("The TSP path is: ");
    Iterator itr = bestList.iterator( );
    while (itr.hasNext( ) ) {
      System.out.print("  " + itr.next( ) );
    }
    System.out.println( );
    System.out.println("The minimum path length is " + minTour);
  }                 
                       
  public static void main(String [ ] args) {
    Graph g = new DirectedGraphList( );
    g.add(new Integer(1) );
    g.add(new Integer(2) );
    g.add(new Integer(3) );
    g.add(new Integer(4) );
    g.add(new Integer(5) );
    g.addEdge(new Integer(1), new Integer(2), new Double(14.0));
    g.addEdge(new Integer(1), new Integer(3), new Double(4.0));
    g.addEdge(new Integer(1), new Integer(4), new Double(10.0));
    g.addEdge(new Integer(1), new Integer(5), new Double(20.0));
    g.addEdge(new Integer(2), new Integer(1), new Double(14.0));
    g.addEdge(new Integer(2), new Integer(3), new Double(7.0));
    g.addEdge(new Integer(2), new Integer(4), new Double(8.0));
    g.addEdge(new Integer(2), new Integer(5), new Double(7.0));
    g.addEdge(new Integer(3), new Integer(1), new Double(4.0));
    g.addEdge(new Integer(3), new Integer(2), new Double(5.0));
    g.addEdge(new Integer(3), new Integer(4), new Double(7.0));
    g.addEdge(new Integer(3), new Integer(5), new Double(16.0));
    g.addEdge(new Integer(4), new Integer(1), new Double(11.0));
    g.addEdge(new Integer(4), new Integer(2), new Double(7.0));
    g.addEdge(new Integer(4), new Integer(3), new Double(9.0));
    g.addEdge(new Integer(4), new Integer(5), new Double(2.0));
    g.addEdge(new Integer(5), new Integer(1), new Double(18.0));
    g.addEdge(new Integer(5), new Integer(2), new Double(7.0));
    g.addEdge(new Integer(5), new Integer(3), new Double(17.0));
    g.addEdge(new Integer(5), new Integer(4), new Double(4.0));
    TSPBandB tsp = new TSPBandB(g);
    try {
      tsp.tspPath();
    }catch (HeapUnderflowException e) {System.out.println(e); }
  }
}