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
|
package graph
// TopSort returns a topological ordering of the vertices in
// a directed acyclic graph; if the graph is not acyclic,
// no such ordering exists and ok is set to false.
//
// In a topological order v comes before w for every directed edge from v to w.
func TopSort(g Iterator) (order []int, ok bool) {
order, ok = topsort(g, true)
return
}
// Acyclic tells if g has no cycles.
func Acyclic(g Iterator) bool {
_, acyclic := topsort(g, false)
return acyclic
}
// Kahn's algorithm
func topsort(g Iterator, output bool) (order []int, acyclic bool) {
indegree := make([]int, g.Order())
for v := range indegree {
g.Visit(v, func(w int, _ int64) (skip bool) {
indegree[w]++
return
})
}
// Invariant: this queue holds all vertices with indegree 0.
var queue []int
for v, degree := range indegree {
if degree == 0 {
queue = append(queue, v)
}
}
order = []int{}
vertexCount := 0
for len(queue) > 0 {
v := queue[0]
queue = queue[1:]
if output {
order = append(order, v)
}
vertexCount++
g.Visit(v, func(w int, _ int64) (skip bool) {
indegree[w]--
if indegree[w] == 0 {
queue = append(queue, w)
}
return
})
}
if vertexCount != g.Order() {
return
}
acyclic = true
return
}
|
