connection.cpp

关于连通性的等分路径压缩带权快速合并算法

// Connection.cpp: implementation of the CConnection class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Connection.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

inline DWORD FindRoot(DWORD aID[], DWORD dwIndex)
{
	for(DWORD i=dwIndex; i!=aID[i]; i=aID[i])
		aID[i] = aID[aID[i]];
	return i;
}

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CConnection::CConnection():
m_aID(NULL),m_aW(NULL),m_dwNodeCount(0)
{
}

CConnection::~CConnection()
{
	Release();
}

void CConnection::Release()
{
	DeleteA(m_aID);
	DeleteA(m_aW);
	m_dwNodeCount = 0;
}


void CConnection::Initial(DWORD dwNodeCount)
{
	Release();

	m_dwNodeCount = dwNodeCount;
	m_aID = new DWORD[dwNodeCount];
	m_aW  = new DWORD[dwNodeCount];

	for(DWORD i=0; i<m_dwNodeCount; i++)
	{
		m_aID[i] = i;
		m_aW[i] = 1;
	}
}

void CConnection::SetConnect(DWORD dwIndex1, DWORD dwIndex2)
{
	ASSERT(dwIndex1<GetNodeCount() && dwIndex2<GetNodeCount());
	DWORD dwRoot1 = ::FindRoot(m_aID, dwIndex1);
	DWORD dwRoot2 = ::FindRoot(m_aID, dwIndex2);
	if(dwRoot1==dwRoot2)return;
	if(m_aW[dwRoot1]<m_aW[dwRoot2])
	{
		m_aID[dwRoot1] = dwRoot2;
		m_aW[dwRoot2] += m_aW[dwRoot1];
	}
	else
	{
		m_aID[dwRoot2] = dwRoot1;
		m_aW[dwRoot1] += m_aW[dwRoot2];
	}
}

BOOL CConnection::IsConnect(DWORD dwIndex1, DWORD dwIndex2)const
{
	ASSERT(dwIndex1<GetNodeCount() && dwIndex2<GetNodeCount());
	DWORD dwRoot1 = ::FindRoot(m_aID, dwIndex1);
	DWORD dwRoot2 = ::FindRoot(m_aID, dwIndex2);
	return (dwRoot1==dwRoot2);
}

DWORD CConnection::FindRoot(DWORD dwIndex)const
{
	ASSERT(dwIndex < m_dwNodeCount);
	return ::FindRoot(m_aID, dwIndex);
}

DWORD CConnection::GetConnect(DWORD dwIndex, DWORD aConnectID[])const
{
	ASSERT(dwIndex < m_dwNodeCount);
	DWORD dwRoot = ::FindRoot(m_aID, dwIndex);
	DWORD dwCount = 0;

	for(DWORD i=0; i<m_dwNodeCount; i++)
	{
		DWORD dwRootFind = ::FindRoot(m_aID, i);
		if(dwRootFind == dwRoot)
		{
			if(i==dwIndex)continue;
			if(aConnectID)aConnectID[dwCount]=i;
			dwCount++;
		}
	}

	return dwCount;
}

DWORD CConnection::GetUnConnect(DWORD dwIndex, DWORD aConnectID[])const
{
	ASSERT(dwIndex < m_dwNodeCount);
	DWORD dwRoot = ::FindRoot(m_aID, dwIndex);
	DWORD dwCount = 0;

	for(DWORD i=0; i<m_dwNodeCount; i++)
	{
		DWORD dwRootFind = ::FindRoot(m_aID, i);
		if(dwRootFind != dwRoot)
		{
			if(aConnectID)aConnectID[dwCount]=i;
			dwCount++;
		}
	}

	return dwCount;
}