Darwin  1.10(beta)
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
Public Member Functions | Protected Member Functions | Protected Attributes | Static Protected Attributes | List of all members
drwnBKMaxFlow Class Reference

Implementation of Boykov and Kolmogorov's maxflow algorithm. More...

Inheritance diagram for drwnBKMaxFlow:

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 ()
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 > > 
 references target node j and edge weights (i,j) and (j,i)

Detailed Description

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.

Member Data Documentation

vector<int> drwnBKMaxFlow::_parents

_parents flag for terminal state

search tree and active list

The documentation for this class was generated from the following files: