Articulation Points Detector by Michael Verdicchio -------------------------------------------------- Compares O(|V|+|E|) algorithm from Gabow[2000] to trivial O(|V|*|E|) algorithm. Please see accompanying documentation for more information. ********************************************** RESULTS: 12 Random Graphs, 60 Iterations/Graph ********************************************** Random Graphs' Information: Graph: 1 2 3 4 5 6 7 8 9 10 11 12 ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- |V|: 25 30 40 50 70 95 120 170 220 520 770 1020 |E|: 10 20 40 60 100 150 200 300 400 1000 1500 2000 |A.P.|: 7 6 3 8 5 5 10 4 6 2 5 2 Gabow's Algorithm Time Results (ms): Trial 1 2 3 4 5 6 7 8 9 10 11 12 ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- 1 0 0 15 15 16 0 16 31 62 672 1813 4375 2 0 0 0 0 15 15 16 47 78 672 1828 4438 3 0 0 0 0 16 16 16 47 78 657 1812 4329 4 0 0 0 0 16 15 15 47 78 672 1797 4391 5 0 0 0 0 0 16 16 31 78 703 1813 4343 6 0 0 0 0 0 15 15 31 78 672 1813 4437 7 0 0 0 0 0 0 15 47 78 672 1797 4343 8 0 0 0 0 0 16 16 47 78 672 1797 4422 9 0 0 0 0 0 16 16 47 94 671 1828 4328 10 0 0 0 15 0 16 15 31 78 656 1812 4390 11 0 0 0 16 0 16 15 31 78 657 1796 4359 12 0 0 0 0 0 0 16 47 78 657 1813 4375 13 0 0 0 0 0 0 16 47 78 718 1797 4344 14 0 0 0 0 0 16 15 46 78 656 1859 4375 15 0 0 0 0 0 15 16 47 78 672 1797 4360 16 0 0 0 0 0 16 16 32 78 735 1891 4344 17 0 0 0 0 0 0 16 46 78 672 1797 4375 18 0 0 16 0 0 0 15 46 94 656 1813 4359 19 0 0 0 0 0 16 16 47 78 656 1812 4344 20 0 0 0 16 0 16 15 32 79 656 1859 4359 21 0 0 0 16 0 16 15 32 79 672 1812 4344 22 0 0 0 0 0 16 16 46 78 656 1797 4359 23 0 0 0 0 0 0 16 47 78 657 1797 4344 24 0 0 0 0 0 0 15 47 79 687 1813 4328 25 0 0 0 0 0 16 15 47 78 656 1797 4422 26 0 0 0 0 0 15 16 31 78 672 1812 4359 27 0 0 0 0 0 16 16 31 63 672 1844 4359 28 0 0 0 0 0 0 15 47 79 672 1844 4344 29 0 0 0 0 0 0 62 47 78 656 1813 4344 30 0 0 0 16 0 16 16 47 62 657 1813 4359 31 0 0 0 15 0 15 16 47 78 671 1797 4359 32 0 0 0 0 0 16 15 31 79 657 1797 4344 33 0 0 16 0 0 15 16 47 78 672 1797 4359 34 15 0 0 0 0 0 15 47 78 672 1812 4343 35 0 0 0 0 0 16 15 47 63 657 1844 4344 36 0 0 0 0 0 15 16 47 79 671 1797 4360 37 0 0 0 0 0 16 16 31 78 656 1891 4328 38 0 0 0 0 0 15 15 47 78 656 1797 4453 39 16 0 0 0 0 0 15 47 63 657 1813 4328 40 0 0 0 15 0 16 16 47 79 703 1813 4344 41 0 0 0 0 0 16 16 46 78 672 1813 4360 42 0 0 0 0 0 16 15 32 78 657 1797 4359 43 0 0 0 0 0 16 15 32 78 672 1812 4359 44 0 0 0 0 0 0 16 46 78 672 1812 4328 45 0 0 0 0 0 15 15 47 62 656 1797 4344 46 0 0 0 0 0 16 16 47 63 656 1859 4360 47 0 0 0 0 0 15 16 47 62 657 1797 4359 48 0 0 0 0 0 16 16 31 78 656 1797 4343 49 0 0 0 15 0 15 15 47 78 672 1797 4343 50 0 0 16 16 16 0 16 47 78 672 1813 4360 51 0 0 0 0 15 16 16 47 78 672 1906 4344 52 0 0 15 0 15 15 16 47 78 656 1843 4344 53 0 0 0 0 16 16 15 31 78 672 1813 4344 54 0 15 0 0 16 15 16 47 78 672 1797 4344 55 0 0 0 0 15 0 16 47 62 672 1812 4344 56 0 0 0 0 15 0 15 47 62 703 1828 4344 57 0 0 0 0 16 15 15 47 78 672 1797 4390 58 0 16 0 0 16 16 16 31 78 672 1844 4344 59 0 0 0 16 15 16 15 47 78 703 1828 4344 60 0 0 0 15 15 0 16 47 79 672 1812 4328 Trivial Algorithm Time Results (ms): Trial 1 2 3 4 5 6 7 8 9 10 11 12 ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- 1 32 0 0 0 16 47 78 172 297 2000 5265 11453 2 15 0 16 16 16 47 78 156 281 2015 5219 11421 3 0 16 0 16 15 47 78 156 282 1999 5266 11421 4 16 0 16 15 31 47 78 172 281 1969 5156 11516 5 0 0 0 16 31 47 94 172 297 1953 5218 11485 6 16 0 15 15 32 47 79 172 297 2000 5281 11485 7 0 16 0 16 31 47 78 156 297 2000 5219 11500 8 0 0 16 16 31 46 78 156 281 2000 5203 11469 9 0 0 0 0 31 47 78 172 297 2032 5203 11485 10 15 0 16 0 32 46 79 172 328 2015 5282 11438 11 0 15 0 0 31 94 78 172 282 1968 5219 11610 12 0 0 15 16 31 62 78 156 297 2281 5203 11359 13 0 0 0 15 31 47 78 157 281 2063 5156 11391 14 0 0 16 16 32 47 78 157 281 2016 5203 11468 15 16 16 0 15 31 47 78 171 297 1999 5203 11359 16 0 0 15 16 31 47 78 172 282 2015 5203 11360 17 0 0 0 16 31 62 78 157 281 2016 5218 11406 18 0 16 0 15 32 47 78 157 328 2031 5266 11391 19 0 0 16 0 31 46 94 156 312 2016 5203 11406 20 15 0 0 0 31 47 79 218 296 2000 5157 11360 21 0 0 15 0 31 46 78 172 328 1969 5203 11453 22 0 15 0 15 32 47 78 157 281 2015 5219 11375 23 0 0 16 16 31 62 78 156 281 2000 5265 11360 24 16 0 0 15 31 47 79 156 312 2016 5140 11406 25 0 0 16 16 31 47 78 156 297 2015 5219 11438 26 0 16 0 16 32 47 78 172 297 1953 5219 11344 27 0 0 15 15 31 47 78 172 296 2000 5156 11344 28 0 0 0 16 31 62 79 156 281 2016 5234 11375 29 16 0 16 0 31 47 78 156 297 2015 5218 11500 30 0 15 0 0 32 47 78 156 297 2000 5203 11422 31 0 0 15 0 31 47 78 172 281 2000 5281 11344 32 0 0 0 16 31 47 78 172 328 1968 5172 11469 33 0 0 0 15 31 47 78 156 281 2016 5234 11407 34 0 16 16 16 32 47 79 156 297 1999 5250 11375 35 0 0 0 16 31 47 78 156 296 2000 5156 11328 36 0 0 15 15 31 47 78 172 281 2032 5203 11375 37 0 0 0 16 31 47 78 172 281 1969 5219 11453 38 0 16 16 16 32 47 79 156 297 2015 5203 11407 39 0 0 0 0 31 47 78 203 296 2031 5218 11375 40 0 0 16 0 31 46 78 157 281 2000 5234 11359 41 0 0 0 16 31 47 78 172 281 1968 5297 11422 42 0 15 15 15 32 46 79 171 282 2015 5203 11344 43 16 0 0 16 31 47 94 172 328 2000 5219 11360 44 0 0 16 16 31 47 78 157 297 2000 5266 11390 45 0 0 0 15 31 47 78 156 297 2016 5219 11422 46 0 16 15 16 32 47 78 156 297 1968 5219 11359 47 0 0 0 16 31 47 78 172 297 2015 5218 11329 48 15 0 16 0 31 47 78 172 281 2016 5219 11376 49 0 0 0 0 31 47 78 156 282 2015 5187 11594 50 0 16 0 0 16 47 78 156 297 2000 5203 11343 51 0 0 0 15 16 47 78 156 281 2000 5157 11375 52 0 0 0 16 16 47 78 172 281 2016 5203 11328 53 0 0 16 16 15 47 78 172 282 2000 5203 11453 54 16 0 0 15 16 47 78 156 344 1953 5266 11359 55 0 0 15 16 16 63 78 156 297 2000 5203 11375 56 0 0 0 16 16 47 79 156 297 2000 5297 11344 57 0 0 16 15 15 94 78 172 282 2000 5203 11422 58 0 0 0 0 16 46 78 172 281 1953 5203 11344 59 0 0 16 0 16 47 78 203 281 1968 5219 11375 60 15 0 0 0 16 62 125 156 296 2000 5204 11344 Statistics: (Averages are time in ms) Graph FastAvg SlowAvg BestAvg FastWin SlowWin FS Ties MostWins ------- ------- ------- ------- ------- ------- ------- -------- 1 2.6 18.2 Fast 13 2 45 Fast 2 2.6 17 Fast 13 2 45 Fast 3 6.5 35.2 Fast 27 5 28 Fast 4 15.5 54.8 Fast 42 12 6 Fast 5 19.4 138.2 Fast 53 3 4 Fast 6 56.1 249.8 Fast 60 0 0 Fast 7 81.8 398.7 Fast 60 0 0 Fast 8 212.2 826.8 Fast 60 0 0 Fast 9 380.3 1468.5 Fast 60 0 0 Fast 10 3349.2 10026.7 Fast 60 0 0 Fast 11 9084.8 26083.1 Fast 60 0 0 Fast 12 21791.6 57029.2 Fast 60 0 0 Fast *************** End Of Report ***************