dawg-0.7.1: Directed acyclic word graphs

Data.DAWG.Node

Contents

Description

Internal representation of automata nodes.

Synopsis

# Basic types

type ID = IntSource

Node identifier.

type Sym = IntSource

Internal representation of the transition symbol.

# Node

data Node a b Source

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.

Since `Leaf` nodes are distinguished from `Branch` nodes, two values equal with respect to `==` function are always kept in one `Leaf` node in the graph. It doesn't change the fact that to all `Branch` nodes one value is assigned through the epsilon transition.

Invariant: the `eps` identifier always points to the `Leaf` node. Edges in the `edgeMap`, on the other hand, point to `Branch` nodes.

Constructors

 Branch Fieldseps :: !IDEpsilon transition. edgeMap :: !(VMap b)Labeled edges outgoing from the node. Leaf Fieldsvalue :: !a

Instances

 (Eq a, Eq b, Unbox b) => Eq (Node a b) (Eq (Node a b), Ord a, Ord b, Unbox b) => Ord (Node a b) (Show a, Show b, Unbox b) => Show (Node a b) (Unbox b, Binary a, Binary b) => Binary (Node a b)

onSym :: Unbox b => Sym -> Node a b -> Maybe bSource

Transition function.

trans :: Unbox b => Node a b -> [(Sym, b)]Source

List of symbol/edge pairs outgoing from the node.

edges :: Unbox b => Node a b -> [b]Source

List of outgoing edges.

subst :: Unbox b => Sym -> b -> Node a b -> Node a bSource

Substitue edge determined by a given symbol.

toGeneric :: Node a -> Node a (Edge ())Source

Yield generic version of a specialized node.

# Edge

type Edge a = (ID, a)Source

Edge with label.

to :: Edge a -> IDSource

Destination ID.

label :: Edge a -> aSource

Edge label.

annotate :: a -> Edge b -> Edge aSource

Annotate edge wit a new label.

labeled :: a -> ID -> Edge aSource

Construct edge annotated with a given label.