ggraph.cpp

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

/*
	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
*/

#include "GGraph.h"
#include <stdio.h>
#include <stdlib.h>
#include "GMacros.h"
#include "GPointerQueue.h"
#include "GHashTable.h"
#include "GRegion.h"

struct GGraphCutEdge;


struct GGraphCutNode
{
public:
	GGraphCutNode* m_pRoot;
	GGraphCutEdge* m_pParent;
	int m_nSibling;
	int m_nChild;
	struct GGraphCutEdge* m_pEdges;


	GGraphCutNode()
		: m_pRoot(NULL), m_pParent(NULL), m_nSibling(-1), m_nChild(-1), m_pEdges(NULL)
	{
	}

	struct GGraphCutNode* GetRoot()
	{
		return m_pRoot;
	}

	void SetRoot(struct GGraphCutNode* pRoot)
	{
		m_pRoot = pRoot;
	}

	struct GGraphCutEdge* GetParentEdge()
	{
		return m_pParent;
	}

	struct GGraphCutEdge* GetFirstEdge()
	{
		return m_pEdges;
	}

	void SetFirstEdge(struct GGraphCutEdge* pEdge)
	{
		m_pEdges = pEdge;
	}

	int GetFirstChild()
	{
		return m_nChild;
	}

	int GetSibling()
	{
		return m_nSibling;
	}
};


struct GGraphCutEdge
{
public:
	int m_nNode1;
	int m_nNode2;
	GGraphCutEdge* m_pNext1;
	GGraphCutEdge* m_pNext2;
	float m_fCapacity;

	struct GGraphCutEdge* GetNextEdge(int nNode)
	{
		if(nNode == m_nNode1)
			return m_pNext1;
		else if(nNode == m_nNode2)
			return m_pNext2;
		else
		{
			GAssert(false, "This edge isn't connected to that node");
			return NULL;
		}
	}

	int GetOtherNode(int nNode)
	{
		if(nNode == m_nNode1)
			return m_nNode2;
		else if(nNode == m_nNode2)
			return m_nNode1;
		else
		{
			GAssert(false, "This edge isn't connected to that node");
			return -1;
		}
	}
};


// ---------------------------------------------------------------------------


GGraphCut::GGraphCut(int nNodes)
{
	m_pQ = new GIntQueue(MAX(1024, nNodes));
	m_pHeap = new GStringHeap(1024);
	m_nNodes = nNodes;
	m_pNodes = new GGraphCutNode[nNodes];
	m_pSource = NULL;
	m_pSink = NULL;
}

GGraphCut::~GGraphCut()
{
	delete(m_pQ);
	delete(m_pHeap);
	delete[] m_pNodes;
}

void GGraphCut::AddEdge(int nNode1, int nNode2, float fCapacity)
{
	GAssert(nNode1 != nNode2, "edge to itself?");
	GAssert(nNode1 >= 0 && nNode1 < m_nNodes, "out of range");
	GAssert(nNode2 >= 0 && nNode2 < m_nNodes, "out of range");
	struct GGraphCutEdge* pNewEdge = (struct GGraphCutEdge*)m_pHeap->Allocate(sizeof(struct GGraphCutEdge));
	pNewEdge->m_nNode1 = nNode1;
	pNewEdge->m_nNode2 = nNode2;
	pNewEdge->m_pNext1 = m_pNodes[nNode1].GetFirstEdge();
	m_pNodes[nNode1].SetFirstEdge(pNewEdge);
	pNewEdge->m_pNext2 = m_pNodes[nNode2].GetFirstEdge();
	m_pNodes[nNode2].SetFirstEdge(pNewEdge);
	pNewEdge->m_fCapacity = fCapacity;
}

void GGraphCut::GetEdgesFromRegionList(GRegionAjacencyGraph* pRegionList)
{
	int nNode1, nNode2;
	float r1, g1, b1, r2, g2, b2;
	int i;
	for(i = 0; i < pRegionList->GetAjacencyCount(); i++)
	{
		pRegionList->GetAjacency(i, &nNode1, &nNode2);
		pRegionList->GetAverageColor(nNode1, &r1, &g1, &b1);
		pRegionList->GetAverageColor(nNode2, &r2, &g2, &b2);
		r1 -= r2;
		g1 -= g2;
		b1 -= b2;
		r1 *= r1;
		g1 *= g1;
		b1 *= b1;
		AddEdge(nNode1, nNode2, (float)1 / (r1 + g1 + b1 + 1));
	}
}

