// ReachableArray.cpp: implementation of the ReachableArray class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "AG_MDA.h"
#include "ReachableArray.h"

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

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

ReachableArray::ReachableArray()
{
	m_Dim = 0;
	m_pData = NULL;
	m_pRlt = NULL;
	m_pMid = NULL;
}

ReachableArray::~ReachableArray()
{
	if( m_pData ) delete[] m_pData;
	if( m_pRlt ) delete[] m_pRlt;
	if( m_pMid ) delete[] m_pMid;
}

void ReachableArray::Init(int dim)
{
	if( m_pData ) delete[] m_pData;
	if( m_pRlt ) delete[] m_pRlt;
	if( m_pMid ) delete[] m_pRlt;
	m_pData = new int[ dim * dim ];
	m_pRlt = new int[ dim * dim ];
	m_pMid = new int[ dim * dim ];
	for( int i = 0 ; i < dim * dim ; i ++ )
	{
		m_pData[ i ] = 0;
		m_pRlt[ i ] = 0;
		m_pMid[ i ] = 0;
	}
	m_Dim = dim;
}

void ReachableArray::SetEdge(int col, int row)
{
	if( m_Dim == 0 ) return;
	m_pData[ row * m_Dim + col ] = 1;
	m_pMid[ row * m_Dim + col ] = 1;
	m_pRlt[ row * m_Dim + col ] = 1;
}

int ReachableArray::Reachable(int col, int row)
{
	if( m_Dim == 0 ) return 0;
	return m_pRlt[ row * m_Dim + col ];
}

void ReachableArray::Cal()
{
	for( int i = 0 ; i < m_Dim - 1; i ++ )
	{
		for( int row = 0 ; row < m_Dim ; row ++ )
		{
			for( int col = 0 ; col < m_Dim ; col ++ )
			{
				m_pRlt[ row * m_Dim + col ] = Multiply( row , col );
			}
		}
		for( row = 0 ; row < m_Dim ; row ++ )
		{
			for( int col = 0 ; col < m_Dim ; col ++ )
			{
				m_pMid[ row * m_Dim + col ] += m_pRlt[ row * m_Dim + col ];
			}
		}
	}
	if( m_Dim )
	for(int  row = 0 ; row < m_Dim ; row ++ )
	{
		for( int col = 0 ; col < m_Dim ; col ++ )
		{
			m_pRlt[ row * m_Dim + col ] += m_pData[ row * m_Dim + col ];
		}
	}
}

int ReachableArray::Multiply(int row, int col)
{
	int rlt = 0 ; 
	for( int i = 0 ; i < m_Dim ; i ++ )
	{
		rlt += ( m_pMid[ row * m_Dim + i ] * m_pData[ i * m_Dim + col ] );
	}
	return rlt;
}

void ReachableArray::PrepareForCal()
{
	for( int i = 0 ; i < m_Dim * m_Dim ; i ++ )
	{
		m_pMid[ i ] = m_pData[ i ];
	}
}

int ReachableArray::GetTail()
{
	for( int i = 0 ; i < m_Dim ; i ++ )
	{
		bool got = true;
		for( int j = 0 ; j < m_Dim ; j ++ )
		{
			if( i == j )continue;
			if( Reachable( i , j ) == 0 ){
				got = false;
				break;
			}
		}
		if( got == true ) return i;
	}
	return -1;
}

int ReachableArray::GetHead()
{
	for( int i = 0 ; i < m_Dim ; i ++ )
	{
		bool got = true;
		for( int j = 0 ; j < m_Dim ; j ++ )
		{
			if( i == j )continue;
			if( Reachable( j , i ) == 0 ){
				got = false;
				break;
			}
		}
		if( got == true ) return i;
	}
	return -1;
}

bool ReachableArray::IsBridge(int row, int col)
{
	int tail,head;
	bool isBridge = false;
	if( m_Dim == 0 ) return isBridge;
	if( m_pData[ row * m_Dim + col ] == 0 ) return isBridge;
	PrepareForCal();
	Cal();
	tail = GetTail();
	head = GetHead();
	if( head == -1 || tail == -1 )return isBridge;
	//혼딜맡긋
	m_pData[ row * m_Dim + col ] = 0;
	m_pMid[ row * m_Dim + col ] = 0;
	PrepareForCal();
	Cal();
	if( Reachable( tail , head ) == false ) isBridge = true;
	//뿟릿맡긋
	m_pData[ row * m_Dim + col ] = 1;
	m_pMid[ row * m_Dim + col ] = 1;
	PrepareForCal();
	Cal();
	return isBridge;
}

int ReachableArray::GetEdge(int col, int row)
{
	return m_pData[ row * m_Dim + col ];
}
