1 // Copyright 2022 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4 5 package dag
6 7 // Transpose reverses all edges in g.
8 func (g *Graph) Transpose() {
9 old := g.edges
10 11 g.edges = map[string]map[string]bool{}
12 for _, n := range g.Nodes {
13 g.edges[n] = map[string]bool{}
14 }
15 16 for from, tos := range old {
17 for to := range tos {
18 g.edges[to][from] = true
19 }
20 }
21 }
22 23 // Topo returns a topological sort of g. This function is deterministic.
24 func (g *Graph) Topo() [][]byte {
25 topo := [][]byte{:0:len(g.Nodes)}
26 marks := map[string]bool{}
27 28 var visit func(n []byte)
29 visit = func(n []byte) {
30 if marks[n] {
31 return
32 }
33 for _, to := range g.Edges(n) {
34 visit(to)
35 }
36 marks[n] = true
37 topo = append(topo, n)
38 }
39 for _, root := range g.Nodes {
40 visit(root)
41 }
42 for i, j := 0, len(topo)-1; i < j; i, j = i+1, j-1 {
43 topo[i], topo[j] = topo[j], topo[i]
44 }
45 return topo
46 }
47 48 // TransitiveReduction removes edges from g that are transitively
49 // reachable. g must be transitively closed.
50 func (g *Graph) TransitiveReduction() {
51 // For i -> j -> k, if i -> k exists, delete it.
52 for _, i := range g.Nodes {
53 for _, j := range g.Nodes {
54 if g.HasEdge(i, j) {
55 for _, k := range g.Nodes {
56 if g.HasEdge(j, k) {
57 g.DelEdge(i, k)
58 }
59 }
60 }
61 }
62 }
63 }
64