this function can do HasCycle() job but it is slower
()
| 48 | |
| 49 | // this function can do HasCycle() job but it is slower |
| 50 | func (g *Graph) FindAllCycles() []Graph { |
| 51 | all := map[int]struct{}{} |
| 52 | visiting := map[int]struct{}{} |
| 53 | visited := map[int]struct{}{} |
| 54 | |
| 55 | allCycles := []Graph{} |
| 56 | |
| 57 | for v := range g.edges { |
| 58 | all[v] = struct{}{} |
| 59 | } |
| 60 | |
| 61 | for current := range all { |
| 62 | foundCycle, parents := g.findAllCyclesHelper(current, all, visiting, visited) |
| 63 | |
| 64 | if foundCycle { |
| 65 | foundCycleFromCurrent := false |
| 66 | //this loop remove additional vertex from detected cycle |
| 67 | //using foundCycleFromCurrent bool to make sure after removing vertex we still have cycle |
| 68 | for i := len(parents) - 1; i > 0; i-- { |
| 69 | if parents[i][1] == parents[0][0] { |
| 70 | parents = parents[:i+1] |
| 71 | foundCycleFromCurrent = true |
| 72 | } |
| 73 | } |
| 74 | if foundCycleFromCurrent { |
| 75 | graph := Graph{Directed: true} |
| 76 | for _, edges := range parents { |
| 77 | graph.AddEdge(edges[1], edges[0]) |
| 78 | } |
| 79 | allCycles = append(allCycles, graph) |
| 80 | } |
| 81 | |
| 82 | } |
| 83 | |
| 84 | } |
| 85 | |
| 86 | return allCycles |
| 87 | |
| 88 | } |
| 89 | |
| 90 | func (g Graph) findAllCyclesHelper(current int, all, visiting, visited map[int]struct{}) (bool, [][]int) { |
| 91 | parents := [][]int{} |