-
Notifications
You must be signed in to change notification settings - Fork 17
/
Copy pathdirected_cycle.go
74 lines (61 loc) · 1.68 KB
/
directed_cycle.go
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
74
package digraph
// import "log"
import "github.com/youngzhu/algs4-go/fund"
// Does a given digraph have a directed cycle?
// Solves this problem using depth-first search
type DirectedCycle struct {
marked []bool // marked[v]: has vertex v been marked?
edgeTo []int // edgeTo[v]: previous vertex on path to v
onStack []bool // onStack[v]: is vertex on the stack?
cycle *fund.Stack // directed cycle (or nil if no such cycle)
}
func NewDirectedCycle(g IDigraph) *DirectedCycle {
marked := make([]bool, g.V())
edgeTo := make([]int, g.V())
onStack := make([]bool, g.V())
dc := &DirectedCycle{marked, edgeTo, onStack, nil}
// log.Println(dc.graph.String())
for v := 0; v < g.V(); v++ {
if !dc.marked[v] && dc.cycle == nil {
dc.dfs(g, v)
}
}
return dc
}
// run DFS and find a directed cycle
// must use pointer (*), otherwise dc.cycle wouldn't change
func (dc *DirectedCycle) dfs(g IDigraph, v int) {
dc.onStack[v] = true
dc.marked[v] = true
for _, it := range g.Adj(v) {
w := it.(int)
// short circuit if directed cycle found
// log.Printf("cycle: %v", dc.cycle!= nil)
if dc.cycle != nil {
return
} else if !dc.marked[w] { // found new vertex, so recur
dc.edgeTo[w] = v
dc.dfs(g, w)
} else if dc.onStack[w] { // trace back directed cycle
cycle := fund.NewStack()
for x := v; x != w; x = dc.edgeTo[x] {
cycle.Push(x)
}
cycle.Push(w)
cycle.Push(v)
// log.Println(w)
dc.cycle = cycle
}
}
dc.onStack[v] = false
}
// Does the digraph have a directed cycle?
func (dc *DirectedCycle) HasCycle() bool {
return dc.cycle != nil
}
func (dc *DirectedCycle) Cycle() fund.Iterator {
if dc.HasCycle() {
return dc.cycle.Iterator()
}
return nil
}