Example Program
Floyd-Warshall Algorithm
Computing all-pairs shortest paths using Floyd-Warshall algorithm.
A tutorial about the Floyd-Warshall algorithm.
 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: 9 directed edges (0,1), (0,2), ...
 11 TSize numEdges = 9; 12 TVertexDescriptor edges[] = {0,1, 0,2, 0,4, 1,3, 1,4, 2,1, 3,0, 3,2, 4,3}; 13 TGraph g; 14 addEdges(g,edges, numEdges); 15 ::std::cout << g << ::std::endl;
One external property map: Weight map
 16 int weights[] =    {3,   8,   -4,  1,   7,   4,   2,   -5,  6}; 17 String weightMap; 18 resizeEdgeMap(g,weightMap, weights);
Out-parameters: Predecessor and distance matrices
 19 String distMat; 20 String predMat;
Floyd-Warshall
 21 floydWarshallAlgorithm(g,weightMap, distMat, predMat);
Console Output
 22 unsigned int len = (unsigned int) std::sqrt((double) length(distMat)); 23 for (TSize row=0;row < len;++row) { 24 for (TSize col=0;col < len;++col) { 25 ::std::cout << row << "," << col << " (Distance=" << getValue(distMat, row*len + col) << "): "; 26 _printAllPairsShortestPath(g,predMat,row,col); 27 ::std::cout << ::std::endl; 28 } 29 } 30 return 0; 31 }
SeqAn - Sequence Analysis Library - www.seqan.de

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