void GGraphCut::RecycleTree(int nChild, int nParent)
{
	struct GGraphCutNode* pChild = &m_pNodes[nChild];
	struct GGraphCutNode* pParent = &m_pNodes[nParent];
	GAssert(pChild->GetRoot(), "Expected the child node to be part of a tree");

	// Unlink the child from the parent
	int nPrev = -1;
	int nCurrent;
	for(nCurrent = pParent->m_nChild; nCurrent != nChild && nCurrent >= 0; nCurrent = m_pNodes[nCurrent].m_nSibling)
		nPrev = nCurrent;
	if(nCurrent < 0)
	{
		GAssert(false, "Failed to find the child");
		return;
	}
	if(nPrev >= 0)
		m_pNodes[nPrev].m_nSibling = pChild->m_nSibling;
	else
		pParent->m_nChild = pChild->m_nSibling;
	pChild->m_nSibling = -1;
	pChild->m_pParent = NULL;
	pChild->m_pRoot = NULL;
	//GAssert(!pChild->IsAncestor(pParent), "still linked");

/*
	// Attempt to find another suitable parent for the tree
	struct GGraphCutEdge* pCandEdge;
	struct GGraphCutNode* pCandidate;
	for(pCandEdge = pChild->GetFirstEdge(); pCandEdge; pCandEdge = pCandEdge->GetNextEdge(pChild))
	{
		if(pCandEdge->m_fCapacity <= 0)
			continue;
		pCandidate = pCandEdge->GetOtherNode(pChild);
		if(pCandidate->GetRoot() != pOldRoot)
			continue;
		if(pCandidate->IsAncestor(pChild))
			continue;
		pCandidate->LinkChild(pCandEdge);
		return;
	}
*/

	// Recursively recycle the children
	int nGrandChild;
	while(true)
	{
		nGrandChild = pChild->GetFirstChild();
		if(nGrandChild < 0)
			break;
		RecycleTree(nGrandChild, nChild);
	}
	GAssert(pChild->GetFirstChild() < 0 && !pChild->GetParentEdge(), "Didn't recycle properly");

	// Any rooted neighbors of the child now become active since they have an unclaimed neighbor
	struct GGraphCutEdge* pEdge;
	int nOther;
	for(pEdge = pChild->GetFirstEdge(); pEdge; pEdge = pEdge->GetNextEdge(nChild))
	{
		if(pEdge->m_fCapacity <= 0)
			continue;
		nOther = pEdge->GetOtherNode(nChild);
		if(m_pNodes[nOther].GetRoot())
			m_pQ->Push(nOther);
	}
}

// pEdge is the edge that joins the two trees
void GGraphCut::AugmentPath(struct GGraphCutEdge* pEdge)
{
	// Find the bottle-neck
	float fBottleneck = pEdge->m_fCapacity;
	int nNode = pEdge->m_nNode1;
	struct GGraphCutEdge* pParentEdge = m_pNodes[nNode].GetParentEdge();
	while(pParentEdge)
	{
		GAssert(pParentEdge->m_fCapacity > 0, "Expected a non-saturated edge");
		if(pParentEdge->m_fCapacity < fBottleneck)
			fBottleneck = pParentEdge->m_fCapacity;
		nNode = pParentEdge->GetOtherNode(nNode);
		pParentEdge = m_pNodes[nNode].GetParentEdge();
	}
	nNode = pEdge->m_nNode2;
	pParentEdge = m_pNodes[nNode].GetParentEdge();
	while(pParentEdge)
	{
		GAssert(pParentEdge->m_fCapacity > 0, "Expected a non-saturated edge");
		if(pParentEdge->m_fCapacity < fBottleneck)
			fBottleneck = pParentEdge->m_fCapacity;
		nNode = pParentEdge->GetOtherNode(nNode);
		pParentEdge = m_pNodes[nNode].GetParentEdge();
	}

	// Augment
	pEdge->m_fCapacity -= fBottleneck;
	nNode = pEdge->m_nNode1;
	pParentEdge = m_pNodes[nNode].GetParentEdge();
	while(pParentEdge)
	{
		pParentEdge->m_fCapacity -= fBottleneck;
		if(pParentEdge->m_fCapacity <= 0)
			RecycleTree(nNode, pParentEdge->GetOtherNode(nNode));
		nNode = pParentEdge->GetOtherNode(nNode);
		pParentEdge = m_pNodes[nNode].GetParentEdge();
	}
	nNode = pEdge->m_nNode2;
	pParentEdge = m_pNodes[nNode].GetParentEdge();
	while(pParentEdge)
	{
		pParentEdge->m_fCapacity -= fBottleneck;
		if(pParentEdge->m_fCapacity <= 0)
			RecycleTree(nNode, pParentEdge->GetOtherNode(nNode));
		nNode = pParentEdge->GetOtherNode(nNode);
		pParentEdge = m_pNodes[nNode].GetParentEdge();
	}
}

