Spec Automaton
Representation of a automaton graph.

Extends Graph
All Extended Graph
All Subcl's WordGraph
All Impl'd AssignableConcept, ContainerConcept, DestructibleConcept
Defined in <seqan/graph_types.h>
Signature template <[typename TAlphabet[, typename TCargo[, typename TSpec]]]> class Graph<Automaton<TAlphabet, TCargo, TSpec>;

Template Parameters

TAlphabet The alphabet type used for transition labels. Default: char.
TCargo The cargo type that can be attached to the edges. Default: void.
TSpec Specializing type. Default: Default. Use WithoutEdgeId here to omit edge ids. NB: if edges to not store ids then external property maps do not work.

Member Function Overview

Member Functions Inherited From AssignableConcept

Interface Function Overview

Interface Functions Inherited From Graph

Interface Functions Inherited From AssignableConcept

Interface Functions Inherited From ContainerConcept

Interface Metafunction Overview

Interface Metafunctions Inherited From Graph

Interface Metafunctions Inherited From ContainerConcept

Detailed Description

An Automaton has directed edges, labeled with input symbols, and a distinct start state, called root. The input symbols require the use of a third parameter: The alphabet of the input symbols.

Interface Functions Detail

void assignRoot(a, v);

Assign a new root vertex to the automaton.

Parameters

a The Automaton to assign the root for.
v A vertex descriptor.

Data Races

Thread safety unknown!

bool canParseString(a[, v], str);

Test whether an Automaton can parse a string completely.

Parameters

a The Automaton to use for parsing.
v Optionally, the descriptor of the vertex to start at. Defaults to the root.
str The string to parse.

Returns

bool true if the Automaton parses str , starting at v, completely and false otherwise.

Data Races

Thread safety unknown!

void createOracle(g, text);

Creates a factor oracle into an Automaton object.

Parameters

g The oracle to create.
text A String to create the oracle with.

Data Races

Thread safety unknown!

See Also

void createOracleOnReverse(g, text);

Creates a factor oracle on the reversed string.

Parameters

g The oracle to create.
text A String to create the oracle with.

Data Races

Thread safety unknown!

See Also

void createRoot(g);

Creates the root for the automaton.

Parameters

g The Automaton to create the root for.

Data Races

Thread safety unknown!

void createSuffixTrie(g, terminalStateMap, text);

Creates a trie of all suffixes of a text.

Parameters

g The Automaton to create the suffix trie in.
terminalStateMap An external property map; of type String<String<unsigned> >.
text A TextConcept object.

Data Races

Thread safety unknown!

createTrie(g, terminalStateMap, keywords);

Creates a trie in an Automaton.

Parameters

g Automaton object to create the trie in.
terminalStateMap An external property map. The type must be String<String<unsigned>> since a number of keywords can end in each vertex of the trie. This is the case in the Aho-Corasick algorithm if one pattern is a suffix of another pattern. Hence, we must associate with every vertex a set of indices that correspond to keywords.
keywords A set of strings.

Data Races

Thread safety unknown!

See Also

createTrie(g, terminalStateMap, keywords);

Creates a trie for all reversed keywords.

Parameters

g Automaton object to create the trie in.
terminalStateMap An external property map. The type must be String<String<unsigned>> since a number of keywords can end in each vertex of the trie. This is the case in the Aho-Corasick algorithm if one pattern is a suffix of another pattern. Hence, we must associate with every vertex a set of indices that correspond to keywords.
keywords A set of strings.

Data Races

Thread safety unknown!

See Also

TVertexDescriptor getRoot(a);

Gets the root of the automaton.

Parameters

a The Automaton to query for its root.

Returns

TVertexDescriptor The root's vertex descriptor.

Data Races

Thread safety unknown!

TVertexDescriptor getSuccessor(a, v, c);

Gets the successor for a given vertex and an edge label.

Parameters

a The Automaton to query for its successor.
v The descriptor fo the vertex to get the successor for.
c The character label.

Returns

TVertexDescriptor A vertex descriptor or nil if successor is not defined.

Data Races

Thread safety unknown!

See Also

bool isRoot(a, v);

Tests whether a given vertex is the root or not.

Parameters

a The Automaton to query.
v The descriptor of the vertex to query.

Returns

bool true if v is the root and false otherwise.

Data Races

Thread safety unknown!

TVertexDescriptor parseString(a, v, beginIt, endIt); TVertexDescriptor parseString(a, v, str);

Parses a string one character at a time and moves accordingly in the automaton.

Parameters

a An Automaton.
v The descriptor of the vertex to start at.
str The ContainerConcept to parse.
beginIt Begin iterator to sequence to parse. Set to the first character that could not be parsed or to the value of endIt if all of the string was parsed.
endIt End iterator to sequence to parse.

Returns

TVertexDescriptor The vertex descriptor of the state that was reached after parsing.

The parsing stops before getSuccessor reaches the nil state or if the complete sequence is read.

Data Races

Thread safety unknown!

TVertexDescriptor root(a);

Gets reference to the root of the automaton.

Parameters

a The Automaton to query for its root.

Returns

TVertexDescriptor Reference to the root's vertex descriptor.

Data Races

Thread safety unknown!