001package algs15;
002import java.util.Scanner;
003import stdlib.*;
004
005public class TestUF {
006        public static enum Order { ZERO_I, I_ZERO, I_MINUS, MINUS_I, RANDOM }
007        public static void main(String[] args) {
008                show(10, "4 3, 3 8, 6 5, 9 4, 2 1, 8 9, 5 0, 7 2, 6 1, 1 0, 6 7"); //textbook tinyUF.txt                
009                show(10, "0 1, 0 2, 0 3, 0 4, 0 5, 0 6, 0 7, 0 8, 0 9"); // ZERO_I
010                show(10, "1 0, 2 0, 3 0, 4 0, 5 0, 6 0, 7 0, 8 0, 9 0"); // I_ZERO
011                show(10, "1 0, 2 1, 3 2, 4 3, 5 4, 6 5, 7 6, 8 7, 9 8"); // I_MINUS
012                show(10, "0 1, 1 2, 2 3, 3 4, 4 5, 5 6, 6 7, 7 8, 8 9"); // MINUS_I
013                show(16, "0 1, 2 3, 4 5, 6 7, 8 9, 10 11, 12 13, 14 15," + "0 2, 4 6, 8 10, 12 14," + "0 4, 8 12," + "0 8");
014                showRandom(12);
015                double prevUnion = 0;
016                double prevConnected = 0;
017                for (int N = 128; N<=MAX; N += N) {
018                        timeTrial(N, Order.RANDOM);
019                        StdOut.format("N=%,13d Union=%7.3f [%8.3f] Connected=%7.3f [%8.3f]\n", N, timeUnion, timeUnion/prevUnion, timeConnected, timeConnected/prevConnected);
020                        prevUnion = timeUnion;
021                        prevConnected = timeConnected;
022                }
023        }
024        private static int MAX=50_000_000;
025        private static UF getUF (int N) {
026                  MAX=500_000; return new QuickFindUF(N);  //   (262_144,RANDOM) Union ~ 36  Connected ~ .006
027            //MAX=500_000; return new QuickUnionUF(N); //   (262_144,RANDOM) Union ~ 17  Connected ~ 18
028                //return new WeightedUF(N);                //(33_554_432,RANDOM) Union ~ 10  Connected ~ 10
029                //return new CompressionUF(N);             //(33_554_432,RANDOM) Union ~ 16  Connected ~ 7
030                //return new XWeightedHalvingUF(N);        //(33_554_432,RANDOM) Union ~  9  Connected ~ 6
031                //return new XWeightedCompressionUF(N);    //(33_554_432,RANDOM) Union ~  9  Connected ~ 6
032        }
033        
034        private static double timeUnion;
035        private static double timeConnected;
036        private static void timeTrial(int N, Order order) {
037                UF ufTime = getUF(N);                           
038                SHOW_COMPRESSION_STEPS = false;
039                Stopwatch sw1 = new Stopwatch();
040                for (int i=1; i<N; i+= 1) {
041                        int p = StdRandom.uniform(N);
042                        int q = StdRandom.uniform(N);
043                        switch (order) {
044                        case ZERO_I: ufTime.union (0, i); break; 
045                        case I_ZERO: ufTime.union (i, 0); break; 
046                        case I_MINUS: ufTime.union (i, i-1); break;
047                        case MINUS_I: ufTime.union (i-1, i); break;
048                        case RANDOM: ufTime.union (p, q); break;
049                        }
050                }
051                timeUnion = sw1.elapsedTime();
052
053                Stopwatch sw2 = new Stopwatch();                
054                for (int i=1; i<N; i+= 1) {
055                        int p = StdRandom.uniform(N);
056                        int q = StdRandom.uniform(N);
057                        ufTime.connected(p, q);
058                }       
059                timeConnected = sw2.elapsedTime();
060        }
061        
062        public static boolean SHOW_COMPRESSION_STEPS=false;
063        private static void showRandom (int N) {
064                SHOW_COMPRESSION_STEPS = true;
065                UF uf = getUF(N);
066                uf.toGraphviz();
067                StdOut.format("       %2d%s\n", uf.count(), uf);
068                for (int i=1; i<4*N; i++) {
069                        int p = StdRandom.uniform(N);
070                        int q = StdRandom.uniform(N);
071                        if (uf.connected(p, q)) {
072                                StdOut.format("%2d %2d: connected\n", p, q); 
073                        } else {
074                                uf.union(p, q);
075                                uf.toGraphviz();
076                                StdOut.format("%2d %2d: %2d%s\n", p, q, uf.count(), uf);
077                        }
078                }
079                StdOut.println();
080        }
081        private static void show (int N, String input) {
082                SHOW_COMPRESSION_STEPS = true;
083                Scanner s = new Scanner(input);
084                s.useDelimiter("[\\s,]\\s*"); // use comma or space as delimiter
085
086                UF uf = getUF(N);
087                uf.toGraphviz();
088                StdOut.format("       %2d%s\n", uf.count(), uf);
089                while (s.hasNext()) {
090                        int p = s.nextInt();
091                        int q = s.nextInt();
092                        if (uf.connected(p, q)) {
093                                StdOut.format("%2d %2d: connected\n", p, q); 
094                        } else {
095                                uf.union(p, q);
096                                uf.toGraphviz();
097                                StdOut.format("%2d %2d: %2d%s\n", p, q, uf.count(), uf);
098                        }
099                }
100                StdOut.println();
101                s.close();
102        }
103}