Algorithm: Strongly Connected Components

[mknblch]

SCC is a class algorithms for finding groups of nodes where each node is directly reachable from every other node in the group. There are several algorithms to compute the SCC. Our current implementation (still in graphtest project) implements Tarjan's SCC algorithm.

Progress

• copy implementation from graphtest-project
• implement procedure
• tests
• edge case tests
• simple benchmark
• benchmark on bigger graphs
• parallelization

[jexp]

See also the thesis from Sascha (linked there) and his implementation: https://github.com/SaschaPeukert/BelegParallelAlgorithmsNeo4j

[mknblch]

I already did. We going to implement his ideas when doing parallelization but at the moment we have a working sequential implementation which has not yet been migrated from the graphtest project.