Example Program
Bellman-Ford Algorithm
Computing single source shortest paths using Bellman-Ford algorithm.
A tutorial about a shortest path search using Bellman-Ford.
 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); 15 std::cout << g << std::endl;
One external property map: Weight map
 16 unsigned int weights[] =    {10,  5,   1,   2,   4,   3,   9,   2,   7,   6}; 17 String weightMap; 18 assignEdgeMap(g,weightMap, weights);
Out-parameters: Predecessor and distance map
 19 String predMap; 20 String distMap;
Bellman-Ford from vertex 0 Note: Bellman-Ford also detects negative cycles
 21 bool noNegativeCycle = bellmanFordAlgorithm(g,0,weightMap,predMap,distMap);
Console Output
 22 std::cout << "Single-Source Shortest Paths: " << std::endl; 23 std::cout << "Graph without negative cycles? " << noNegativeCycle << std::endl; 24 typedef Iterator::Type TVertexIterator; 25 TVertexIterator it(g); 26 while(!atEnd(it)) { 27 std::cout << "Path from 0 to " << getValue(it) << ": "; 28 _printPath(g,predMap,(TVertexDescriptor) 0, getValue(it)); 29 std::cout << " (Distance: " << getProperty(distMap, getValue(it)) << ")" << std::endl; 30 goNext(it); 31 } 32 return 0; 33 }
SeqAn - Sequence Analysis Library - www.seqan.de

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