Implementation of Edmonds-Karp maxflow/min-cut algorithm. More...
Inheritance diagram for drwnEdmondsKarpMaxFlow:
Public Member Functions | |
| drwnEdmondsKarpMaxFlow (unsigned maxNodes=0) | |
| virtual double | solve () |
| solve the max-flow problem and return the flow | |
 Public Member Functions inherited from drwnMaxFlow | |
| drwnMaxFlow (unsigned maxNodes=0) | |
| construct a maxflow/mincut problem with estimated maxNodes | |
| virtual | ~drwnMaxFlow () |
| destructor | |
| size_t | numNodes () const |
| get number of nodes in the graph | |
| virtual void | reset () |
| reset all edge capacities to zero (but don't free the graph) | |
| virtual void | clear () |
| clear the graph and internal datastructures | |
| int | addNodes (unsigned n=1) |
| add nodes to the graph (returns the id of the first node added) | |
| void | addConstant (double c) |
| add constant flow to graph | |
| void | addSourceEdge (int u, double cap) |
| add edge from s to nodeId | |
| void | addTargetEdge (int u, double cap) |
| add edge from nodeId to t | |
| void | addEdge (int u, int v, double cap_uv, double cap_vu=0.0) |
| add edge from u to v and edge from v to u (requires cap_uv + cap_vu >= 0) | |
| bool | inSetS (int u) const |
return true if u is in the s-set after calling solve. (note that sometimes a node can be in either S or T) | |
| bool | inSetT (int u) const |
return true if u is in the t-set after calling solve (note that sometimes a node can be in either S or T) | |
| double | operator() (int u, int v) const |
| returns the residual capacity for an edge (use -1 for terminal so that (-1,-1) represents the current flow) | |
Protected Member Functions | |
| void | findCuts () |
| Protected Member Functions inherited from drwnMaxFlow | |
| void | preAugmentPaths () |
| pre-augment s-u-t and s-u-v-t paths | |
Additional Inherited Members | |
| Protected Types inherited from drwnMaxFlow | |
| typedef map< int, pair< unsigned, unsigned > > | _drwnCapacitatedEdge |
| references target node j and edge weights (i,j) and (j,i) | |
| Protected Attributes inherited from drwnMaxFlow | |
| vector< double > | _sourceEdges |
| edges leaving the source | |
| vector< double > | _targetEdges |
| edges entering the target | |
| vector< double > | _edgeWeights |
| internal edge weights | |
| vector< _drwnCapacitatedEdge > | _nodes |
| nodes and their outgoing internal edges | |
| double | _flowValue |
| current flow value (includes constant) | |
| vector< unsigned char > | _cut |
| identifies which side of the cut a node falls | |
| Static Protected Attributes inherited from drwnMaxFlow | |
| static const unsigned char | FREE = 0x00 |
| tree states | |
| static const unsigned char | SOURCE = 0x01 |
| static const unsigned char | TARGET = 0x02 |
Detailed Description
Implementation of Edmonds-Karp maxflow/min-cut algorithm.
The documentation for this class was generated from the following files:
- drwnMaxFlow.h
- drwnMaxFlow.cpp
