Safe Haskell | None |
---|
Internal representation of the Data.DAWG automaton. Names in this module correspond to a graphical representation of automaton: nodes refer to states and edges refer to transitions.
Documentation
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 reduce
the memory footprint?
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 descendants 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 descendant of the node.