Safe Haskell | None |
---|
The module provides a representation of a tree where all equivalent nodes
(i.e. trees equal with respect to the ==
function) are compressed to one
directed acyclic graph (DAG) node with unique identifier. Alternatively,
it can be thought of as a minimal acyclic finite-state automata.
- data Node a = Node {}
- type Id = Int
- onChar :: Char -> Node a -> Maybe Id
- subst :: Char -> Id -> Node a -> Node a
- data Graph a = Graph {}
- empty :: Graph a
- size :: Graph a -> Int
- nodeBy :: Id -> Graph a -> Node a
- nodeID :: Ord a => Node a -> Graph a -> Id
- insert :: Ord a => Node a -> Graph a -> (Id, Graph a)
- delete :: Ord a => Node a -> Graph a -> Graph a
Node
Two nodes (states) belong to the same equivalence class (and, consequently, they must be represented as one node in the graph) iff they are equal with respect to their values and outgoing edges.
onChar :: Char -> Node a -> Maybe IdSource
Identifier of the child determined by the given character.
subst :: Char -> Id -> Node a -> Node aSource
Substitue the identifier of the child determined by the given character.
Graph
A set of nodes. To every node a unique identifier is assigned. Invariants:
- freeIDs \intersection occupiedIDs = \emptySet,
- freeIDs \sum occupiedIDs = {0, 1, ..., |freeIDs \sum occupiedIDs| - 1},
where occupiedIDs = elemSet idMap.
TODO: Is it possible to merge freeIDs with ingoMap to save some memory?
Graph | |
|
insert :: Ord a => Node a -> Graph a -> (Id, Graph a)Source
Insert node into the graph. If the node was already a member of the graph, just increase the number of ingoing paths. NOTE: Number of ingoing paths will not be changed for any ancestors of the node, so the operation alone will not ensure that properties of the graph are preserved.
delete :: Ord a => Node a -> Graph a -> Graph aSource
Delete node from the graph. If the node was present in the graph at multiple positions, just decrease the number of ingoing paths. NOTE: The function does not delete descendant nodes which may become inaccesible nor does it change the number of ingoing paths for any ancestor of the node.