| Safe Haskell | None |
|---|
Data.DAWG.Graph
Description
The module provides a directed acyclic graph (DAG) implementation
where all equivalent nodes (i.e. roots of DAGs equal with respect to
the == function) are compressed to one node with unique identifier.
It can be alternatively thought of as a
minimal acyclic finite-state automata.
- data Node a = Node {}
- type Id = Int
- leaf :: Node a
- 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.
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?
Constructors
| Graph | |