khenaidoo | ac63710 | 2019-01-14 15:44:34 -0500 | [diff] [blame] | 1 | package goraph |
| 2 | |
| 3 | // TopologicalSort does topological sort(ordering) with DFS. |
| 4 | // It returns true if the graph is a DAG (no cycle, with a topological sort). |
| 5 | // False if the graph is not a DAG (cycle, with no topological sort). |
| 6 | // |
| 7 | // 0. TopologicalSort(G) |
| 8 | // 1. |
| 9 | // 2. L = Empty list that will contain the sorted nodes |
| 10 | // 3. isDAG = true |
| 11 | // 4. |
| 12 | // 5. for each vertex v in G: |
| 13 | // 6. |
| 14 | // 7. if v.color == "white": |
| 15 | // 8. |
| 16 | // 9. topologicalSortVisit(v, L, isDAG) |
| 17 | // 10. |
| 18 | // 11. |
| 19 | // 12. |
| 20 | // 13. |
| 21 | // 14. topologicalSortVisit(v, L, isDAG) |
| 22 | // 15. |
| 23 | // 16. if v.color == "gray": |
| 24 | // 17. isDAG = false |
| 25 | // 18. return |
| 26 | // 19. |
| 27 | // 20. if v.color == "white": |
| 28 | // 21. |
| 29 | // 22. v.color = "gray": |
| 30 | // 23. |
| 31 | // 24. for each child vertex w of v: |
| 32 | // 25. topologicalSortVisit(w, L, isDAG) |
| 33 | // 26. |
| 34 | // 27. v.color = "black" |
| 35 | // 28. L.push_front(v) |
| 36 | // |
| 37 | func TopologicalSort(g Graph) ([]ID, bool) { |
| 38 | |
| 39 | // L = Empty list that will contain the sorted nodes |
| 40 | L := []ID{} |
| 41 | isDAG := true |
| 42 | color := make(map[ID]string) |
| 43 | for v := range g.GetNodes() { |
| 44 | color[v] = "white" |
| 45 | } |
| 46 | |
| 47 | // for each vertex v in G: |
| 48 | for v := range g.GetNodes() { |
| 49 | // if v.color == "white": |
| 50 | if color[v] == "white" { |
| 51 | // topologicalSortVisit(v, L, isDAG) |
| 52 | topologicalSortVisit(g, v, &L, &isDAG, &color) |
| 53 | } |
| 54 | } |
| 55 | |
| 56 | return L, isDAG |
| 57 | } |
| 58 | |
| 59 | func topologicalSortVisit( |
| 60 | g Graph, |
| 61 | id ID, |
| 62 | L *[]ID, |
| 63 | isDAG *bool, |
| 64 | color *map[ID]string, |
| 65 | ) { |
| 66 | |
| 67 | // if v.color == "gray": |
| 68 | if (*color)[id] == "gray" { |
| 69 | // isDAG = false |
| 70 | *isDAG = false |
| 71 | return |
| 72 | } |
| 73 | |
| 74 | // if v.color == "white": |
| 75 | if (*color)[id] == "white" { |
| 76 | // v.color = "gray": |
| 77 | (*color)[id] = "gray" |
| 78 | |
| 79 | // for each child vertex w of v: |
| 80 | cmap, err := g.GetTargets(id) |
| 81 | if err != nil { |
| 82 | panic(err) |
| 83 | } |
| 84 | for w := range cmap { |
| 85 | // topologicalSortVisit(w, L, isDAG) |
| 86 | topologicalSortVisit(g, w, L, isDAG, color) |
| 87 | } |
| 88 | |
| 89 | // v.color = "black" |
| 90 | (*color)[id] = "black" |
| 91 | |
| 92 | // L.push_front(v) |
| 93 | temp := make([]ID, len(*L)+1) |
| 94 | temp[0] = id |
| 95 | copy(temp[1:], *L) |
| 96 | *L = temp |
| 97 | } |
| 98 | } |