GClasses

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>

List of all members.

Public Member Functions

 GGraphCut (size_t nNodes)
 ~GGraphCut ()
size_t nodeCount ()
 Returns the number of nodes in the graph.
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.
void getEdgesFromRegionList (GRegionAjacencyGraph *pRegionList)
 Creates an edge from the node that represents each region to the node for each of its neighbor regions.
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.
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.)
bool doesBorderTheCut (size_t nNode)
 Returns true if the specified node borders the cut.

Static Public Member Functions

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

Protected Member Functions

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

Protected Attributes

std::deque< size_t > m_q
GHeapm_pHeap
size_t m_nNodes
struct GGraphCutNode * m_pNodes
struct GGraphCutNode * m_pSource
struct GGraphCutNode * m_pSink

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]
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]