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

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

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

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

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

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

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

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

See Also

void createRoot(g);

Creates the root for the automaton.

Parameters

g The Automaton to create the root for.

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

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

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

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

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

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

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

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

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

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

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

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

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

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

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.

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

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.