Agda.Utils.Graph.TopSort

1 value

PackageAgda-2.8.0.2
Exports1
LanguageHaskell2010
LicenceMIT
SourceTopSort.hs

valuetopSort :: Ord n => Set n -> [(n, n)] -> Maybe [n]

topoligical sort with smallest-numbered available vertex first | input: nodes, edges | output is Nothing if the graph is not a DAG Note: should be stable to preserve order of generalizable variables. Algorithm due to Richard Eisenberg, and works by walking over the list left-to-right and moving each node the minimum distance left to guarantee topological ordering.