Safe Haskell	Safe
Language	Haskell2010

Data.Named.DAG

Contents

DAG
Access by key
Access by vertex (index)
Conversion to forest
Utilities

Description

Implementation of a DAG with each node identified by a unique key.

Synopsis

data DAG k v = DAG {
- graph :: Graph
- nodeDesc :: Vertex -> (v, k, [k])
- maybeVertex :: k -> Maybe Vertex
}
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

data DAG k v Source #

A directed acyclic graph.

Constructors

DAG
Fields graph :: Graph The underlying graph. nodeDesc :: Vertex -> (v, k, [k]) Map vertex identifier to a node description. maybeVertex :: k -> Maybe Vertex Map key to a vertex identifier. Return Nothing if the key is not a member of the 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.

unDAG :: DAG k v -> [(v, k, [k])] Source #

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)

nodeV :: DAG k v -> Vertex -> v Source #

keyV :: DAG k v -> Vertex -> k Source #

edgesV :: DAG k v -> Vertex -> [k] Source #

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.

Utilities

roots :: Ord k => DAG k v -> [k] Source #

leaves :: DAG k v -> [k] Source #