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:

Public Member Functions