Util.Graph

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

Documentation

data Graph n

Instances

Functor Graph

Show n => Show (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)

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)

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

reachable :: Graph n -> [Vertex] -> [n]

fromScc :: Either t [t] -> [t]

findLoopBreakers

Arguments

:: (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.

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