Data.Named.Graph

Implementation of a graph with each node identified by a unique key. It is a provisional module and it might be replaced by the standard graph from containers package in the future.

Documentation

data Graph k v

A graph.

Constructors

Graph

Fields

nodeMap :: Map k v

edgeMap :: Map k [k]

mkGraph :: Ord k => [(k, v, [k])] -> Graph k v

Make a graph from a list of (key, value, [children keys]) tuples.

node :: (Show k, Ord k) => Graph k v -> k -> v

Get node with the given key.

edges :: (Show k, Ord k) => Graph k v -> k -> [k]

Get keys of adjacent nodes for the given node key.

roots :: Ord k => Graph k v -> [k]

Return all graph roots (i.e. nodes with no parents).

disjointForest :: (Show k, Ord k) => (k -> Int) -> Graph k v -> Forest k

Spanning-like forest of a DAG. Trees in the resulting forest are disjoint with respect to their ranges. It is not checked if the input graph is actually a DAG.