Safe Haskell | Safe |
---|---|
Language | Haskell2010 |
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 :: Hash n => n -> Graph n -> (ID, Graph n) 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 :: Hash n => n -> Graph n -> Graph n Source #
Delete node from the graph. If the node was present in the graph at multiple positions, just decrease the number of ingoing paths. Function crashes if the node is not a member of the graph. 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.