|
Darwin
1.10(beta)
|
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
|
Darwin
1.10(beta)
|
Interface for maxflow/min-cut algorithms (for minimizing submodular quadratic pseudo-Boolean functions) More...
Public Member Functions | |
| 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) | |
| virtual double | solve ()=0 |
| solve the max-flow problem and return the flow | |
| 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 Types | |
|
typedef map< int, pair < unsigned, unsigned > > | _drwnCapacitatedEdge |
| references target node j and edge weights (i,j) and (j,i) | |
Protected Member Functions | |
| void | preAugmentPaths () |
| pre-augment s-u-t and s-u-v-t paths | |
Protected Attributes | |
| 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 unsigned char | FREE = 0x00 |
| tree states | |
| static const unsigned char | SOURCE = 0x01 |
| static const unsigned char | TARGET = 0x02 |
Interface for maxflow/min-cut algorithms (for minimizing submodular quadratic pseudo-Boolean functions)
Residual capacities are updated in-place. See Max-flow/Min-cut. Negative edge weights are allowed between terminals (source or target) and added to the constant. Supports dynamic graph-cuts (see Kohli and Torr, PAMI 2007).
1.8.6