
/**************************************************************************************
*        Symbolic Circuit Analysis With GPDDs (Graph-Pair Decision Diagram)
* Subgraph.h
* Class Definition for Subgraph.
* Subgraph is the class to represent one tree of the tree pair.
*
* CHEN Weiwei, G. Shi; 	03-31-2006
* School of Microelectronics, Shanghai Jiaotong Univ.
* {shiguoyong}@ic.sjtu.edu.cn
**************************************************************************************/


#ifndef SUBGRAPH_H
#define SUBGRAPH_H

#include "Comparable.h"
#include "gpdd_struct.h"
#include "class_id.h"

/**
	The class for the reduced graph for graph reduce process.
	It is proper to name this class subReduceGraph.
*/

class Subgraph : public Comparable
{	
private:
	short NumEdges   ;

	short NumNodes   ;

	/** 
		the sign of the reduced graph.
		the sign of the node equals 
		<BR>
		signL(sign of theleft reduced graph) * signR(sign of the right reduced graph).
	*/
	short Sign		;

	/// the pointer to the array recording the edge infos in the reduced graph.
	EdgeInfo *EdgeList;

	/// Added by Xu Hui
	int TotalNodes;
public:
	/**
		The default constructor of Subgraph.
	*/
	Subgraph(){};

	/**
		The constructor of a Subgraph.
		@param pe the pointer to the array recording the edge infos in the reduced graph.
		@param En the number of the edges in the reduced graph.
		@param Nn the number of the nodes in the reduced graph.
		@param s  the sign of the reduced graph.
	*/
	//Subgraph(EdgeInfo *pe, int En, int Nn, int s);
	//Change by Xu Hui
	Subgraph(EdgeInfo *pe, int En, int Nn, int s, int TotalN);

	/**
		The destructor of the Subgraph.
	*/
	~Subgraph();

	/**
		Get the pointer to the array recording the edge infos in the reduced graph.
		@return EdgeInfo* EdgeList.
	*/
	inline EdgeInfo * GetSubgraph() {return EdgeList;}

	/**
		Get the the number of the edges in the reduced graph.
		@return int EdgeNum.
	*/
	inline int GetNumEdges() {return NumEdges;}

	/**
		Get the the number of the nodes in the reduced graph.
		@return int NodeNum.
	*/
	inline int GetNumNodes() {return NumNodes;}

	/**
		Get the sign of the reduced graph.
		@return int sign.
	*/
	inline int GetSign() {return Sign;}
//	inline short GetTag() {return tag;}

	/**
		Set the pointer to the array recording the edge infos in the reduced graph.
		@param pe the pointer to the array recording the edge infos in the reduced graph.
	*/
	inline void SetEdgeList(EdgeInfo *edgelist) { EdgeList = edgelist;}

	/**
		Set the number of the edges in the reduced graph.
		@param En the number of the edges in the reduced graph.
	*/
	inline void SetNumEdges(int En) { NumEdges = En;}

	/**
		Set the number of the nodes in the reduced graph.
		@param Nn the number of the nodes in the reduced graph.
	*/
	inline void SetNumNodes(int Nn) { NumNodes = Nn;}

	/**
		Set the sign of the reduce graph.
		@param s the sign of the reduced graph.
	*/
	inline void SetSign(int sign) {Sign = sign;}
//	inline void SetTag(int t) {tag = t;}

	/**
		The function to identify the type of this class
		@return SUBTREE
	*/
	virtual int isa() {return SUBGRAPH;}


	/**
	    The function to get the hash value.
		The value is determined by all the edges in the reduced graph.
	*/
	virtual unsigned Hash(unsigned i = 0);

	/**
		The function to compare two Subgraphs with the same hash value.
		@param p: the Subgraph with the same hash value with this Subgraph.
	*/
	virtual int Compare(Comparable *p);

	/**
		 The function to get the entry of the hash table.
		 the entry is determined by the number of the edges and nodes in the reduced graph.
	*/
	unsigned HashTreeID();

	/**
		The function to compare two Subgraphs.
		@param pSubTree the Subgraph to be compared with the Subgraph pointed by this.
		@return 1 the two Subgraphs are identical.
		@return 0 the two Subgraphs are different.
	*/
	int CompareGraph(Subgraph * pSubgraph);

	/**
		The function to compare two Subgraphs isomorphic or not.
		@param pSubTree the Subgraph to be compared with the Subgraph pointed by this.
		@param edgeNum the number of the edges.
		@return 1 the two Subgraphs are isomorphic.
		@return 0 the two Subgraphs are not isomorphic.

		Two reduced graphs are isomorphic if and only if they have the same topologies.
		(The index of the nodes may be different but the connection of the edges should be the same.)

	  <BR>	The complexity of this function is O(E*N).
	  <BR>	E = the number of the edges.
	  <BR>	N = the number of the nodes.
	  <BR><PRE><I><EM> graph1 and graph2 is isomorphic.	</EM></I></PRE>
      <PRE>     v1                         v1			</PRE>
      <PRE>     /\                         /\			</PRE>
      <PRE>    /  \                       /  \			</PRE>
      <PRE>e1 /    \  e3              e2 /    \  e3		</PRE>
      <PRE>  /      \                   /      \		</PRE>	
      <PRE> v2 ----- v3                v2 ----- v3		</PRE>
      <PRE>      e2                         e1			</PRE>
      <PRE>    graph1                     graph2		</PRE>

	  <BR><PRE><I><EM> graph1 and graph2 is not isomorphic.	</EM></I></PRE>
      <PRE>     v1                         v1			</PRE>
      <PRE>     /\                         /|\			</PRE>
      <PRE>    /  \                       / | \			</PRE>
      <PRE>e1 /    \  e3              e2 / /e1 \  e3	</PRE>
      <PRE>  /      \                   /_/     \		</PRE>	
      <PRE> v2 ----- v3                v2      v3		</PRE>
      <PRE>      e2                         			</PRE>
      <PRE>    graph1                     graph2		</PRE>
	*/
	int CompleteCompareGraph(Subgraph * pSubTree, int edgeNum);

	/**
		Count the number of the valide edges in the reduced graph.
		The valid edges should not be shelf-looped.
	*/
	int CountValidEdges();

	int GetFirstValidEdge();
	int GetFirstDirectedEdge();

	void PrintGraph(Edge *Elist);
	
};


#endif


