/
StronglyConnected.scala
51 lines (47 loc) · 1.11 KB
/
StronglyConnected.scala
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 sbt.inc
// stolen from Josh
object StronglyConnected
{
def apply[N](nodes: Iterable[N])(dependencies: N => Iterable[N]): Set[Set[N]] =
{
val stack = new collection.mutable.Stack[N]
val onStack = new collection.mutable.HashSet[N]
val scc = new collection.mutable.ArrayBuffer[Set[N]]
val index = new collection.mutable.ArrayBuffer[N]
val lowLink = new collection.mutable.HashMap[N, Int]
def tarjanImpl(v: N)
{
index += v
lowLink(v) = index.size-1
stack.push(v)
onStack += v
for(n <- dependencies(v))
{
if( !index.contains(n) )
{
tarjanImpl(n)
lowLink(v) = math.min(lowLink(v), lowLink(n))
}
else if(onStack(n))
lowLink(v) = math.min(lowLink(v), index.indexOf(n))
}
if(lowLink(v) == index.indexOf(v))
{
val components = new collection.mutable.ArrayBuffer[N]
def popLoop()
{
val popped = stack.pop()
onStack -= popped
components.append(popped)
if(popped != v) popLoop()
}
popLoop()
scc.append(components.toSet)
}
}
for(node <- nodes)
if( !index.contains(node) )
tarjanImpl(node)
scc.toSet
}
}