Example Program
Maximum Flow
Ford-Fulkerson maximum flow code example
A tutorial about the maximum flow algorithm of Ford-Fulkerson.
 1 #include  2 #include  3 4 using namespace seqan; 5 6 7 int main() { 8 typedef Graph > TGraph; 9 typedef VertexDescriptor::Type TVertexDescriptor; 10 typedef EdgeDescriptor::Type TEdgeDescriptor; 11 typedef Iterator::Type TEdgeIterator; 12 typedef Size::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 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 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 }
SeqAn - Sequence Analysis Library - www.seqan.de

Page built @2011/02/08 21:37:01