| Maintainer | Simon Meier <iridcode@gmail.com> |
|---|---|
| Safe Haskell | Safe-Infered |
Data.DAG.Simple
Description
Simple vertice list based representation of DAGs and some common operations on it.
- type Relation a = [(a, a)]
- inverse :: Relation a -> Relation a
- image :: Eq a => a -> Relation a -> [a]
- reachableSet :: Ord a => [a] -> [(a, a)] -> Set a
- restrict :: Eq a => (a -> Bool) -> Relation a -> Relation a
- dfsLoopBreakers :: Ord a => [(a, a)] -> [a]
- cyclic :: Ord a => [(a, a)] -> Bool
- toposort :: Ord a => [(a, a)] -> [a]
Computing with binary relations
reachableSet :: Ord a => [a] -> [(a, a)] -> Set aSource
Compute the set of nodes reachable from the given set of nodes.
restrict :: Eq a => (a -> Bool) -> Relation a -> Relation aSource
Restrict a relation to elements satisfying a predicate.
Cycles
dfsLoopBreakers :: Ord a => [(a, a)] -> [a]Source
Compute a minimal set of loop-breakers using a greedy DFS strategy. A set of loop-breakers is a set of nodes such that removing them ensures the acyclicity of the relation. It is minimal, if no node can be removed from the set.