Class
Graph
Generic graph.
Parameters
The specializing type determines the kind of graph, e.g., directed, undirected, tree, or automaton. Default: Directed<> Remarks: The default Graph<> corresponds to a directed graph. |
Specializations
An alignment graph. | |
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. | |
A directed graph that stores the edges in an adjacency list. | |
A factor oracle. | |
A Tree has a distinct root and directed edges. The source vertex of each edge is the parent vertex, the target vertex of each edge is the child. Trees provide fast access to child vertices and the parent. | |
A keyword trie. | |
An undirected graph that stores the edges in an adjacency list. |
Metafunctions
Type of additional data stored in an object. | |
Type of an object that represents an edge descriptor. | |
Type of an object that represents an Id Manager. | |
Edge type of a graph object. | |
Type of the object a given object depends on. | |
Type of iterator objects that are used to traverse the container. | |
Type of an object that is suitable to hold size information. | |
The spec of a class. | |
Type of an object that represents a vertex descriptor. |
Functions
Adds a new edge to the graph, either with or without cargo. | |
Shortcut to add multiple edges at once. Creates vertices implicitly. | |
Adds a new vertex to the graph. | |
Finds shortest paths between all pairs of vertices in a graph. | |
Computes shortest paths from a single source in a graph. | |
Implements a breadth-first search on a graph. | |
Resets an object. | |
Removes all edges in a graph. | |
Removes all vertices in a graph. | |
Number of incident edges for a given vertex. | |
Implements a depth-first search on a graph. | |
Computes shortest paths from a single source in a graph. | |
Test a container for being empty. | |
Finds an edge. | |
Finds shortest paths between all pairs of vertices in a graph. | |
Returns an adjacency matrix representation of the graph. | |
Utility function for various graph algorithms. | |
Number of incoming edges for a given vertex. | |
Computes a minimum spanning tree on a graph. | |
Number of edges in a graph. | |
Number of vertices in a graph. | |
Number of outgoing edges for a given vertex. | |
Computes a minimum spanning tree on a graph. | |
Removes an edge from the graph. For automatons a label is required. | |
Removes the incoming edges of a given vertex. | |
Removes the outgoing edges of a given vertex. | |
Removes a vertex. | |
Initializes an edge map | |
Initializes a vertex map. | |
Returns the source vertex of an edge. | |
Returns the target vertex of an edge. | |
Determines whether there is a path between any two given vertices or not. | |
Transposes a graph, either in-place or from source to dest. |
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