GClasses::GGraphCut Class Reference

This implements an optimized max-flow/min-cut algorithm described in "An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision" by Boykov, Y. and Kolmogorov, V. This implementation assumes that edges are undirected. More...

#include <GGraph.h>

Public Member Functions
	GGraphCut (size_t nNodes)
	~GGraphCut ()
void	addEdge (size_t nNode1, size_t nNode2, float fCapacity)
	Adds an edge to the graph. You must add all the edges before calling "Cut". The edge will be stored internally as a directed edge (from nNode1 to nNode2), but the Cut method will treat them as undirected edges. More...
void	cut (size_t nSourceNode, size_t nSinkNode)
	This computes the cut. nSourceNode is the node that represents the source, and nSinkNode is the node that represents the sink. More...
bool	doesBorderTheCut (size_t nNode)
	Returns true if the specified node borders the cut. More...
void	getEdgesFromRegionList (GRegionAjacencyGraph *pRegionList)
	Creates an edge from the node that represents each region to the node for each of its neighbor regions. More...
bool	isSource (size_t nNode)
	Determine whether the specified node is on the source-side or the sink-side of the cut. (You must call "Cut" before calling this method.) More...
size_t	nodeCount ()
	Returns the number of nodes in the graph. More...

Static Public Member Functions
static void	test ()
	Performs unit tests for this class. Throws an exception if there is a failure. More...

Protected Member Functions
void	augmentPath (struct GGraphCutEdge *pEdge)
void	findAHome (size_t nNode)
void	growNode (size_t nNode)
void	recycleTree (size_t nChild, size_t nParent)

Protected Attributes
size_t	m_nNodes
GHeap *	m_pHeap
struct GGraphCutNode *	m_pNodes
struct GGraphCutNode *	m_pSink
struct GGraphCutNode *	m_pSource
std::deque< size_t >	m_q

Friends
class	GGraphEdgeIterator

Detailed Description

This implements an optimized max-flow/min-cut algorithm described in "An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision" by Boykov, Y. and Kolmogorov, V. This implementation assumes that edges are undirected.

Constructor & Destructor Documentation

GClasses::GGraphCut::GGraphCut

(

size_t

nNodes

)

GClasses::GGraphCut::~GGraphCut

(

)

Member Function Documentation

void GClasses::GGraphCut::addEdge	(	size_t	nNode1,
		size_t	nNode2,
		float	fCapacity
	)

Adds an edge to the graph. You must add all the edges before calling "Cut". The edge will be stored internally as a directed edge (from nNode1 to nNode2), but the Cut method will treat them as undirected edges.

void GClasses::GGraphCut::augmentPath ( struct GGraphCutEdge *  pEdge )

protected

void GClasses::GGraphCut::cut	(	size_t	nSourceNode,
		size_t	nSinkNode
	)

This computes the cut. nSourceNode is the node that represents the source, and nSinkNode is the node that represents the sink.

bool GClasses::GGraphCut::doesBorderTheCut

(

size_t

nNode

)

Returns true if the specified node borders the cut.

void GClasses::GGraphCut::findAHome ( size_t  nNode )

protected

void GClasses::GGraphCut::getEdgesFromRegionList

(

GRegionAjacencyGraph *

pRegionList

)

Creates an edge from the node that represents each region to the node for each of its neighbor regions.

void GClasses::GGraphCut::growNode ( size_t  nNode )

protected

bool GClasses::GGraphCut::isSource

(

size_t

nNode

)

Determine whether the specified node is on the source-side or the sink-side of the cut. (You must call "Cut" before calling this method.)

size_t GClasses::GGraphCut::nodeCount ( )

inline

Returns the number of nodes in the graph.

void GClasses::GGraphCut::recycleTree ( size_t  nChild, size_t  nParent  )

protected

static void GClasses::GGraphCut::test ( )

static

Performs unit tests for this class. Throws an exception if there is a failure.

Friends And Related Function Documentation

friend class GGraphEdgeIterator

friend

Member Data Documentation

size_t GClasses::GGraphCut::m_nNodes

protected

GHeap* GClasses::GGraphCut::m_pHeap

protected

struct GGraphCutNode* GClasses::GGraphCut::m_pNodes

protected

struct GGraphCutNode* GClasses::GGraphCut::m_pSink

protected

struct GGraphCutNode* GClasses::GGraphCut::m_pSource

protected

std::deque<size_t> GClasses::GGraphCut::m_q

protected