|
Darwin
1.10(beta)
|
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
|
Darwin
1.10(beta)
|
Implementation of Boykov and Kolmogorov's maxflow algorithm. More...
Public Member Functions | |
| drwnBKMaxFlow (unsigned maxNodes=0) | |
| virtual void | reset () |
| reset all edge capacities to zero (but don't free the graph) | |
| virtual void | clear () |
| clear the graph and internal datastructures | |
| 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 | |
| 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 | initializeTrees () |
| initialize trees from source and target | |
| pair< int, int > | expandTrees () |
| expand trees until a path is found (or no path (-1, -1)) | |
| void | augmentBKPath (const pair< int, int > &path, deque< int > &orphans) |
| augment the path found by expandTrees; return orphaned subtrees | |
| void | adoptOrphans (deque< int > &orphans) |
| adopt orphaned subtrees | |
| bool | isAncestor (int u, int v) const |
| return true if u is an ancestor of v | |
| Protected Member Functions inherited from drwnMaxFlow | |
| void | preAugmentPaths () |
| pre-augment s-u-t and s-u-v-t paths | |
Protected Attributes | |
| vector< int > | _parents |
| _parents flag for terminal state More... | |
| vector< pair< double *, double * > > | _weightptrs |
| drwnIndexQueue | _activeList |
| 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 | |
| static const int | TERMINAL = -1 |
| 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 |
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) | |
Implementation of Boykov and Kolmogorov's maxflow algorithm.
See Boykov and Kolmogorov, "An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision", PAMI 2004 for a description of the algorithm.
|
protected |
_parents flag for terminal state
search tree and active list
1.8.6