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  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,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 weightMap; 18 resizeEdgeMap(g,weightMap, weights);
Out-parameters: Predecessor and distance map
 19 String predMap; 20 String 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::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 }
See
SeqAn - Sequence Analysis Library - www.seqan.de

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