void GGraphCut::GrowNode(int nNode)
{
	struct GGraphCutNode* pNode = &m_pNodes[nNode];
	struct GGraphCutEdge* pEdge;
	int nCandidate;
	struct GGraphCutNode* pCandidate;
	struct GGraphCutNode* pCandRoot;
	bool bRedo = false;
	for(pEdge = pNode->GetFirstEdge(); pEdge; pEdge = bRedo ? pEdge : pEdge->GetNextEdge(nNode))
	{
		bRedo = false;
		if(pEdge->m_fCapacity <= 0)
			continue; // this edge has no residual capacity
		nCandidate = pEdge->GetOtherNode(nNode);
		pCandidate = &m_pNodes[nCandidate];
		pCandRoot = pCandidate->GetRoot();
		if(pCandRoot == pNode->GetRoot())
			continue; // the candidate node is already part of this tree
		if(pCandRoot)
		{
			// The two trees now touch, so augment the path in order to break up the connection
			AugmentPath(pEdge);
			if(!pNode->GetRoot())
				return; // this node is no longer part of a tree, so it can't grow anymore
			bRedo = true; // this edge may be valid now, so try it again
		}
		else
		{
			// Link the candidate as a new child of pNode
			GAssert(pCandidate->m_nChild < 0, "That node has children of its own");
			GAssert(pNode != pCandidate, "Circular edge!");
			GAssert(pNode->m_pParent != pEdge, "That's the node's parent edge!");
			pCandidate->m_pRoot = pNode->m_pRoot;
			pCandidate->m_pParent = pEdge;
			pCandidate->m_nSibling = pNode->m_nChild;
			pCandidate->m_nChild = -1;
			pNode->m_nChild = nCandidate;

			// The candidate is now active
			m_pQ->Push(nCandidate);
		}
	}
}

void GGraphCut::Cut(int nSourceNode, int nSinkNode)
{
	// Push the source and sink into the queue
	struct GGraphCutNode* pNode;
	pNode = &m_pNodes[nSourceNode];
	pNode->SetRoot(pNode);
	m_pSource = pNode;
	m_pQ->Push(nSourceNode);
	pNode = &m_pNodes[nSinkNode];
	pNode->SetRoot(pNode);
	m_pSink = pNode;
	m_pQ->Push(nSinkNode);

	// Grow the trees
	int nNode;
	while(m_pQ->GetSize() > 0)
	{
		nNode = m_pQ->Pop();
		if(!m_pNodes[nNode].GetRoot())
			continue; // The node is no longer part of either tree
		GrowNode(nNode);
	}
}

