/*!
* @class Automaton
*
* @extends Graph
*
* @headerfile <seqan/graph_types.h>
*
* @brief Representation of a automaton graph.
*
* @signature template <[typename TAlphabet[, typename TCargo[, typename
* TSpec]]]> class Graph<Automaton<TAlphabet, TCargo, TSpec>;
*
* @tparam TAlphabet The alphabet type used for transition labels. Default:
* <tt>char</tt>.
* @tparam TCargo The cargo type that can be attached to the edges. Default:
* <tt>void</tt>.
* @tparam TSpec Specializing type. Default: <tt>Default</tt>. Use
* <tt>WithoutEdgeId</tt> here to omit edge ids. NB: if edges to
* not store ids then external property maps do not work.
*
* 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.
*
* <img src="automatonGraph.png" title="An automaton where 0 is the start state"
* />
*
* @fn Automaton#createRoot
*
* @brief Creates the root for the automaton.
*
* @signature void createRoot(g);
*
* @param[in,out] g The Automaton to create the root for.
*
* @fn Automaton#assignRoot
*
* @brief Assign a new root vertex to the automaton.
*
* @signature void assignRoot(a, v);
*
* @param[in,out] a The Automaton to assign the root for.
* @param[in] v A vertex descriptor.
*
* @fn Automaton#root
*
* @brief Gets reference to the root of the automaton.
*
* @signature TVertexDescriptor root(a);
*
* @param[in] a The Automaton to query for its root.
*
* @return TVertexDescriptor Reference to the root's vertex descriptor.
*
* @fn Automaton#getRoot
*
* @brief Gets the root of the automaton.
*
* @signature TVertexDescriptor getRoot(a);
*
* @param[in] a The Automaton to query for its root.
*
* @return TVertexDescriptor The root's vertex descriptor.
*
* @fn Automaton#isRoot
*
* @brief Tests whether a given vertex is the root or not.
*
* @signature bool isRoot(a, v);
*
* @param[in] a The Automaton to query.
* @param[in] v The descriptor of the vertex to query.
*
* @return bool true if v is the root and false otherwise.
*
* @fn Automaton#getSuccessor
*
* @brief Gets the successor for a given vertex and an edge label.
*
* @signature TVertexDescriptor getSuccessor(a, v, c);
*
* @param[in] a The Automaton to query for its successor.
* @param[in] v The descriptor fo the vertex to get the successor for.
* @param[in] c The character label.
*
* @return TVertexDescriptor A vertex descriptor or nil if successor is not
* defined.
*
* @see Automaton#parseString
* @see Graph#getNil
*
* @fn Automaton#parseString
*
* @brief Parses a string one character at a time and moves accordingly in the
* automaton.
*
* @signature TVertexDescriptor parseString(a, v, beginIt, endIt);
* @signature TVertexDescriptor parseString(a, v, str);
*
* @param[in] a An Automaton.
* @param[in] v The descriptor of the vertex to start at.
* @param[in] str The @link SequenceConcept @endlink to parse.
* @param[in,out] 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.
* @param[in] endIt End iterator to sequence to parse.
*
* @return TVertexDescriptor The vertex descriptor of the state that was reached
* after parsing.
*
* The parsing stops before @link Automaton#getSuccessor @endlink reaches the
* nil state or if the complete sequence is read.
*
* @fn Automaton#canParseString
*
* @brief Test whether an Automaton can parse a string completely.
*
* @signature bool canParseString(a[, v], str);
*
* @param[in] a The Automaton to use for parsing.
* @param[in] v Optionally, the descriptor of the vertex to start at. Defaults
* to the root.
* @param[in] str The string to parse.
*
* @return bool <tt>true</tt> if the Automaton parses <tt>str</tt> , starting at
* <tt>v</tt>, completely and <tt>false</tt> otherwise.
*
* @fn Automaton#createTrie
*
* @brief Creates a trie in an Automaton.
*
* @signature createTrie(g, terminalStateMap, keywords);
*
* @param[in,out] g Automaton object to create the trie in.
* @param[in] terminalStateMap An external property map. The type must be
* <tt>String<String<unsigned>></tt>
* 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.
* @param[in] keywords A set of strings.
*
* @see Automaton#createTrieOnReverse
*
* @fn Automaton#createTrieOnReverse
*
* @brief Creates a trie for all reversed keywords.
*
* @signature createTrie(g, terminalStateMap, keywords);
*
* @param[in,out] g Automaton object to create the trie in.
* @param[in] terminalStateMap An external property map. The type must be
* <tt>String<String<unsigned>></tt>
* 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.
* @param[in] keywords A set of strings.
*
* @see Automaton#createTrie
*
* @fn Automaton#createSuffixTrie
*
* @brief Creates a trie of all suffixes of a text.
*
* @signature void createSuffixTrie(g, terminalStateMap, text);
*
* @param[out] g The Automaton to create the suffix trie in.
* @param[out] terminalStateMap An external property map; of type
* <tt>String<String<unsigned> ></tt>.
* @param[in] text A @link TextConcept @endlink object.
*
* @fn Automaton#createOracle
*
* @brief Creates a factor oracle into an Automaton object.
*
* @signature void createOracle(g, text);
*
* @param[out] g The oracle to create.
* @param[in] text A @link String @endlink to create the oracle with.
*
* @see Automaton#createOracleOnReverse
*
* @fn Automaton#createOracleOnReverse
*
* @brief Creates a factor oracle on the reversed string.
*
* @signature void createOracleOnReverse(g, text);
*
* @param[out] g The oracle to create.
* @param[in] text A @link String @endlink to create the oracle with.
*
* @see Automaton#createOracle
*/