Generic graph.
Include Headers
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.
Alignment GraphAn alignment graph.
AutomatonAn 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.
Directed GraphA directed graph that stores the edges in an adjacency list.
HmmAn Hmm is a directed graph with edges labeled with transition probabilities and emission profiles for each vertex. Vertices correspond to states in an HMM.
OracleA factor oracle.
TreeA 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.
TrieA keyword trie.
Undirected GraphAn undirected graph that stores the edges in an adjacency list.
AlphabetAccess to the Alphabet type.
CargoType of additional data stored in an object.
EdgeDescriptorType of an object that represents an edge descriptor.
EdgeIdHandlerType of an object that represents an Id Manager.
EdgeTypeEdge type of a graph object.
HostType of the object a given object depends on.
IteratorType of iterator objects that are used to traverse the container.
SpecThe spec of a class.
VertexDescriptorType of an object that represents a vertex descriptor.
addEdgeAdds a new edge to the graph, either with or without cargo.
addEdgesShortcut to add multiple edges at once. Creates vertices implicitly.
addVertexAdds a new vertex to the graph.
assignEdgeMapInitializes a vertex map with values of an array.
assignVertexMapInitializes a vertex map with values of an array.
clearResets an object.
clearEdgesRemoves all edges in a graph.
clearVerticesRemoves all vertices in a graph.
createIntervalTreeCreate an interval tree.
degreeNumber of incident edges for a given vertex.
emptyTest a container for being empty.
findEdgeFinds an edge.
getAdjacencyMatrixReturns an adjacency matrix representation of the graph.
inDegreeNumber of incoming edges for a given vertex.
numEdgesNumber of edges in a graph.
numVerticesNumber of vertices in a graph.
outDegreeNumber of outgoing edges for a given vertex.
removeEdgeRemoves an edge from the graph. For automatons a label is required.
removeInEdgesRemoves the incoming edges of a given vertex.
removeOutEdgesRemoves the outgoing edges of a given vertex.
removeVertexRemoves a vertex.
resizeEdgeMapInitializes an edge map
resizeVertexMapInitializes a vertex map.
sourceVertexReturns the source vertex of an edge.
targetVertexReturns the target vertex of an edge.
transposeTransposes a graph, either in-place or from source to dest.
writeSaves records to a file.
This is an example for Dijkstra's algorithm on a directed graph with an external property map. The property map adds weights to the edges. The example only outputs distances, not the details of the paths.
1// A tutorial about the dijkstra's algorithm, once using an external map and once using an internal map.
2#include <iostream>
3#include <seqan/graph_algorithms.h>
5using namespace seqan;
7int main() {
8    typedef Graph<Directed<> > TGraph;
10    // Graph creation: 10 directed edges (0,1), (0,3), ...
11    TGraph g;
12    Size<TGraph>::Type numEdges = 10;
13    VertexDescriptor<TGraph>::Type edges[] = {0,1, 0,3, 1,2, 1,3, 2,4, 3,1, 3,2, 3,4, 4,0, 4,2};
14    addEdges(g, edges, numEdges);
16    // One external property map: Weight map    
17    unsigned int weights[] =    {10,  5,   1,   2,   4,   3,   9,   2,   7,   6};
18    String<unsigned int> weightMap;
19    assignEdgeMap(g, weightMap, weights);
21    // Out-parameters: Predecessor and distance map
22    String<unsigned int> predMap;
23    String<unsigned int> distMap;
25    // Dijkstra from vertex 0 (single source shortest paths)
26    dijkstra(g, 0, weightMap, predMap, distMap);
28    // Output distances of shortest paths
29    Iterator<TGraph, VertexIterator>::Type it(g);
30    while(!atEnd(it)) {
31        std::cout << "Distance from 0 to " << getValue(it) << ": ";
32        std::cout << getProperty(distMap, getValue(it)) << std::endl;
33        goNext(it);
34    }
35    return 0;
The output of the distances is as follows:
Distance from 0 to 0: 0
Distance from 0 to 1: 8
Distance from 0 to 2: 9
Distance from 0 to 3: 5
Distance from 0 to 4: 7
SeqAn - Sequence Analysis Library -

Page built @2013/07/11 09:12:34