Spec
AutomatonRepresentation of a automaton graph.
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. |
Interface Function Overview
-
void assignRoot(a, v);
Assign a new root vertex to the automaton. -
bool canParseString(a[, v], str);
Test whether an Automaton can parse a string completely. -
void createOracle(g, text);
Creates a factor oracle into an Automaton object. -
void createOracleOnReverse(g, text);
Creates a factor oracle on the reversed string. -
void createRoot(g);
Creates the root for the automaton. -
void createSuffixTrie(g, terminalStateMap, text);
Creates a trie of all suffixes of a text. -
createTrie(g, terminalStateMap, keywords);
Creates a trie in an Automaton. -
createTrie(g, terminalStateMap, keywords);
Creates a trie for all reversed keywords. -
TVertexDescriptor getRoot(a);
Gets the root of the automaton. -
TVertexDescriptor getSuccessor(a, v, c);
Gets the successor for a given vertex and an edge label. -
bool isRoot(a, v);
Tests whether a given vertex is the root or not. -
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. -
TVertexDescriptor root(a);
Gets reference to the root of the automaton.
Interface Functions Inherited From Graph
addEdge
addEdges
addVertex
assignEdgeMap
assignVertexMap
clear
clearEdges
clearVertices
degree
empty
findEdge
getAdjacencyMatrix
getNil
getVertexAdjacencyVector
inDegree
numEdges
numVertices
outDegree
removeEdge
removeInEdges
removeOutEdges
removeVertex
resizeEdgeMap
resizeVertexMap
sourceVertex
targetVertex
transpose
writeRecords
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.