Safe Haskell | None |
---|

- newtype Graph n e = Graph {}
- invariant :: Ord n => Graph n e -> Bool
- edges :: Ord n => Graph n e -> [(n, n, e)]
- edgesFrom :: Ord n => Graph n e -> [n] -> [(n, n, e)]
- nodes :: Ord n => Graph n e -> Set n
- filterEdges :: Ord n => (e -> Bool) -> Graph n e -> Graph n e
- fromNodes :: Ord n => [n] -> Graph n e
- fromList :: (SemiRing e, Ord n) => [(n, n, e)] -> Graph n e
- empty :: Graph n e
- singleton :: Ord n => n -> n -> e -> Graph n e
- insert :: (SemiRing e, Ord n) => n -> n -> e -> Graph n e -> Graph n e
- removeNode :: Ord n => n -> Graph n e -> Graph n e
- removeEdge :: Ord n => n -> n -> Graph n e -> Graph n e
- union :: (SemiRing e, Ord n) => Graph n e -> Graph n e -> Graph n e
- unions :: (SemiRing e, Ord n) => [Graph n e] -> Graph n e
- lookup :: Ord n => n -> n -> Graph n e -> Maybe e
- neighbours :: Ord n => n -> Graph n e -> [(n, e)]
- sccs' :: Ord n => Graph n e -> [SCC n]
- sccs :: Ord n => Graph n e -> [[n]]
- acyclic :: Ord n => Graph n e -> Bool
- transitiveClosure1 :: (Eq e, SemiRing e, Ord n) => Graph n e -> Graph n e
- transitiveClosure :: (Eq e, SemiRing e, Ord n) => Graph n e -> Graph n e
- findPath :: (SemiRing e, Ord n) => (e -> Bool) -> n -> n -> Graph n e -> Maybe e
- allPaths :: (SemiRing e, Ord n, Ord c) => (e -> c) -> n -> n -> Graph n e -> [e]
- nodeIn :: (Ord n, Arbitrary n) => Graph n e -> Gen n
- edgeIn :: (Ord n, Arbitrary n, Arbitrary e) => Graph n e -> Gen (n, n, e)
- tests :: IO Bool

# Documentation

edgesFrom :: Ord n => Graph n e -> [n] -> [(n, n, e)]Source

All edges originating in the given nodes.

fromNodes :: Ord n => [n] -> Graph n eSource

Constructs a completely disconnected graph containing the given nodes.

removeNode :: Ord n => n -> Graph n e -> Graph n eSource

Removes the given node, and all corresponding edges, from the graph.

removeEdge :: Ord n => n -> n -> Graph n e -> Graph n eSource

`removeEdge n1 n2 g`

removes the edge going from `n1`

to `n2`

, if
any.

neighbours :: Ord n => n -> Graph n e -> [(n, e)]Source

sccs' :: Ord n => Graph n e -> [SCC n]Source

The graph's strongly connected components, in reverse topological order.

sccs :: Ord n => Graph n e -> [[n]]Source

The graph's strongly connected components, in reverse topological order.

transitiveClosure1 :: (Eq e, SemiRing e, Ord n) => Graph n e -> Graph n eSource

Computes the transitive closure of the graph.

Note that this algorithm is not guaranteed to be correct (or terminate) for arbitrary semirings.

This function operates on the entire graph at once.

transitiveClosure :: (Eq e, SemiRing e, Ord n) => Graph n e -> Graph n eSource

Computes the transitive closure of the graph.

Note that this algorithm is not guaranteed to be correct (or terminate) for arbitrary semirings.

This function operates on one strongly connected component at a time.

allPaths :: (SemiRing e, Ord n, Ord c) => (e -> c) -> n -> n -> Graph n e -> [e]Source

`allPaths classify a b g`

returns a list of pathes (accumulated edge weights)
from node `a`

to node `b`

in `g`

.
Alternative intermediate pathes are only considered if they
are distinguished by the `classify`

function.

nodeIn :: (Ord n, Arbitrary n) => Graph n e -> Gen nSource

Generates a node from the graph. (Unless the graph is empty.)