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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
package graph
// StrongComponents produces a partition of g's vertices into its
// strongly connected components.
//
// A component is strongly connected if all its vertices are reachable
// from every other vertex in the component.
// Each vertex of the graph appears in exactly one of the strongly
// connected components, and any vertex that is not on a directed cycle
// forms a strongly connected component all by itself.
func StrongComponents(g Iterator) [][]int {
n := g.Order()
s := &scc{
graph: g,
visited: make([]bool, n),
lowLink: make([]int, n),
}
components := [][]int{}
for v := range s.visited {
if !s.visited[v] {
components = s.append(components, v)
}
}
return components
}
// Tarjan's algorithm
type scc struct {
graph Iterator
visited []bool
stack []int
lowLink []int
time int
}
// Make a depth-first search starting at v and append all strongly
// connected components of the visited subgraph to comps.
func (s *scc) append(components [][]int, v int) [][]int {
// A vertex remains on this stack after it has been visited iff
// there is a path from it to some vertex earlier on the stack.
s.stack = append(s.stack, v)
// lowLink[v] is the smallest vertex known to be reachable from v.
s.lowLink[v] = s.time
s.time++
newComponent := true
s.visited[v] = true
s.graph.Visit(v, func(w int, _ int64) (skip bool) {
if !s.visited[w] {
components = s.append(components, w)
}
if s.lowLink[v] > s.lowLink[w] {
s.lowLink[v] = s.lowLink[w]
newComponent = false
}
return
})
if !newComponent {
return components
}
var comp []int
for {
n := len(s.stack) - 1
w := s.stack[n]
s.stack = s.stack[:n]
s.lowLink[w] = int(^uint(0) >> 1) // maxint
comp = append(comp, w)
if v == w {
return append(components, comp)
}
}
}
|
