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