| Example Program Maximum Flow Ford-Fulkerson maximum flow code example 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;
|
| 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;
|
| 18 | String<unsigned int> capMap;
| | 19 | unsigned int capacity[] = {16, 13, 12, 10, 20, 9, 4, 14, 7, 4};
| | 20 | assignEdgeMap(g,capMap, capacity);
|
| 21 | String<unsigned int> flow;
|
| 22 | unsigned int valF = fordFulkersonAlgorithm(g, 0, 3, capMap, flow);
|
| 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: "
| | 28 | << getProperty(capMap, getValue(itEdge)) << std::endl;
| | 29 | }
| | 30 | return 0;
| | 31 | }
|
|