isAcyclic traverses the given graph starting from a specific node using depth-first search using recursion. If a cycle is detected, it returns the node that contains the "last" edge that introduces a cycle. For example, running isAcyclic starting from 1 on the following graph will return 3. 1 -> 2
(g graph, u int, info cycleInfo, path []int)
| 66 | // graph will return 3. |
| 67 | // 1 -> 2 -> 3 -> 1 |
| 68 | func isAcyclic(g graph, u int, info cycleInfo, path []int) []int { |
| 69 | // We've already verified that there are no cycles from this node. |
| 70 | if info[u].Visited { |
| 71 | return nil |
| 72 | } |
| 73 | info[u].Visited = true |
| 74 | info[u].OnStack = true |
| 75 | |
| 76 | path = append(path, u) |
| 77 | for _, v := range g.edgesFrom(u) { |
| 78 | if !info[v].Visited { |
| 79 | if cycle := isAcyclic(g, v, info, path); len(cycle) > 0 { |
| 80 | return cycle |
| 81 | } |
| 82 | } else if info[v].OnStack { |
| 83 | // We've found a cycle, and we have a full path back. |
| 84 | // Prune it down to just the cyclic nodes. |
| 85 | cycle := path |
| 86 | for i := len(cycle) - 1; i >= 0; i-- { |
| 87 | if cycle[i] == v { |
| 88 | cycle = cycle[i:] |
| 89 | break |
| 90 | } |
| 91 | } |
| 92 | |
| 93 | // Complete the cycle by adding this node to it. |
| 94 | return append(cycle, v) |
| 95 | } |
| 96 | } |
| 97 | info[u].OnStack = false |
| 98 | return nil |
| 99 | } |
| 100 | |
| 101 | // cycleNode keeps track of a single node's info for cycle detection. |
| 102 | type cycleNode struct { |