SUMMARY These preliminary results indicate that a properly coded version of LOWPOINT behaves very similar to Path, but the 2-pass algorithm is not competitive. The statistics below refer to 7 routines: Path.0 -- algorithm presented in the new paper Path.1 -- saves B[TOP[B]] in a variable LWPT.0 -- LOWPOINT algorithm as presented in Aho,Hopcroft & Ullman LWPT.1 -- uses D array (discovery times) in a manner similar to Path, to store component numbers LWPT.2 -- saves LOWLINK[v] in a variable, during DFS(v) 2P.0 -- 2-pass algorithm 2P.1 -- uses D array (discovery times) in a manner similar to Path, to store component numbers Path.0, Path.1 and LWPT.2 behave the same. This assumes optimized compilation - without optimization LWPT.2 can run up to 100% slower than Path.0 or Path.1 on bad examples. Random Wraparound Rectangular 2D Grid Digraphs n m #SCC's Path.0 Path.1 LWPT.0 LWPT.1 LWPT.2 2P.0 2P.1 86031 172048 22934 0.12 0.12 0.21 0.15 0.13 0.62 0.59 72732 145553 19325 0.10 0.11 0.17 0.13 0.11 0.51 0.49 189975 379986 50639 0.26 0.26 0.47 0.32 0.28 2.11 2.10 125614 251524 32296 0.17 0.18 0.30 0.22 0.19 0.95 0.95 76375 152608 20220 0.11 0.11 0.18 0.13 0.11 0.54 0.52 76362 152522 20932 0.11 0.10 0.18 0.13 0.11 0.54 0.52 153109 305969 39920 0.21 0.22 0.37 0.27 0.23 1.46 1.19 58905 117681 15585 0.08 0.08 0.15 0.10 0.09 0.42 0.40 60066 119802 16460 0.08 0.09 0.14 0.10 0.09 0.42 0.40 96300 193131 24497 0.14 0.14 0.24 0.17 0.14 0.69 0.66 227168 454422 60314 0.31 0.32 0.71 0.39 0.35 2.48 2.29 122408 244823 32556 0.17 0.18 0.29 0.22 0.17 0.94 0.83 156400 312446 41705 0.22 0.22 0.38 0.27 0.23 1.41 1.11 157950 316035 41049 0.22 0.22 0.39 0.29 0.23 2.11 1.13 112710 225566 29822 0.16 0.16 0.26 0.20 0.17 0.80 0.77 160160 319843 42938 0.23 0.22 0.38 0.28 0.24 2.02 1.12 93600 187198 24873 0.13 0.13 0.22 0.17 0.14 0.67 0.63 54390 109035 13762 0.07 0.08 0.13 0.10 0.08 0.38 0.37 172966 346075 45324 0.25 0.26 0.41 0.30 0.25 2.15 1.24 114957 230195 30424 0.16 0.16 0.28 0.20 0.17 0.81 0.78 Random Rectangular 2D Grid Digraphs n m #SCC's Path.0 Path.1 LWPT.0 LWPT.1 LWPT.2 2P.0 2P.1 179928 359005 68646 0.26 0.27 0.50 0.32 0.29 2.16 1.72 153966 307147 59459 0.23 0.23 0.38 0.28 0.24 1.80 1.13 54060 107651 21761 0.08 0.08 0.13 0.09 0.08 0.39 0.38 64034 127549 24676 0.09 0.09 0.16 0.11 0.10 0.47 0.44 134460 268152 52567 0.20 0.19 0.33 0.24 0.21 1.22 0.96 83622 166651 32329 0.12 0.12 0.20 0.15 0.13 0.60 0.59 128673 256592 50512 0.19 0.18 0.32 0.22 0.21 1.00 0.90 55930 111387 22487 0.08 0.08 0.13 0.10 0.08 0.40 0.39 92082 183511 35944 0.13 0.13 0.22 0.16 0.14 0.67 0.64 91300 181993 36597 0.13 0.13 0.22 0.16 0.14 0.66 0.63 55822 111171 21202 0.08 0.08 0.14 0.10 0.09 0.40 0.39 96409 192168 37458 0.14 0.15 0.23 0.17 0.14 0.69 0.67 146510 292231 55653 0.23 0.22 0.41 0.27 0.24 1.37 1.03 96789 192928 38408 0.14 0.14 0.23 0.17 0.15 0.70 0.67 95940 191207 36125 0.14 0.14 0.23 0.17 0.15 0.70 0.67 80238 159907 31381 0.11 0.12 0.19 0.14 0.12 0.58 0.56 85836 171085 33945 0.13 0.12 0.20 0.15 0.13 0.62 0.61 77988 155387 30105 0.11 0.11 0.18 0.13 0.12 0.56 0.53 96279 191878 37576 0.14 0.13 0.23 0.16 0.15 0.68 0.66 142964 285169 55784 0.20 0.21 0.35 0.25 0.23 1.37 1.08 Random Dense Digraphs n m #SCC's Path.0 Path.1 LWPT.0 LWPT.1 LWPT.2 2P.0 2P.1 1152 26584 1 0.00 0.01 0.01 0.01 0.00 0.10 0.09 3896 303898 1 0.08 0.06 0.11 0.08 0.07 15.86 15.89 2874 164698 1 0.04 0.04 0.06 0.05 0.03 5.05 5.06 4733 448419 1 0.11 0.10 0.16 0.12 0.09 30.53 30.88 3508 245306 1 0.06 0.06 0.08 0.07 0.05 10.86 10.85 1059 22182 1 0.01 0.00 0.01 0.01 0.00 0.07 0.08 4307 370333 1 0.10 0.08 0.14 0.09 0.09 22.18 22.14 3753 281324 1 0.07 0.07 0.10 0.07 0.06 13.66 13.60 3741 279573 1 0.08 0.06 0.10 0.07 0.06 13.47 13.41 3424 233890 1 0.07 0.05 0.08 0.06 0.06 9.85 9.87 4803 461460 1 0.12 0.10 0.17 0.12 0.09 32.39 32.54 3098 192194 1 0.05 0.05 0.07 0.05 0.04 7.01 6.87 1591 50479 1 0.01 0.01 0.02 0.01 0.02 0.23 0.23 3512 246422 1 0.06 0.06 0.09 0.06 0.05 10.52 10.51 3613 259985 1 0.06 0.06 0.09 0.07 0.06 11.76 11.77 3449 237995 1 0.06 0.06 0.08 0.06 0.05 10.03 10.01 2221 99046 1 0.03 0.02 0.04 0.02 0.02 1.64 1.64 4902 481492 1 0.13 0.09 0.17 0.13 0.09 34.26 34.20 4968 493625 1 0.13 0.10 0.17 0.13 0.11 36.06 35.56 2988 178113 1 0.04 0.04 0.07 0.04 0.04 5.86 5.86 Random Acyclic Digraphs n m #SCC's Path.0 Path.1 LWPT.0 LWPT.1 LWPT.2 2P.0 2P.1 1165 348980 1165 0.07 0.06 0.09 0.07 0.06 2.28 2.27 1418 490546 1418 0.09 0.09 0.12 0.10 0.08 4.42 4.00 1663 684917 1663 0.13 0.12 0.17 0.14 0.12 8.30 6.81 1872 871501 1872 0.17 0.17 0.26 0.19 0.15 10.79 10.57 1024 254184 1024 0.05 0.04 0.07 0.05 0.04 1.51 1.50 1418 509758 1418 0.10 0.09 0.12 0.10 0.09 4.40 4.29 1971 936662 1971 0.22 0.14 0.25 0.22 0.23 12.09 12.40 1466 542662 1466 0.10 0.10 0.13 0.11 0.09 5.23 4.79 1069 286920 1069 0.05 0.05 0.08 0.05 0.05 1.78 1.76 1344 452618 1344 0.09 0.07 0.12 0.08 0.08 3.91 3.46 1727 742374 1727 0.15 0.13 0.18 0.15 0.13 9.16 8.30 1040 271710 1040 0.06 0.04 0.07 0.05 0.05 1.63 1.62 1994 992093 1994 0.27 0.22 0.29 0.25 0.35 13.72 13.73 1668 700529 1668 0.14 0.12 0.17 0.14 0.12 8.35 7.32 1503 558341 1503 0.11 0.09 0.14 0.11 0.10 4.84 5.30 1659 675744 1659 0.13 0.12 0.17 0.13 0.12 7.49 6.66 1730 750003 1730 0.14 0.13 0.19 0.15 0.13 8.98 8.39 1153 323810 1153 0.06 0.06 0.08 0.06 0.06 2.06 2.04 1079 289304 1079 0.05 0.05 0.07 0.06 0.05 1.77 1.76 1838 850874 1838 0.20 0.20 0.24 0.21 0.18 10.25 10.42 Random Acyclic Digraphs (Selection Sampling) n m #SCC's Path.0 Path.1 LWPT.0 LWPT.1 LWPT.2 2P.0 2P.1 1352 472659 1352 0.09 0.08 0.12 0.08 0.08 3.10 3.38 1467 531166 1467 0.10 0.09 0.14 0.10 0.09 4.07 4.09 1389 479441 1389 0.10 0.08 0.12 0.09 0.08 3.50 3.31 1537 595871 1537 0.12 0.10 0.15 0.11 0.11 5.20 4.27 1351 448750 1351 0.08 0.08 0.11 0.09 0.07 3.13 2.83