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  2 #include  3 4 using namespace seqan; 5 6 int main() { 7 typedef Graph > TGraph; 8 typedef VertexDescriptor::Type TVertexDescriptor; 9 typedef EdgeDescriptor::Type TEdgeDescriptor; 10 typedef Size::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 weightMap; 17 resizeEdgeMap(g,weightMap, weights);
Out-parameters: Predecessor and distance map
 18 String predMap; 19 String 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::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 TEdges; 32 typedef Graph TCargoGraph;
Graph creation
 33 TCargoGraph cargo_g; 34 addEdges(cargo_g, edges, numEdges);
One internal property map: Weight map
 35 InternalMap 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::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 }
See
SeqAn - Sequence Analysis Library - www.seqan.de

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