ggraph.h

来自「一个由Mike Gashler完成的机器学习方面的includes neural」· C头文件 代码 · 共 93 行

/*
	Copyright (C) 2006, Mike Gashler

	This library is free software; you can redistribute it and/or
	modify it under the terms of the GNU Lesser General Public
	License as published by the Free Software Foundation; either
	version 2.1 of the License, or (at your option) any later version.

	see http://www.gnu.org/copyleft/lesser.html
*/

struct GGraphCutNode;
struct GGraphCutEdge;
class GStringHeap;
class GIntQueue;
class GRegionAjacencyGraph;
class GGraphEdgeIterator;


// 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.
class GGraphCut
{
friend class GGraphEdgeIterator;
protected:
	GIntQueue* m_pQ;
	GStringHeap* m_pHeap;
	int m_nNodes;
	struct GGraphCutNode* m_pNodes;
	struct GGraphCutNode* m_pSource;
	struct GGraphCutNode* m_pSink;

public:
	GGraphCut(int nNodes);
	~GGraphCut();

#ifndef NO_TEST_CODE
	static void Test();
#endif // !NO_TEST_CODE

	// Returns the number of nodes in the graph
	int GetNodeCount() { return m_nNodes; }

	// Adds an edge to the graph. You must add all the edges
	// before calling "Cut".
	void AddEdge(int nNode1, int nNode2, float fCapacity);

	// Creates an edge from the node that represents each region
	// to the node for each of its neighbor regions.
	void GetEdgesFromRegionList(GRegionAjacencyGraph* pRegionList);

	// This computes the cut. nSourceNode is the node that
	// represents the source, and nSinkNode is the node that
	// represents the sink.
	void Cut(int nSourceNode, int nSinkNode);

	// 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 IsSource(int nNode);

	// Returns true if the specified node borders the cut
	bool DoesBorderTheCut(int nNode);

protected:
	void GrowNode(int nNode);
	void AugmentPath(struct GGraphCutEdge* pEdge);
	void RecycleTree(int nChild, int nParent);
	void FindAHome(int nNode);
};


class GGraphEdgeIterator
{
protected:
	GGraphCut* m_pGraph;
	int m_nNode;
	struct GGraphCutEdge* m_pCurrentEdge;

public:
	GGraphEdgeIterator(GGraphCut* pGraph, int nNode);
	~GGraphEdgeIterator();

	// Starts over with a new node
	void Reset(int nNode);

	// Gets the next edge. Returns false if there isn't
	// one left to get. If it returns true, pNode and pEdgeWeight
	// will contain the values of the edge.
	bool GetNext(int* pNode, float* pEdgeWeight);
};