Mikan
Safe HaskellNone
LanguageHaskell2010

Mikan.Utils.Graph.TopSort

Description

Topological sorting.

Synopsis

Documentation

topSort :: Ord n => Set n -> [(n, n)] -> Maybe [n] Source #

Topological sort with smallest-numbered available vertex first. Returns 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.