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 <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);
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<unsigned int> weightMap;
18    assignEdgeMap(g,weightMap, weights);
Out-parameters: Predecessor and distance map
19    String<unsigned int> predMap;
20    String<unsigned int> 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<TGraph, VertexIterator>::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:16