45 lines
1.2 KiB
Go
45 lines
1.2 KiB
Go
// Package sort provides topological sorting for directed acyclic graphs.
|
|
package sort
|
|
|
|
// Node is a generic interface representing a graph node.
|
|
type Node[T any] interface {
|
|
// Value returns the value of the node.
|
|
Value() T
|
|
// Adjacencies returns a slice of nodes adjacent to this node (outgoing edges).
|
|
Adjacencies() []Node[T]
|
|
}
|
|
|
|
// TopoSort performs a topological sort on a slice of nodes in place using depth-first search.
|
|
// Nodes are sorted such that for every directed edge from node A to node B, A comes before B in the result.
|
|
func TopoSort[T any](nodes []Node[T]) {
|
|
v := make(map[Node[T]]bool)
|
|
pos := 0
|
|
var dfs func(Node[T])
|
|
dfs = func(n Node[T]) {
|
|
v[n] = true
|
|
for _, e := range n.Adjacencies() {
|
|
if !v[e] {
|
|
dfs(e)
|
|
}
|
|
}
|
|
nodes[pos] = n
|
|
pos++
|
|
}
|
|
|
|
for _, n := range nodes {
|
|
if !v[n] {
|
|
dfs(n)
|
|
}
|
|
}
|
|
}
|
|
|
|
// RTopoSort performs a reverse topological sort on a slice of nodes in place.
|
|
// Nodes are sorted such that for every directed edge from node A to node B, B comes before A in the result.
|
|
func RTopoSort[T any](nodes []Node[T]) {
|
|
TopoSort(nodes)
|
|
|
|
for i, j := 0, len(nodes)-1; i < j; i, j = i+1, j-1 {
|
|
nodes[i], nodes[j] = nodes[j], nodes[i]
|
|
}
|
|
}
|