A golang implementation of topological sorting algorithms for fast ordering.
$ go get -u github.com/amwolff/gorder
Check cmd/example/example.go for example usage.
$ go run cmd/example/example.go
Solution (Kahn): [1 {3.141592653589793} 3 5 4]
Solution (DFS-based): [1 {3.141592653589793} 3 5 4]
-
Maps are one of the common ways to store graphs in Go. The
TopologicalSortfunction input supportsmap[interface{}][]interface{}maps. -
Sub-package
dageneratorwas developed and used for generating random DAGs for performance tests (cmd/measurementsshould be rewritten as benchmarks). -
Implementation of Kahn's algorithm does pre-computation in the beginning of its work in order to calculate indegree of every vertex in the graph. This may be split into two separate algorithms/functions in the future:
- one that doesn't take any additional input but the graph (current implementation)
- and one that takes additional input of indegrees