Example Program
Maximum Flow
Ford-Fulkerson maximum flow code example
File "graph_algo_flow_fordfulkerson.cpp"
A tutorial about the maximum flow algorithm of Ford-Fulkerson.

1 | #include <iostream>
2 | #include <seqan/graph_algorithms.h>
3 |
4 | using namespace seqan;
5 |
6 |
7 | int main() {
8 | typedef Graph<Directed<> > TGraph;
9 | typedef VertexDescriptor<TGraph>::Type TVertexDescriptor;
10 | typedef EdgeDescriptor<TGraph>::Type TEdgeDescriptor;
11 | typedef Iterator<TGraph, EdgeIterator>::Type TEdgeIterator;
12 | typedef Size<TGraph>::Type TSize;

Graph creation: 10 directed edges (0,1), (0,4), ...

13 | TSize numEdges = 10;
14 | TVertexDescriptor edges[] = {0,1, 0,4, 1,2, 1,4, 2,3, 2,4, 4,1, 4,5, 5,2, 5,3};
15 | TGraph g;
16 | addEdges(g,edges, numEdges);
17 | ::std::cout << g << ::std::endl;

One external property map: Edge capacities

18 | String<unsigned int> capMap;
19 | unsigned int capacity[] = {16, 13, 12, 10, 20, 9, 4, 14, 7, 4};
20 | resizeEdgeMap(g,capMap, capacity);

Out-parameters: Edge flows

21 | String<unsigned int> flow;

Ford-Fulkerson flow from source = 0 to sink = 3. valF is the value of the flow.

22 | unsigned int valF = fordFulkersonAlgorithm(g, 0, 3, capMap, flow);

Console Output

23 | ::std::cout << "Ford-Fulkerson (Value of the flow = " << valF << ")" << ::std::endl;
24 | TEdgeIterator itEdge(g);
25 | for(;!atEnd(itEdge);goNext(itEdge)) {
26 | ::std::cout << "(" << sourceVertex(itEdge) << "," << targetVertex(itEdge) << "): ";
27 | ::std::cout << "Flow: " << getProperty(flow, getValue(itEdge)) << ", Capacity: " << getProperty(capMap, getValue(itEdge)) << ::std::endl;
28 | }
29 | return 0;
30 | }

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

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