GClasses
|
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 |
GHeap * | m_pHeap |
struct GGraphCutNode * | m_pNodes |
struct GGraphCutNode * | m_pSink |
struct GGraphCutNode * | m_pSource |
std::deque< size_t > | m_q |
Friends | |
class | GGraphEdgeIterator |
GClasses::GGraphCut::GGraphCut | ( | size_t | nNodes | ) |
GClasses::GGraphCut::~GGraphCut | ( | ) |
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.
|
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.
|
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.
|
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.)
|
inline |
Returns the number of nodes in the graph.
|
protected |
|
static |
Performs unit tests for this class. Throws an exception if there is a failure.
|
friend |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |