Example Program
Shortest Path in DAGs
Computing single source shortest paths in a directed acyclic graph.
A tutorial about a shortest path search in a directed acyclic graph.
1#include <iostream>
2#include <seqan/graph_algorithms.h>
3
4using namespace seqan;
5
6int main() {
7    typedef Graph<Directed<> > TGraph;
8    typedef VertexDescriptor<TGraph>::Type TVertexDescriptor;
9    typedef EdgeDescriptor<TGraph>::Type TEdgeDescriptor;
10    typedef Size<TGraph>::Type TSize;
Graph creation: 10 directed edges (0,2), (0,1), ...
11    TSize numEdges = 10;
12    TVertexDescriptor edges[] = {0,2, 0,1, 1,3, 1,2, 2,5, 2,4, 2,3, 3,5, 3,4, 4,5};
13    TGraph g;
14    addEdges(g, edges, numEdges);
15    std::cout << g << std::endl;
One external property map: Weight map
16    int weights[] =             {3,   5,   6,   2,   2,   4,   7,   1,   -1,  -2};
17    String<int> weightMap;
18    assignEdgeMap(g,weightMap, weights);
Out-parameters: Predecessor and distance map
19    String<unsigned int> predMap;
20    String<unsigned int> distMap;
DAG-Shortest path from vertex 1
21    dagShortestPath(g,1,weightMap,predMap,distMap);
Console Output
22    std::cout << "Single-Source Shortest Paths in DAG: " << std::endl;
23    typedef Iterator<TGraph, VertexIterator>::Type TVertexIterator;
24    TVertexIterator it(g);
25    while(!atEnd(it)) {
26        std::cout << "Path from 1 to " << getValue(it) << ": ";
27        _printPath(g,predMap,(TVertexDescriptor) 1, getValue(it));
28        std::cout << " (Distance: " << getProperty(distMap, getValue(it)) << ")" << std::endl;
29        goNext(it);
30    }
31    return 0;
32}
SeqAn - Sequence Analysis Library - www.seqan.de
 

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