Topological assumes that graph given is valid and that its possible to get a topological ordering. constraints are array of []int{a, b}, representing an edge going from a to b
(N int, constraints [][]int)
| 12 | // constraints are array of []int{a, b}, representing |
| 13 | // an edge going from a to b |
| 14 | func Topological(N int, constraints [][]int) []int { |
| 15 | dependencies := make([]int, N) |
| 16 | nodes := make([]int, N) |
| 17 | for i := range nodes { |
| 18 | nodes[i] = i |
| 19 | } |
| 20 | edges := make([][]bool, N) |
| 21 | for i := range edges { |
| 22 | edges[i] = make([]bool, N) |
| 23 | } |
| 24 | |
| 25 | for _, c := range constraints { |
| 26 | a := c[0] |
| 27 | b := c[1] |
| 28 | dependencies[b]++ |
| 29 | edges[a][b] = true |
| 30 | } |
| 31 | |
| 32 | var answer []int |
| 33 | for s := 0; s < N; s++ { |
| 34 | // Only start walking from top level nodes |
| 35 | if dependencies[s] == 0 { |
| 36 | route, _ := DepthFirstSearchHelper(s, N, nodes, edges, true) |
| 37 | answer = append(answer, route...) |
| 38 | } |
| 39 | } |
| 40 | |
| 41 | return answer |
| 42 | } |