

/**************************************************************************************
*        Symbolic Circuit Analysis With TPDDs (Tree Pair Decision Diagram)
* Subgraph.cpp
* Member functions for class Subgraph.
* Subgraph is the class to represent one tree of the tree pair.
*
* CHEN Weiwei		GShi	06/03/31
* School of Microelectronics, Shanghai Jiaotong Univ.
* {chenweiwei, shiguoyong}@ic.sjtu.edu.cn
**************************************************************************************/

#include <cstdlib>
#include <cstring>

#include "gpdd_defs.h"
#include "gpdd_global.h"
#include "gpdd_struct.h"
#include "Subgraph.h"


//Change by Xu Hui
//Subgraph::Subgraph(EdgeInfo *pe, int En, int Nn, int s)
Subgraph::Subgraph(EdgeInfo *edgelist, int numedges, int numnodes, int sign, int totalnodes)
{
		EdgeList	= edgelist;
		NumEdges = numedges;
		NumNodes = numnodes;
		Sign	= sign;
		//Change by Xu Hui
		TotalNodes = totalnodes;
}

Subgraph::~Subgraph()
{
	if (EdgeList)
	{
		delete [] EdgeList;
	}
	EdgeList = NULL;
}


unsigned Subgraph::Hash(unsigned i)
{
	int j;
	unsigned result = 0;
/*	if(tag)
		return NumEdges;*/

	for(j = 0; j < NumEdges; j ++)
	{
		if(EdgeList[j].node1 ^ EdgeList[j].node2)
			result += (((EdgeList[j].node1 + 1) << 9) ^ ((EdgeList[j].node2 + 1) << 7)) * (EdgeList[j].edgenum);
	}
	return ((result ^ i) % SUBGRAPH_PRIME);
}
	
int Subgraph::Compare(Comparable *p)
{
	ASSERT( p->isa() == SUBGRAPH, "not a Subgraph Object");
 
	Subgraph *n = (Subgraph *)p;

	if(NumEdges == n->GetNumEdges() && NumNodes == n->GetNumNodes())
	{
		return this->CompareGraph(n);
	}

	if((long int)this > (long int)n)
		return 1;
	else
		return -1;
}

unsigned Subgraph::HashTreeID()
{
	int i;
	unsigned result = 0;
	for(i = 0; i < NumEdges; i ++)
		result ^= (EdgeList[i].edgenum);

	return ((NumEdges * TotalNodes + NumNodes) * result) % SUBGRAPH_PRIME;
}
	
int Subgraph::CompareGraph(Subgraph * pSubgraph)
{
	int ne1, ne2, i;
	EdgeInfo *pC, *pS;

	ne1 = this->CountValidEdges();
	ne2 = pSubgraph->CountValidEdges();

/*	if(ne1 != ne2)
	{
		if((int)this > (int)pSubgraph)
			return 1;
		else
			return -1;
	}*/	

	if (NumNodes == 2 && ne1 == 1 && ne2 == 1)
	{
		if ((this->GetFirstDirectedEdge() == pSubgraph->GetFirstDirectedEdge()) 
				&& !EdgeList[this->GetFirstValidEdge()].isSrc)
			return 0;
		else
			return ((long int)this > (long int)pSubgraph ? 1 : -1);
	}

	for (i = 0; i < NumEdges; i ++)
	{
		pC = &EdgeList[i];
		pS = &pSubgraph->GetSubgraph()[i];

		if ((pC->edgenum ^ pS->edgenum) || (pC->node1 ^ pS->node1) || (pC->node2 ^ pS->node2))
		{
			if ((long int)this > (long int)pSubgraph)
				return 1;
			else
				return -1;
		}
	}

	return 0;
}

int Subgraph::CountValidEdges()
{
	int	validedges = 0;
	
	for (int i = 0; i < NumEdges; i ++)
	{
		if (EdgeList[i].node1 ^ EdgeList[i].node2)
			validedges ++;
	}
	
	return validedges;
}

/**
	Get the index of the first valid edge in the reduced graph.
	This function is designed to assist the function CompareGraph.
	@return the index of the first valid edge.
*/
int Subgraph::GetFirstValidEdge()
{
	for (int i = 0; i < NumEdges; i ++)
	{
		if (EdgeList[i].node1 ^ EdgeList[i].node2)
			return i;
	}
	return -1;
}


/**
	Get the index of the first directed valid edge in the reduced graph.
	This function is designed to assist the function CompareGraph.
	@return the index of the first valid edge, position direction with positive sign and vice versa.
*/
int Subgraph::GetFirstDirectedEdge()
{
	int	dir;
	
	for (int i = 0; i < NumEdges; i ++)
	{
		if (EdgeList[i].node1 ^ EdgeList[i].node2)	//(node1 != node2)
		{
			dir = EdgeList[i].node1 > EdgeList[i].node2 ? 1 : -1;
			
			//modified by Xu Hui
			//since edgenum begin from 0, it should be add 1.
			//(0*-1 == 0*1)
			return (EdgeList[i].edgenum+1) * dir;
		}
	}
	return 0;
}