void GGraphCut::FindAHome(int nNode)
{
	// Find a new root for this node
	struct GGraphCutNode* pNode = &m_pNodes[nNode];
	struct GGraphCutNode* pNewRoot = NULL;
	struct GGraphCutNode* pOther;
	struct GGraphCutEdge* pEdge;
	struct GGraphCutEdge* pFollowEdge;
	int nCurrent = nNode;
	int nSafety = 500;
	while(!pNewRoot && --nSafety >= 0)
	{
		pFollowEdge = m_pNodes[nCurrent].GetFirstEdge();
		for(pEdge = pFollowEdge; pEdge; pEdge = pEdge->GetNextEdge(nCurrent))
		{
			pOther = &m_pNodes[pEdge->GetOtherNode(nCurrent)];
			pNewRoot = pOther->GetRoot();
			if(pNewRoot)
				break;
			if((rand() % 4) == 0)
				pFollowEdge = pEdge;
		}
		if(!pFollowEdge)
		{
			pNode->SetRoot(m_pSink);
			return;
		}
		nCurrent = pFollowEdge->GetOtherNode(nCurrent);
	}
	if(!pNewRoot)
		pNewRoot = m_pSink;

	// Give neighbors the same root
	GAssert(m_pQ->GetSize() == 0, "queue still in use");
	pNode->SetRoot(pNewRoot);
	m_pQ->Push(nNode);
	int nOther;
	while(m_pQ->GetSize() > 0)
	{
		nCurrent = m_pQ->Pop();
		for(pEdge = m_pNodes[nCurrent].GetFirstEdge(); pEdge; pEdge = pEdge->GetNextEdge(nCurrent))
		{
			nOther = pEdge->GetOtherNode(nCurrent);
			pOther = &m_pNodes[nOther];
			if(!pOther->GetRoot())
			{
				pOther->SetRoot(pNewRoot);
				m_pQ->Push(nOther);
			}
		}
	}
}

bool GGraphCut::IsSource(int nNode)
{
	GAssert(m_pSource, "You must call 'Cut' before calling this method");
	GAssert(nNode >= 0 && nNode < m_nNodes, "out of range");
	struct GGraphCutNode* pNode = &m_pNodes[nNode];
	if(!pNode->GetRoot())
		FindAHome(nNode);
	return(pNode->GetRoot() == m_pSource);
}

bool GGraphCut::DoesBorderTheCut(int nNode)
{
	bool bSource = IsSource(nNode);
	struct GGraphCutNode* pNode = &m_pNodes[nNode];
	struct GGraphCutEdge* pEdge;
	for(pEdge = pNode->GetFirstEdge(); pEdge; pEdge = pEdge->GetNextEdge(nNode))
	{
		if(IsSource(pEdge->GetOtherNode(nNode)) != bSource)
			return true;
	}
	return false;
}


#ifndef NO_TEST_CODE
//     2--3--4
//   / |  |  | \        .
// 0   |  |  |  1
//   \ |  |  | /
//     5--6--7
// static
void GGraphCut::Test()
{
	GGraphCut graph(8);
	graph.AddEdge(0, 2, 3);
	graph.AddEdge(0, 5, 3);
	graph.AddEdge(1, 4, 3);
	graph.AddEdge(1, 7, 3);
	graph.AddEdge(2, 3, 3);
	graph.AddEdge(3, 4, 1);
	graph.AddEdge(5, 6, 1);
	graph.AddEdge(6, 7, 3);
	graph.AddEdge(2, 5, 3);
	graph.AddEdge(3, 6, 1);
	graph.AddEdge(4, 7, 3);
	graph.Cut(0, 1);
	if(!graph.IsSource(0))
		throw "got the source wrong!";
	if(!graph.IsSource(2))
		throw "got the sink wrong!";
	if(!graph.IsSource(3))
		throw "wrong cut";
	if(!graph.IsSource(5))
		throw "wrong cut";
	if(graph.IsSource(1))
		throw "wrong cut";
	if(graph.IsSource(4))
		throw "wrong cut";
	if(graph.IsSource(6))
		throw "wrong cut";
	if(graph.IsSource(7))
		throw "wrong cut";
}
#endif // !NO_TEST_CODE

// --------------------------------------------------------------------

GGraphEdgeIterator::GGraphEdgeIterator(GGraphCut* pGraph, int nNode)
{
	m_pGraph = pGraph;
	Reset(nNode);
}

GGraphEdgeIterator::~GGraphEdgeIterator()
{
}

void GGraphEdgeIterator::Reset(int nNode)
{
	GAssert(nNode >= 0 && nNode < m_pGraph->GetNodeCount(), "out of range");
	m_nNode = nNode;
	m_pCurrentEdge = m_pGraph->m_pNodes[nNode].GetFirstEdge();
}

bool GGraphEdgeIterator::GetNext(int* pNode, float* pEdgeWeight)
{
	if(!m_pCurrentEdge)
		return false;
	*pNode = m_pCurrentEdge->GetOtherNode(m_nNode);
	*pEdgeWeight = m_pCurrentEdge->m_fCapacity;
	m_pCurrentEdge = m_pCurrentEdge->GetNextEdge(m_nNode);
	return true;
}