Repository navigation
Expand file tree
/
Copy pathdag.go
More file actions
219 lines (172 loc) · 5.91 KB
/
Copy pathdag.go
File metadata and controls
219 lines (172 loc) · 5.91 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
package graph
import (
"errors"
"fmt"
"sort"
)
// TopologicalSort runs a topological sort on a given directed graph and returns
// the vertex hashes in topological order. The topological order is a non-unique
// order of vertices in a directed graph where an edge from vertex A to vertex B
// implies that vertex A appears before vertex B.
//
// Note that TopologicalSort doesn't make any guarantees about the order. If there
// are multiple valid topological orderings, an arbitrary one will be returned.
// To make the output deterministic, use [StableTopologicalSort].
//
// TopologicalSort only works for directed acyclic graphs. This implementation
// works non-recursively and utilizes Kahn's algorithm.
func TopologicalSort[K comparable, T any](g Graph[K, T]) ([]K, error) {
if !g.Traits().IsDirected {
return nil, fmt.Errorf("topological sort cannot be computed on undirected graph")
}
gOrder, err := g.Order()
if err != nil {
return nil, fmt.Errorf("failed to get graph order: %w", err)
}
adjacencyMap, err := g.AdjacencyMap()
if err != nil {
return nil, fmt.Errorf("failed to get adjacency map: %w", err)
}
predecessorMap, err := g.PredecessorMap()
if err != nil {
return nil, fmt.Errorf("failed to get predecessor map: %w", err)
}
queue := make([]K, 0)
for vertex, predecessors := range predecessorMap {
if len(predecessors) == 0 {
queue = append(queue, vertex)
delete(predecessorMap, vertex)
}
}
order := make([]K, 0, gOrder)
for len(queue) > 0 {
currentVertex := queue[0]
queue = queue[1:]
order = append(order, currentVertex)
edgeMap := adjacencyMap[currentVertex]
for target := range edgeMap {
predecessors := predecessorMap[target]
delete(predecessors, currentVertex)
if len(predecessors) == 0 {
queue = append(queue, target)
delete(predecessorMap, target)
}
}
}
if len(order) != gOrder {
return nil, errors.New("topological sort cannot be computed on graph with cycles")
}
return order, nil
}
// StableTopologicalSort does the same as [TopologicalSort], but takes a function
// for comparing (and then ordering) two given vertices. This allows for a stable
// and deterministic output even for graphs with multiple topological orderings.
func StableTopologicalSort[K comparable, T any](g Graph[K, T], less func(K, K) bool) ([]K, error) {
if !g.Traits().IsDirected {
return nil, fmt.Errorf("topological sort cannot be computed on undirected graph")
}
gOrder, err := g.Order()
if err != nil {
return nil, fmt.Errorf("failed to get graph order: %w", err)
}
adjacencyMap, err := g.AdjacencyMap()
if err != nil {
return nil, fmt.Errorf("failed to get adjacency map: %w", err)
}
predecessorMap, err := g.PredecessorMap()
if err != nil {
return nil, fmt.Errorf("failed to get predecessor map: %w", err)
}
queue := make([]K, 0)
for vertex, predecessors := range predecessorMap {
if len(predecessors) == 0 {
queue = append(queue, vertex)
delete(predecessorMap, vertex)
}
}
order := make([]K, 0, gOrder)
sort.Slice(queue, func(i, j int) bool {
return less(queue[i], queue[j])
})
for len(queue) > 0 {
currentVertex := queue[0]
queue = queue[1:]
order = append(order, currentVertex)
frontier := make([]K, 0)
edgeMap := adjacencyMap[currentVertex]
for target := range edgeMap {
predecessors := predecessorMap[target]
delete(predecessors, currentVertex)
if len(predecessors) == 0 {
frontier = append(frontier, target)
delete(predecessorMap, target)
}
}
sort.Slice(frontier, func(i, j int) bool {
return less(frontier[i], frontier[j])
})
queue = append(queue, frontier...)
}
if len(order) != gOrder {
return nil, errors.New("topological sort cannot be computed on graph with cycles")
}
return order, nil
}
// TransitiveReduction returns a new graph with the same vertices and the same
// reachability as the given graph, but with as few edges as possible. The graph
// must be a directed acyclic graph.
//
// TransitiveReduction is a very expensive operation scaling with O(V(V+E)).
func TransitiveReduction[K comparable, T any](g Graph[K, T]) (Graph[K, T], error) {
if !g.Traits().IsDirected {
return nil, fmt.Errorf("transitive reduction cannot be performed on undirected graph")
}
transitiveReduction, err := g.Clone()
if err != nil {
return nil, fmt.Errorf("failed to clone the graph: %w", err)
}
adjacencyMap, err := transitiveReduction.AdjacencyMap()
if err != nil {
return nil, fmt.Errorf("failed to get adajcency map: %w", err)
}
// For each vertex in the graph, run a depth-first search from each direct
// successor of that vertex. Then, for each vertex visited within the DFS,
// inspect all of its edges. Remove the edges that also appear in the edge
// set of the top-level vertex and target the current vertex. These edges
// are redundant because their targets apparently are not only reachable
// from the top-level vertex, but also through a DFS.
for vertex, successors := range adjacencyMap {
tOrder, err := transitiveReduction.Order()
if err != nil {
return nil, fmt.Errorf("failed to get graph order: %w", err)
}
for successor := range successors {
stack := newStack[K]()
visited := make(map[K]struct{}, tOrder)
stack.push(successor)
for !stack.isEmpty() {
current, _ := stack.pop()
if _, ok := visited[current]; ok {
continue
}
visited[current] = struct{}{}
stack.push(current)
for adjacency := range adjacencyMap[current] {
if _, ok := visited[adjacency]; ok {
if stack.contains(adjacency) {
// If the current adjacency is both on the stack and
// has already been visited, there is a cycle.
return nil, fmt.Errorf("transitive reduction cannot be performed on graph with cycle")
}
continue
}
if _, ok := adjacencyMap[vertex][adjacency]; ok {
_ = transitiveReduction.RemoveEdge(vertex, adjacency)
}
stack.push(adjacency)
}
}
}
}
return transitiveReduction, nil
}