As part of my application as an intern, I was asked to implement Tarjan's algorithm for finding strongly connected components.

Just a brief overview to explain the basic structure of the project

You can find the Tarjan implementation inside the Tarjan.kt file.

The Node.kt interface and the sample implementation TarjanNode.kt can be found inside the node subdirectory.

Helper classes, like the TarjanNodeData.kt, can be found inside the helper subdirectory. This class packs all the data needed per node inside a single class, which greatly helps the readability and cache-efficiency of the Tarjan implementation.

All the tests are divided into two groups: TarjanFunctionalTests.kt and TarjanEdgeCaseTests.kt.

To further ease the testing of huge graphs, a dynamic testing framework was created, which can found inside the helper subdirectory. For example, the TarjanTestHelper.kt file verifies the output of the Tarjan implementation, by checking the count and content of the strongly connected components (SCC) compared to the Kosaraju.kt algorithm.