GClasses
GClasses::GGraphCut Class Reference

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.

#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
 
GHeapm_pHeap
 
struct GGraphCutNode * m_pNodes
 
struct GGraphCutNode * m_pSink
 
struct GGraphCutNode * m_pSource
 
std::deque< size_t > m_q
 

Friends

class GGraphEdgeIterator
 

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