Clash.Util.Graph

Collection of utilities

Documentation

topSort

Arguments

:: [(Int, a)]

Nodes

-> [(Int, Int)]

Edges

-> Either String [a]

Error message or topologically sorted nodes

See: https://en.wikipedia.org/wiki/Topological_sorting. This function errors if edges mention nodes not mentioned in the node list or if the given graph contains cycles.

reverseTopSort

Arguments

:: [(Int, a)]

Nodes

-> [(Int, Int)]

Edges

-> Either String [a]

Reversely, topologically sorted nodes

Same as `reverse (topSort nodes edges)` if alternative representations are considered the same. That is, topSort might produce multiple answers and still deliver on its promise of yielding a topologically sorted node list. Likewise, this function promises one of those lists in reverse, but not necessarily the reverse of topSort itself.