Example Program
Bellman-Ford Algorithm
Computing single source shortest paths using Bellman-Ford algorithm.
File "graph_algo_path_bellmanford.cpp"
A tutorial about a shortest path search using Bellman-Ford.

1 | #include <iostream>
2 | #include <seqan/graph_algorithms.h>
3 |
4 | using namespace seqan;
5 |
6 | int 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 | resizeEdgeMap(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 | }

See
Graph, bellmanFordAlgorithm
SeqAn - Sequence Analysis Library - www.seqan.de

Page built @2012/03/14 16:34:45