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}