int Subgraph::CompleteCompareGraph(Subgraph * pSubgraph, int edgeNum)
{
	int i, j, k, v, tag1, tag2, tag3;
	edgeComp* pNew, *pCur, *peSrc, *peDes;
	vertexComp* pvSrc, *pvDes;

	int *mark = new int[TotalNodes];
	vertexComp* vSrc = new vertexComp[TotalNodes];
	vertexComp* vDes = new vertexComp[TotalNodes];

//	memset(vSrc, 0, TotalNodes * sizeof(vertexComp));
//	memset(vDes, 0, TotalNodes * sizeof(vertexComp));

	for(i = 0; i < TotalNodes; i ++)
	{
		vSrc[i].edgeSum = 0;
		vSrc[i].pedge = NULL;
		vSrc[i].vertexNo = i;

		vDes[i].edgeSum = 0;
		vDes[i].pedge = NULL;
		vDes[i].vertexNo = i;
	}

	memset(mark, 0, TotalNodes * sizeof(int));

	for(i = 0; i < NumEdges; i ++)
	{
		pNew = new edgeComp;
		pNew->direct = 1;
		pNew->edgeNo = EdgeList[i].edgenum;
		v = EdgeList[i].node1;
		pNew->pNext = vSrc[v].pedge;
		vSrc[v].pedge = pNew;
		vSrc[v].edgeSum ++;

		pNew = new edgeComp;
		pNew->direct = -1;
		pNew->edgeNo = EdgeList[i].edgenum;
		v = EdgeList[i].node2;
		pNew->pNext = vSrc[v].pedge;
		vSrc[v].pedge = pNew;
		vSrc[v].edgeSum ++;

		pNew = new edgeComp;
		pNew->direct = 1;
		pNew->edgeNo = pSubgraph->EdgeList[i].edgenum;
		v = pSubgraph->EdgeList[i].node1;
		pNew->pNext = vDes[v].pedge;
		vDes[v].pedge = pNew;
		vDes[v].edgeSum ++;

		pNew = new edgeComp;
		pNew->direct = -1;
		pNew->edgeNo = pSubgraph->EdgeList[i].edgenum;
		v = pSubgraph->EdgeList[i].node2;
		pNew->pNext = vDes[v].pedge;
		vDes[v].pedge = pNew;
		vDes[v].edgeSum ++;
	}

/*********************** Compare ***********************************/

	tag3 = 0;

	for(i = 0; i < TotalNodes; i ++)
	{
		pvSrc = &vSrc[i];
		if(!pvSrc->edgeSum)
			continue;
		
		tag2 = 0;

		for(j = 0; j < TotalNodes; j ++)
		{
			pvDes = &vDes[j];
			if(pvSrc->edgeSum == pvDes->edgeSum && !mark[pvDes->vertexNo])
			{
				peSrc = pvSrc->pedge;
				peDes = pvDes->pedge;
					
				tag1 = 0;

				while(peSrc)
				{
					if(peSrc->edgeNo == peDes->edgeNo && peSrc->direct == peDes->direct)
					{
						peSrc = peSrc->pNext;
						peDes = peDes->pNext;
						continue;
					}
					tag1 = 1;
					break;
				}

				if(!tag1)
				{
					mark[pvDes->vertexNo] = 1;
					tag2 = 1;
					break;
				}
			}
		}

		if(!tag2)
		{
			tag3 = 1;
			break;
		}
	}

	for(i = 0; i < TotalNodes; i ++)
	{
		pCur = vSrc[i].pedge;
		while(pCur)
		{
			vSrc[i].pedge = pCur->pNext;
			delete pCur;
			pCur = vSrc[i].pedge;
		}

		pCur = vDes[i].pedge;
		while(pCur)
		{
			vDes[i].pedge = pCur->pNext;
			delete pCur;
			pCur = vDes[i].pedge;
		}
	}

	delete[] vSrc;
	delete[] vDes;

	if(tag3)
	{
		if((long int)this > (long int)pSubgraph)
			return 1;
		else
			return -1;
	}

	return 0;
}


//Add by XuHui
void Subgraph::PrintGraph(Edge *Elist)
{
	cout << LINE_INFO << endl;
	
	EdgeInfo *pE;
	for(int i=0; i<NumEdges; i++)
	{
	pE = &EdgeList[i];
	std::cout << "\t" << Elist[pE->edgenum].name << "(" << pE->node1 << ", "
	     << pE->node2 << ")" << std::endl;
	}
}




