Safe Haskell | None |
---|

Data.Graph is sorely lacking in several ways, This just tries to fill in some holes and provide a more convinient interface

- data Graph n
- fromGraph :: Graph n -> [(n, [n])]
- newGraph :: Ord k => [n] -> (n -> k) -> (n -> [k]) -> Graph n
- newGraph' :: Ord k => [n] -> (n -> k) -> (n -> [k]) -> (Map k Vertex, Graph n)
- newGraphReachable :: Ord k => [n] -> (n -> k) -> (n -> [k]) -> ([k] -> [n], Graph n)
- reachableFrom :: Ord k => (n -> k) -> (n -> [k]) -> [n] -> [k] -> [n]
- reachable :: Graph n -> [Vertex] -> [n]
- fromScc :: Either t [t] -> [t]
- findLoopBreakers :: (n -> Int) -> (n -> Bool) -> Graph n -> ([n], [n])
- sccGroups :: Graph n -> [[n]]
- scc :: Graph n -> [Either n [n]]
- sccForest :: Graph n -> Forest n
- dff :: Graph n -> Forest n
- components :: Graph n -> [[n]]
- topSort :: Graph n -> [n]
- cyclicNodes :: Graph n -> [n]
- toDag :: Graph n -> Graph [n]
- restitchGraph :: Ord k => (n -> k) -> (n -> [k]) -> Graph n -> Graph n
- mapGraph :: forall a b. (a -> [b] -> b) -> Graph a -> Graph b
- transitiveClosure :: Graph n -> Graph n
- transitiveReduction :: Graph n -> Graph n

# Documentation

newGraph' :: Ord k => [n] -> (n -> k) -> (n -> [k]) -> (Map k Vertex, Graph n)Source

Build a graph from a list of nodes uniquely identified by keys, with a list of keys of nodes this node should have edges to. The out-list may contain keys that don't correspond to nodes of the graph; they are ignored.

newGraphReachable :: Ord k => [n] -> (n -> k) -> (n -> [k]) -> ([k] -> [n], Graph n)Source

reachableFrom :: Ord k => (n -> k) -> (n -> [k]) -> [n] -> [k] -> [n]Source

:: (n -> Int) | fitness function, greater numbers mean more likely to be a loopbreaker |

-> (n -> Bool) | whether a node is suitable at all for a choice as loopbreaker |

-> Graph n | the graph |

-> ([n], [n]) | (loop breakers,dependency ordered nodes after loopbreaking) |

determine a set of loopbreakers subject to a fitness function loopbreakers have a minimum of their incoming edges ignored.

components :: Graph n -> [[n]]Source

cyclicNodes :: Graph n -> [n]Source

restitchGraph :: Ord k => (n -> k) -> (n -> [k]) -> Graph n -> Graph nSource

transitiveClosure :: Graph n -> Graph nSource

transitiveReduction :: Graph n -> Graph nSource