fn() fordFulkersonAlgorithmComputes a maximum flow in a directed graph.
Computes a maximum flow in a directed graph.
Defined in | <seqan/graph_algorithms.h> |
---|---|
Signature |
TValue fordFulkeronAlgorithm(flow, g, source, sink, capacity);
|
Parameters
flow
|
A property map with the flow of each edge. |
---|---|
g
|
A directed graph. Types: Directed Graph |
source
|
A source vertex. Types: VertexDescriptor |
sink
|
A sink vertex. Types: VertexDescriptor |
capacity
|
A property map of edge capacities. |
Return Values
TValue |
The value of the flow. TValue is the Value tpye of the type of flow. |
---|
Detailed Description
Example
#include <iostream>
#include <seqan/graph_algorithms.h>
using namespace seqan2;
int main()
{
typedef Graph<Directed<> > TGraph;
typedef VertexDescriptor<TGraph>::Type TVertexDescriptor;
typedef Iterator<TGraph, EdgeIterator>::Type TEdgeIterator;
typedef Size<TGraph>::Type TSize;
// Create graph with 10 directed edges (0,1), (0,4), ...
TSize numEdges = 10;
TVertexDescriptor edges[] = {0, 1, 0, 4, 1, 2, 1, 4, 2, 3, 2, 4, 4, 1, 4, 5, 5, 2, 5, 3};
TGraph g;
addEdges(g, edges, numEdges);
// Print graph.
std::cout << g << "\n";
// Create external property map for the edge capacities and assign to the graph.
String<unsigned int> capMap;
unsigned capacity[] = {16, 13, 12, 10, 20, 9, 4, 14, 7, 4};
assignEdgeMap(capMap, g, capacity);
// Run the Ford-Fulkerson algorithm for maximum flow computation from source
// vertex 0 to sink vertex 3. valF is the value of the flow.
String<unsigned int> flow;
unsigned valF = fordFulkersonAlgorithm(flow, g, 0, 3, capMap);
// Print the result to stdout.
std::cout << "Ford-Fulkerson (Value of the flow = " << valF << ")\n";
TEdgeIterator itEdge(g);
for (; !atEnd(itEdge); goNext(itEdge))
std::cout << "(" << sourceVertex(itEdge) << "," << targetVertex(itEdge) << "): "
<< "Flow: " << getProperty(flow, getValue(itEdge)) << ", Capacity: "
<< getProperty(capMap, getValue(itEdge)) << "\n";
return 0;
}
Adjacency list: 0 -> 4,1, 1 -> 4,2, 2 -> 4,3, 3 -> 4 -> 5,1, 5 -> 3,2, Edge list: Source: 0,Target: 4 (Id: 1) Source: 0,Target: 1 (Id: 0) Source: 1,Target: 4 (Id: 3) Source: 1,Target: 2 (Id: 2) Source: 2,Target: 4 (Id: 5) Source: 2,Target: 3 (Id: 4) Source: 4,Target: 5 (Id: 7) Source: 4,Target: 1 (Id: 6) Source: 5,Target: 3 (Id: 9) Source: 5,Target: 2 (Id: 8) Ford-Fulkerson (Value of the flow = 23) (0,4): Flow: 11, Capacity: 13 (0,1): Flow: 12, Capacity: 16 (1,4): Flow: 0, Capacity: 10 (1,2): Flow: 12, Capacity: 12 (2,4): Flow: 0, Capacity: 9 (2,3): Flow: 19, Capacity: 20 (4,5): Flow: 11, Capacity: 14 (4,1): Flow: 0, Capacity: 4 (5,3): Flow: 4, Capacity: 4 (5,2): Flow: 7, Capacity: 7
Data Races
If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.