Safe Haskell | Safe |
---|---|
Language | Haskell2010 |
Implementation of a DAG with each node identified by a unique key.
Synopsis
- data DAG k v = DAG {}
- mkDAG :: (Show k, Ord k) => [(v, k, [k])] -> Maybe (DAG k v)
- unDAG :: DAG k v -> [(v, k, [k])]
- vertex :: Show k => DAG k v -> k -> Vertex
- node :: Show k => DAG k v -> k -> v
- edges :: Show k => DAG k v -> k -> [k]
- maybeNode :: DAG k v -> k -> Maybe v
- maybeEdges :: DAG k v -> k -> Maybe [k]
- nodeV :: DAG k v -> Vertex -> v
- keyV :: DAG k v -> Vertex -> k
- edgesV :: DAG k v -> Vertex -> [k]
- toForest :: (Show k, Ord k) => DAG k v -> Forest k
- toForestBy :: (Show k, Ord k) => (k -> k -> Ordering) -> DAG k v -> Forest k
- roots :: Ord k => DAG k v -> [k]
- leaves :: DAG k v -> [k]
DAG
A directed acyclic graph.
mkDAG :: (Show k, Ord k) => [(v, k, [k])] -> Maybe (DAG k v) Source #
Smart constructur which verifies that the graph is actually a DAG. Return Nothing if the input list constitutes a graph with cycles.
Access by key
vertex :: Show k => DAG k v -> k -> Vertex Source #
Map key to a vertex identifier. Report error if the key is not a member of the graph.
node :: Show k => DAG k v -> k -> v Source #
The node for the given key. Report error if the key is not a member of the graph.
edges :: Show k => DAG k v -> k -> [k] Source #
The edge list for the given key. Report error if the key is not a member of the graph.
maybeNode :: DAG k v -> k -> Maybe v Source #
The node for the given key. Return Nothing if the key is not a member of the graph.
maybeEdges :: DAG k v -> k -> Maybe [k] Source #
The edge list for the given key. Return Nothing if the key is not a member of the graph.
Access by vertex (index)
Conversion to forest
toForest :: (Show k, Ord k) => DAG k v -> Forest k Source #
Spanning forest of the DAG using the standard compare
function to
compare keys kept in DAG leaves. Overloaded version of the toForestBy
function.
toForestBy :: (Show k, Ord k) => (k -> k -> Ordering) -> DAG k v -> Forest k Source #
Spanning forest of the DAG. Non-overloaded version of the toForest
function. The comparison function is used to sort the list of leaves
and the spanning tree is computed with respect to the resulting order.