This pages shows timings of C++ implementations of three Strong Components algorithms: Path (Gabow), LOWPOINT (Tarjan), & 2-Pass (Kosaraju-Sharir). Timings for 2-Pass do not include constructing the reverse digraph. Table I: Randomly oriented grid graphs. Path runs about 20% faster than LOWPOINT. 2-Pass runs about 40% slower than LOWPOINT. Table II: Random dense digraphs. Path is slightly faster than LOWPOINT, sometimes 10%. 2-Pass is close to 100% slower. Table III: Random mixed digraphs. Path is slightly faster than LOWPOINT. 2-Pass is close to 100% slower. Table I: Random Grid Digraphs #vertices #edges #SCC's Path LOWPOINT 2-Pass 445116 888887 169817 0.53 0.71 0.89 607459 1213338 232670 0.73 1.00 1.23 724122 1446541 274527 0.91 1.23 1.56 612380 1223176 232222 0.80 1.00 1.37 560763 1120002 213301 0.73 0.89 1.27 662109 1322588 257284 0.87 1.07 1.52 357994 714789 137076 0.47 0.58 0.82 782280 1562781 300346 1.02 1.31 1.81 600320 1199074 228100 0.80 0.98 1.40 652098 1302577 248725 0.86 1.07 1.53 862978 1724097 332585 1.12 1.62 2.00 512442 1023451 194143 0.68 0.82 1.19 618240 1234876 236636 0.81 1.02 1.45 475139 948898 184143 0.61 0.78 1.09 517398 1033325 199230 0.68 0.84 1.20 467928 934470 179005 0.62 0.76 1.09 377553 753872 144090 0.51 0.63 0.88 346465 691744 132870 0.46 0.56 0.80 364800 728390 141170 0.48 0.59 0.85 854104 1706358 324166 1.12 1.41 2.00 759228 1516712 290601 1.02 1.29 1.77 574758 1147987 219220 0.76 0.95 1.35 861840 1721823 328097 1.15 1.43 2.02 431675 862018 164543 0.57 0.70 1.01 635481 1269352 242105 0.85 1.06 1.47 883116 1764349 332020 1.18 1.50 2.08 454896 908439 177311 0.59 0.74 1.05 493014 984619 189515 0.66 0.82 1.14 588288 1175042 227386 0.78 0.97 1.38 535847 1070206 206272 0.71 0.87 1.24 Table II: Random Dense Digraphs #vertices #edges #SCC's Path LOWPOINT 2-Pass 5863 688920 1 0.27 0.30 0.54 6897 950984 1 0.37 0.42 0.73 8250 1361597 1 0.54 0.58 1.06 9627 1855924 1 0.72 0.78 1.43 7254 1053440 1 0.42 0.44 0.82 6793 923595 1 0.37 0.40 0.71 7916 1255085 1 0.50 0.54 0.97 7062 999599 1 0.40 0.43 0.78 9926 1973486 1 0.76 0.83 1.54 8321 1384510 1 0.55 0.59 1.09 5377 578748 1 0.24 0.25 0.45 8800 1547439 1 0.62 0.67 1.21 8518 1453234 1 0.58 0.63 1.13 5208 543071 1 0.22 0.24 0.43 8911 1587839 1 0.63 0.68 1.25 8708 1517762 1 0.61 0.65 1.19 8902 1586425 1 0.63 0.70 1.24 7279 1059764 1 0.43 0.45 0.83 6163 760129 1 0.31 0.32 0.59 6062 735171 1 0.30 0.32 0.57 7676 1179712 1 0.47 0.51 0.93 8490 1443436 1 0.58 0.66 1.23 9687 1878201 1 0.75 0.79 1.48 7494 1123922 1 0.45 0.48 0.87 9343 1746870 1 0.70 0.75 1.36 7740 1201481 1 0.48 0.52 0.95 8084 1308611 1 0.54 0.56 1.05 6015 723528 1 0.29 0.32 0.58 9296 1728917 1 0.70 0.76 1.37 6182 764785 1 0.31 0.33 0.59 Table III: Random Mixed Digraphs #vertices #edges #SCC's Path LOWPOINT 2-Pass 1510 1160745 3 0.44 0.46 0.87 1033 531354 3 0.20 0.21 0.40 1319 888940 1 0.33 0.35 0.66 1362 933127 2 0.35 0.37 0.74 1524 1137576 1 0.42 0.45 0.85 1601 1284178 4 0.48 0.50 0.96 1661 1362798 1 0.52 0.53 1.02 1202 744006 3 0.28 0.29 0.55 1504 1103091 2 0.42 0.43 0.81 1076 564421 4 0.22 0.22 0.42 1236 781618 2 0.30 0.30 0.59 1589 1253380 3 0.47 0.48 0.94 1751 1546958 1 0.58 0.61 1.15 1423 1019746 1 0.38 0.39 0.77 1861 1752361 2 0.66 0.68 1.31 1961 1950116 2 0.73 0.77 1.44 1583 1236499 4 0.47 0.49 0.91 1403 1020784 2 0.38 0.40 0.77 1181 692209 2 0.27 0.27 0.52 1683 1426216 3 0.54 0.56 1.06 1837 1723565 3 0.66 0.67 1.30 1679 1406719 2 0.55 0.55 1.05 1042 541535 1 0.20 0.21 0.40 1683 1403980 6 0.53 0.55 1.05 1930 1878495 3 0.70 0.72 1.41 1709 1445670 2 0.55 0.56 1.08 1175 702707 1 0.27 0.27 0.53 1077 581621 4 0.22 0.23 0.43 1930 1890813 4 0.71 0.74 1.42 1440 1004294 5 0.38 0.40 0.75