TSP Branch-and-Bound Solver Visualizer

TspBab.java

import java.awt.*;
import java.awt.geom.*;
import java.awt.event.*;
import java.awt.image.*;
import java.io.*;
import java.util.*;
import javax.swing.*;
import javax.swing.event.*;
import java.lang.reflect.*;

public class TspBab extends JFrame implements Runnable {
    public static final int board_size = 1000;
    private Point[] pts;
    private MyPanel panel;
    public TspBab() {
        super("TSP Branch-and-Bound Solver Visualizer");

        getContentPane().add(panel = new MyPanel());
        setDefaultCloseOperation(EXIT_ON_CLOSE);
        setSize(600, 480);
        setVisible(true);
        new Thread(this).start();
    }
    private Segment[][] segms_at;
    private Segment[] segms;
    private Segment[] segms_from;
    private int[] segms_from_count;
    private int[] segms_to_count;
    private Segment[] fixed_segms_from;
    private Segment[] fixed_segms_to;
    private int segms_index;
    private int[] old_seq;
    private int[] min_seq;
    private double cur_len;
    private double min_len = Double.POSITIVE_INFINITY;
    @Override
    public void run() {
        while(true) {
            //initialize
            old_seq = min_seq = segms_from_count = segms_to_count = null;
            segms_at = null;
            segms = segms_from = fixed_segms_from = fixed_segms_to = null;
            segms_index = 0;
            cur_len = 0;
            min_len = Double.POSITIVE_INFINITY;

            pts = new Point[16];
            for(int i = 0; i < pts.length; i++) {
                pts[i] = new Point((int)(Math.random()*board_size), (int)(Math.random()*board_size));
            }
            try{Thread.sleep(1000);}catch(Exception e){}
            long firstTime = System.currentTimeMillis();

            segms_at = new Segment[pts.length][pts.length];
            segms_from = new Segment[pts.length];
            segms_from_count = new int[pts.length];
            segms_to_count = new int[pts.length];
            fixed_segms_from = new Segment[pts.length];
            fixed_segms_to = new Segment[pts.length];
            segms = new Segment[pts.length*pts.length];
            segms_index = 0;
            for(int i = 0; i < pts.length; i++) {
                for(int j = 0; j < pts.length; j++) {
                    segms[segms_index++] = segms_at[i][j] = new Segment(i,j);
                }
            }
            segms_index = 0;

            Arrays.sort(segms);

            search_simple();

            for(segms_index = 0; segms_index < pts.length; segms_index++) {
                Segment s = segms[segms_index];
                addsegm(s);
            }
            search();
            repaint();
            System.out.println("finished.");
            long secondTime = System.currentTimeMillis();
            System.out.println((secondTime - firstTime) + " milliseconds.");
            try{Thread.sleep(3000);}catch(Exception e){}
        }
    }
    private void search_simple() {
        int[] next_link = new int[pts.length];
        int[] prev_link = new int[pts.length];
        int[] warp_link = new int[pts.length];
        for(int i = 0; i < pts.length; i++) {
            next_link[i] = -1;
            prev_link[i] = -1;
            warp_link[i] = i;
        }
        int count = 0;
        for(Segment s : segms) {
            if(next_link[s.in] == -1 && prev_link[s.out] == -1 && (warp_link[s.in] != s.out || count+1==pts.length)) {
                next_link[s.in] = s.out;
                prev_link[s.out] = s.in;
                int a = warp_link[s.in], b = warp_link[s.out];
                warp_link[b] = a;
                warp_link[a] = b;
                count++;
            }
        }
        old_seq = min_seq;
        min_seq = new int[pts.length];
        int current = 0;
        for(int i = 0; i < pts.length; i++) {
            min_seq[i] = current;
            current = next_link[current];
        }

        warp_link = null;
        boolean flag = true;
testwhile: while(flag) {
            flag = false;
            for(int i0 = 0; i0 < pts.length; i0++) {
                int i1 = (i0+1)%pts.length;
                for(int j0 = 2; j0 < pts.length; j0++) {
                    int j1 = (j0+1)%pts.length;
                    // before:  --- i0-i1 --- j0-j1 ---
                    // after: --- i0-j0 --- i1-j1 ---
                    int si0 = min_seq[i0];
                    int si1 = min_seq[i1];
                    int sj0 = min_seq[j0];
                    int sj1 = min_seq[j1];
                    if(segms_at[si0][si1].len+segms_at[sj0][sj1].len >
                            segms_at[si0][sj0].len+segms_at[si1][sj1].len) {
                        flag = true;
                        for(int k=0; i1+k<j0-k; k++) {
                            int t = min_seq[i1+k];
                            min_seq[i1+k] = min_seq[j0-k];
                            min_seq[j0-k] = t;
                        }
                        continue testwhile;
                    }
                }
            }
        }
        min_len = 0;
        for(int i = 0; i < pts.length; i++) {
            min_len += segms_at[min_seq[i]][min_seq[(i+1)%pts.length]].len;
        }
    }
    int repeat_count = 0;
    private void search() {
        if(repeat_count%10000==0) {
            repaint();
        }
        //try{Thread.sleep(10);}catch(Exception e){}
        repeat_count++;
        if(cur_len > min_len) {
            return;
        }

        {
            int hamil_cnt = 0;
            int i = 0;
            while(true) {
                //if(segms_from[i]==null || segms_from[i].link!=null)break;
                if(segms_from_count[i]!=1)break;
                //if(segms_to_count[i]!=1)break;
                i = segms_from[i].out;
                hamil_cnt++;
                if(hamil_cnt>pts.length)break;
                if(i==0)break;
            }
            if(hamil_cnt==pts.length) {
                System.out.println("!");
                old_seq = min_seq;
                min_len = cur_len;
                min_seq = new int[pts.length];
                i = 0;
                for(int j = 0; j < pts.length; j++) {
                    min_seq[j] = i;
                    i = segms_from[i].out;
                }
                repaint();
                return;
            }
        }
        Segment targ = null;
        int max_count = -1;
        double max_len = -1;
        for(int i = 0; i < pts.length; i++) {
            Segment s = segms_from[i];
            while(s != null) {
                int curr_count = segms_from_count[s.in] + segms_to_count[s.out];
                if(segms_at[s.out][s.in].used) curr_count = curr_count*2;
                if(fixed_segms_from[s.in]!=null) curr_count = curr_count+pts.length;
                if(fixed_segms_to[s.out]!=null) curr_count = curr_count+pts.length;
                if(!s.flag) {
                    if(curr_count > max_count) {
                        max_count = curr_count;
                        max_len = s.len;
                        targ = s;
                    } else if(curr_count==max_count && s.len > max_len) {
                        max_len = s.len;
                        targ = s;
                    }
                }
                s = s.link;
            }
        }
        if(segms[segms_index].in == segms[segms_index].out) {
            return;
        }
        if(targ == null) {
            return;
        }
        int old_index = segms_index++;
        //while(true) {
        //    if(segms_index>=segms.length) {
        //        segms_index = old_index;
        //        return;
        //    }
        //    Segment s = segms[segms_index];
        //    if(!segms_at[s.out][s.in].used) break;
        //    segms_index++;
        //}
        Segment adding = segms[segms_index-1];
        adding.flag = false;
        rmsegm(targ);
        addsegm(adding);
        search();
        rmsegm(adding);
        addsegm(targ);
        segms_index = old_index;

        if(fixed_segms_from[targ.in]!=null || fixed_segms_to[targ.out]!=null) {
            return;
        }
        {
            int i = targ.in;
            int hamil_cnt = 0;
            while(true) {
                if(fixed_segms_from[i]==null)break;
                i = fixed_segms_from[i].out;
                hamil_cnt++;
                if(hamil_cnt>pts.length)return;
                if(i==targ.in)return;
            }
        }
        fixed_segms_from[targ.in] = targ;
        fixed_segms_to[targ.out] = targ;
        targ.flag = true;
        search();
        targ.flag = false;
        fixed_segms_from[targ.in] = null;
        fixed_segms_to[targ.out] = null;
    }
    private void rmsegm(Segment targ) {
        if(segms_from[targ.in] == targ) {
            segms_from_count[targ.in]--;
            segms_to_count[targ.out]--;
            segms_from[targ.in] = targ.link;
            targ.used = false;
            cur_len -= targ.len;
        } else {
            Segment s = segms_from[targ.in];
            while(s != null) {
                if(s.link == targ) {
                    segms_from_count[targ.in]--;
                    segms_to_count[targ.out]--;
                    s.link = targ.link;
                    targ.used = false;
                    cur_len -= targ.len;
                    return;
                }
                s = s.link;
            }
            System.out.println("remove failed.");
        }
    }
    private void addsegm(Segment targ) {
        segms_from_count[targ.in]++;
        segms_to_count[targ.out]++;
        targ.link = segms_from[targ.in];
        segms_from[targ.in] = targ;
        targ.used = true;
        cur_len += targ.len;
    }
    private class Segment implements Comparable<Segment> {
        private int in, out;
        private double len;
        private int lensq;
        private Segment link;
        private boolean used;
        private boolean flag;
        private Segment(int in, int out) {
            this.in = in;
            this.out = out;
            Point p0 = pts[in];
            Point p1 = pts[out];
            len = p0.distance(p1);
            lensq = (p0.x-p1.x)*(p0.x-p1.x) + (p0.y-p1.y)*(p0.y-p1.y);
            if(in==out) {
                lensq = Integer.MAX_VALUE;
                len = Double.POSITIVE_INFINITY;
            }
        }
        @Override
        public int compareTo(Segment o) {
            return o.lensq==lensq ? 0 : lensq<o.lensq ? -1 : 1;
            //return o.lensq==lensq ? idcompare(o) : lensq<o.lensq ? -1 : 1;
        }
        private int idcompare(Segment o) {
            int it0 = Math.min(in, out);
            int it1 = Math.max(in, out);
            int io0 = Math.min(o.in, o.out);
            int io1 = Math.max(o.in, o.out);
            return it0==io0 ? (it1==io1 ? 0 : it1<io1 ? -1 : 1) : it0<io0 ? -1 : 1;
        }
        @Override
        public int hashCode() {
            return in*pts.length+out;
        }
    }
    private class MyPanel extends JPanel{
        public MyPanel() {
            super(true);
        }
        private int bsize, offx, offy;
        @Override
        public void paint(Graphics g_) {
            Graphics2D g = (Graphics2D)g_;

            g.setColor(Color.WHITE);
            g.fillRect(0, 0, getWidth(), getHeight());

            if(pts==null)return;

            bsize = Math.min(getWidth(), getHeight())-10;
            offx = (getWidth()-bsize)/2;
            offy = (getHeight()-bsize)/2;

            g.setColor(new Color(128,0,255,20));
            g.setStroke(new BasicStroke(9));
            if(old_seq != null) {
                for(int i = 0; i < pts.length; i++) {
                    drawSegment(g, segms_at[old_seq[i]][old_seq[(i+1)%pts.length]]);
                }
            }
            g.setColor(new Color(255,0,0,100));
            g.setStroke(new BasicStroke(5));
            if(min_seq != null) {
                for(int i = 0; i < pts.length; i++) {
                    drawSegment(g, segms_at[min_seq[i]][min_seq[(i+1)%pts.length]]);
                }
            }
            g.setStroke(new BasicStroke(2));
            if(segms_from != null) {
                //for(int i = 0; i < segms_index; i++) {
                //    Segment s = segms[i];
                //    if(!s.used) {
                //        g.setColor(Color.YELLOW);
                //        drawSegment(g, s);
                //    }
                //}
                for(int i = 0; i < pts.length; i++) {
                    Segment s = segms_from[i];
                    while(s != null) {
                        g.setColor(s.flag ? Color.GREEN : Color.BLACK);
                        drawSegment(g, s);
                        s = s.link;
                    }
                }
            }

            g.setColor(Color.BLUE);
            g.setStroke(new BasicStroke(1));
            for(int i = 0; i < pts.length; i++) {
                int dx = pts[i].x*bsize/board_size+offx;
                int dy = pts[i].y*bsize/board_size+offy;
                g.fillRect(dx-2,dy-2,4,4);
            }
            g.setColor(Color.BLACK);
            g.setStroke(new BasicStroke(1));
            g.drawString(Double.toString(cur_len), 0, getHeight()-20);
            g.drawString(Double.toString(min_len), 0, getHeight());
        }
        private void drawSegment(Graphics2D g, Segment s) {
            int dx0 = pts[s.in].x*bsize/board_size+offx;
            int dy0 = pts[s.in].y*bsize/board_size+offy;
            int dx1 = pts[s.out].x*bsize/board_size+offx;
            int dy1 = pts[s.out].y*bsize/board_size+offy;
            //g.drawLine(dx0,dy0,(int)(dx1*1.2-dx0*0.2),(int)(dy1*1.2-dy0*0.2));
            g.drawLine(dx0,dy0,dx1,dy1);
        }
    }
    public static void main(String[] args) {
        new TspBab();
    }
}