Example Program
Dijkstras Algorithm
Computing single source shortest paths using Dijkstra algorithm.
A tutorial about the dijkstra's algorithm, once using an external map and once using an internal map.
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,1), (0,3), ...
11    TSize numEdges = 10;
12    TVertexDescriptor edges[] = {0,1, 0,3, 1,2, 1,3, 2,4, 3,1, 3,2, 3,4, 4,0, 4,2};
13    TGraph g;
14    addEdges(g, edges, numEdges);
One external property map: Weight map
15    unsigned int weights[] =    {10,  5,   1,   2,   4,   3,   9,   2,   7,   6};
16    String<unsigned int> weightMap;
17    resizeEdgeMap(g,weightMap, weights);
Out-parameters: Predecessor and distance map
18    String<unsigned int> predMap;
19    String<unsigned int> distMap;
Dijkstra from vertex 0
20    dijkstra(g,0,weightMap,predMap,distMap);
Console Output
21    ::std::cout << "Single-Source Shortest Paths: " << ::std::endl;
22    typedef Iterator<TGraph, VertexIterator>::Type TVertexIterator;
23    TVertexIterator it(g);
24    while(!atEnd(it)) {
25        ::std::cout << "Path from 0 to " << getValue(it) << ": ";
26        _printPath(g,predMap,(TVertexDescriptor) 0, getValue(it));
27        ::std::cout << " (Distance: " << getProperty(distMap, getValue(it)) << ")" << ::std::endl;
28        goNext(it);
29    }
We can achieve the same thing using an internal map that is edge cargos.
30    typedef unsigned int TEdgeCargo;
31    typedef Directed<TEdgeCargo> TEdges;
32    typedef Graph<TEdges> TCargoGraph;
Graph creation
33    TCargoGraph cargo_g;
34    addEdges(cargo_g, edges, numEdges);
One internal property map: Weight map
35    InternalMap<TEdgeCargo> intMap;
36    resizeEdgeMap(cargo_g,intMap, weights);
Out parameters of Dijkstra: Predecessor map and distance map
37    clear(predMap);
38    clear(distMap);
Dijkstra from vertex 0 using an internal map
39    dijkstra(cargo_g,0,intMap,predMap,distMap);
Console Output
40    ::std::cout << "Single-Source Shortest Paths: " << ::std::endl;
41    typedef Iterator<TCargoGraph, VertexIterator>::Type TCargoVertexIterator;
42    TCargoVertexIterator itC(cargo_g);
43    while(!atEnd(itC)) {
44        ::std::cout << "Path from 0 to " << getValue(itC) << ": ";
45        _printPath(cargo_g,predMap,(TVertexDescriptor) 0, getValue(itC));
46        ::std::cout << " (Distance: " << getProperty(distMap, getValue(itC)) << ")" << ::std::endl;
47        goNext(itC);
48    }
49    return 0;
50}
SeqAn - Sequence Analysis Library - www.seqan.de
 

Page built @2011/02/08 21:37:01