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
5package dag
6
7// Transpose reverses all edges in g.
8func (g *Graph) Transpose() {
9	old := g.edges
10
11	g.edges = make(map[string]map[string]bool)
12	for _, n := range g.Nodes {
13		g.edges[n] = make(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.
24func (g *Graph) Topo() []string {
25	topo := make([]string, 0, len(g.Nodes))
26	marks := make(map[string]bool)
27
28	var visit func(n string)
29	visit = func(n string) {
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.
50func (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