| Class Specialization Automaton 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.
An automaton, where 0 is the start state.
Graph
Automaton
Word Graph
Graph<Automaton<TAlphabet, TCargo, TSpec> > Parameters
TAlphabet | The alphabet type that is used for the transition labels. Metafunctions: Alphabet Default: char Remarks: Use Alphabet to get the type of the labels in an automaton.
TCargo | The cargo type that can be attached to the edges. Metafunctions: Cargo Default: void Remarks: Use Cargo to get the cargo type of an undirected graph.
TSpec | The specializing type for the graph. Metafunctions: Spec Default: Default, see Default. Remarks: Use WithoutEdgeId here to omit edge ids. Note: If edges do not store ids external property maps do not work.
Specialization of Graph Specializations
Word Graph | A special automaton that stores words instead of single characters along its edges.
Metafunctions
Cargo | Type of additional data stored in an object. (Graph)
EdgeDescriptor | Type of an object that represents an edge descriptor. (Graph)
EdgeIdHandler | Type of an object that represents an Id Manager. (Graph)
EdgeType | Edge type of a graph object. (Graph)
Host | Type of the object a given object depends on. (Graph)
Iterator | Type of iterator objects that are used to traverse the container. (Graph)
Size | Type of an object that is suitable to hold size information. (Graph)
Spec | The spec of a class. (Graph)
VertexDescriptor | Type of an object that represents a vertex descriptor. (Graph)
Functions
addEdge | Adds a new edge to the graph, either with or without cargo. (Graph)
addEdges | Shortcut to add multiple edges at once. Creates vertices implicitly. (Graph)
addVertex | Adds a new vertex to the graph. (Graph)
all_pairs_shortest_path | Finds shortest paths between all pairs of vertices in a graph. (Graph)
assignRoot | Assigns a new root vertex to the automaton.
bellman_ford_algorithm | Computes shortest paths from a single source in a graph. (Graph)
breadth_first_search | Implements a breadth-first search on a graph. (Graph)
clear | Resets an object. (Graph)
clearEdges | Removes all edges in a graph. (Graph)
clearVertices | Removes all vertices in a graph. (Graph)
createRoot | Creates the root in a tree or an automaton.
degree | Number of incident edges for a given vertex. (Graph)
depth_first_search | Implements a depth-first search on a graph. (Graph)
dijkstra | Computes shortest paths from a single source in a graph. (Graph)
empty | Test a container for being empty. (Graph)
findEdge | Finds an edge. (Graph)
floyd_warshall | Finds shortest paths between all pairs of vertices in a graph. (Graph)
getAdjacencyMatrix | Returns an adjacency matrix representation of the graph. (Graph)
getNilPredecessor | Utility function for various graph algorithms. (Graph)
getRoot | Get method for the root of a tree or an automaton.
getSuccessor | Gets the successor for a given vertex and an edge label. For an automaton a single character is required whereas for a word graph getSuccessor takes a string.
inDegree | Number of incoming edges for a given vertex. (Graph)
isRoot | Tests whether a given vertex is the root or not.
kruskals_algorithm | Computes a minimum spanning tree on a graph. (Graph)
numEdges | Number of edges in a graph. (Graph)
numVertices | Number of vertices in a graph. (Graph)
outDegree | Number of outgoing edges for a given vertex. (Graph)
parseString | Parses a string one character at a time and moves accordingly in the automaton.
prims_algorithm | Computes a minimum spanning tree on a graph. (Graph)
removeEdge | Removes an edge from the graph. For automatons a label is required. (Graph)
removeInEdges | Removes the incoming edges of a given vertex. (Graph)
removeOutEdges | Removes the outgoing edges of a given vertex. (Graph)
removeVertex | Removes a vertex. (Graph)
resizeEdgeMap | Initializes an edge map (Graph)
resizeVertexMap | Initializes a vertex map. (Graph)
root | Gets a reference to the root of the tree.
sourceVertex | Returns the source vertex of an edge. (Graph)
targetVertex | Returns the target vertex of an edge. (Graph)
transitive_closure | Determines whether there is a path between any two given vertices or not. (Graph)
transpose | Transposes a graph, either in-place or from source to dest. (Graph)
Example Programs All Pairs Shortest Path, Bellman-Ford Algorithm, Breadth-First Search, Depth-First Search, Dijkstras Algorithm, Floyd-Warshall Algorithm, Gotohs Algorithm, Heaviest Increasing Subsequence, Heuristic Matching, Hirschbergs Algorithm, Kruskals Algorithm, Longest Common Subsequence, Longest Increasing Subsequence, Maximum Flow, MSA with Neighbor-Joining, MSA with UPGMA, Needleman-Wunsch Algorithm, Prims Algorithm, Shortest Path in DAGs, Smith-Waterman Algorithm, Strongly Connected Components, T-Coffee, Topological Sort, Transitive Closure Include Headers graph.h SeqAn - Sequence Analysis Library - www.seqan.de