This repository has been archived by the owner on Jul 2, 2023. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
TarjanTestHelper.kt
51 lines (42 loc) · 1.75 KB
/
TarjanTestHelper.kt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
package helper
import Task
import node.Node
import org.junit.jupiter.api.Assertions
import org.junit.jupiter.api.Assertions.assertEquals
import org.junit.jupiter.api.Assertions.assertTrue
import org.junit.jupiter.api.assertDoesNotThrow
/**
* A collection of functions to test the tarjan implementation
*/
internal object TarjanTestHelper {
/**
* Asserts the validity of the computed strongly connected components of a given [graph]
* through a comparison of the tarjan results with those of the [kosaraju algorithm](https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm)
*/
fun validateTarjanResults(graph: List<Node<*>?>?) {
if (graph.isNullOrEmpty())
return
val tarjanResult = Task.tarjan(graph)
Assertions.assertFalse(tarjanResult == null)
val countOfNodes = tarjanResult!!.sumOf { it.count() }
assertEquals(graph.filterNotNull().count(), countOfNodes)
val kosarajuResult = Kosaraju.kosaraju(graph)
assertEquals(kosarajuResult.size, tarjanResult.size)
kosarajuResult.forEach { scc ->
val possibleTarjanLists = tarjanResult.filter { scc.size == it.size }
assertTrue(possibleTarjanLists.isNotEmpty())
var lastIndex = 0
scc.forEachIndexed { index, node ->
var currentIndex = -1
assertDoesNotThrow {
currentIndex =
possibleTarjanLists.indexOf(possibleTarjanLists.first { list -> list.contains(node) })
}
// check if all nodes are in the same strongly connected components
if (index > 0)
assertTrue(currentIndex == lastIndex)
lastIndex = currentIndex
}
}
}
}