/*
最大團問題描述：
G的完全子圖U是G的一個團當且僅當U不包含在G的更大的完全子圖中
G的最大團是指G中所含頂點數最多的團
G的空子圖U是G的一個獨立集當且僅當U不包含在G的更大的空子圖中
G的最大獨立集是G中所含頂點數最多的獨立集

最大團和最大獨立子集問題都可以用回溯法在O(n2^n)時間內解決
設當前擴展結點Z位于解空間樹的第i層。
在進入左子樹前，必須確認從頂點i到已選入的頂點集中每一個頂點
都有邊相連。在進入右子樹前，必須確認還有足夠多的可選擇頂點使得算法
有可能在右子樹中找到更大的團
*/
/*
利用到最大堆，因為每個結點的結點上限個數
就是優先級。且每個結點屬性都相同，所以不需要進行預處理，來對各個結點進行排序，以達到
搜索上的優化，像0-1背包問題，因為每個包的屬性都不相同，所以通過一定的預處理可以達到比較好的
搜索效果。而這里是不必要進行預備處理的，因為各個結點只有名稱不同，而且求的只是總個數
*/
#include<iostream>
using namespace std;

template<class Type>
class MaxHeap
{
	public:
		Type *H;
		int Capacity;
		int Size;
	public:
		MaxHeap(int n)
		{
			H = NULL;
			H = new Type[n+1];
			Capacity = n;
			Size = 0;
		};
		MaxHeap( MaxHeap& a )
		{
			//要排除自賦值的情況
			if ( this.H != a.H )
			{
				this.H = a.H;
				this.Size = a.Size;
				this.Capacity = a.Capacity;
				for( int i = 0; i < Size; ++i )
				{
					this.H[i] = a.H[size];
				}
			}
		};

		/*
		基本的堆插入操作
		為了將node插入到堆中
		首先在下一個空閑位置++Size處，創建一個空穴，否則該堆將不是完全樹
		如果x可以放在該穴中而不破壞堆的序，那么插入完成
		否則我們把空穴的父親結點上的元素移動到該穴中，這樣空穴就朝著根的方向上行一步
		繼續該過程直到x能被放入空穴為止
		*/
		void Insert( Type& node )
		{
			//插入元素的時候按照從大到順序
			for( int i = ++Size; H[ i / 2 ] < node && i != 0; i /= 2 )
			{
				//cout<<"小于"<<endl;
				H[i] = H[ i / 2 ];
			}
			//一定要注意從下標一開始的時候，添加如何進行比較才行
			H[i] = node;
			//cout<<"insert i = "<<i<<endl;
			//cout<<"H[1].print():"<<endl;
			//H[1].print();
			
			//cout<<"Insert Size = "<<Size<<endl;
			for( int k = 1; k <= Size; ++k )
			{
				//cout<<"H["<<k<<"]: "<<endl;
				//H[k].print();
			}
			
		};

		/*
		當刪除一個最小元時
		在根結點處產生一個空穴。
		由于現在堆少了一個元素，因此堆中最后一個元素必須移動到該堆的某個地方
		如果x可以放到空穴中，那么DeleteMin完成
		否則應該將兩個兒子中較小者移入空穴
		這樣空穴就向下推了一層。重復該步驟直到x可以被放入空穴中
		*/
		void DeleteMax( Type& node )
		{
			int i,Child;
			Type MinElement,LastElement;
			node = H[1];
			/*
			cout<<"Size = "<<Size<<endl;
			for( int k = 1; k < Size; ++k )
			{
				cout<<"H["<<k<<"]: "<<endl;
				H[k].print();
			}
			*/
			
			//cout<<"node: "<<endl;
			//node.print();
			LastElement = H[Size--];

			for( i = 1; i * 2 <= Size; i = Child )
			{
				Child = i * 2;
				if ( ( Child != Size && H[ Child + 1 ] > H[ Child ] ) )
				{
					Child++;
				}

				if ( LastElement < H[ Child ] )
					//找到孩子結點中最大的一個覆蓋孩子結點
				{
					H[ i ] = H[ Child ];      
				}
				else
				{
					break;
				}
			}
			H[i] = LastElement;
			//node = MinElement;

		};
};

class bbnode
{
	friend class Clique;
public:
	bbnode()
	{
		parent = 0;
		LChild = 0;
	}
private:
	bbnode *parent;
	//指向父結點的指針
	bool LChild;
	//左兒子結點標志
};

class CliqueNode
{
	friend class Clique;
public:
	CliqueNode()
	{
		ptr = 0;
		ptr = new bbnode();
		cn = 0;
		un = 0;
		level = 0;
	}
	operator int() const
	{
		return un;
	}
	bool operator>( CliqueNode& a ) const
	{
		return un > a.un;
	}
private:
	int cn;
	//當前團的頂點數
	int un;
	//當前團的最大頂點數的上界
	int level;
	//結點在子集空間樹中所處的層次
	bbnode* ptr;
	//指向活結點在子集樹中相應結點的指針
};

class Clique
{
	friend void main(void);
public:
	int BBMaxClique( int [] );
private:
	void AddLiveNode( MaxHeap< CliqueNode > &H,
					  int cn,
					  int un,
					  int level,
					  bbnode *E,
					  bool ch );
	int **a;
	//圖G的鄰接矩陣
	int n;
	//圖G的頂點數
};

/*
算法中函數AddLiveNode的功能是將當前構造出的活結點
加入到子集空間樹中并插入活結點優先隊列中
*/
void Clique::AddLiveNode( MaxHeap< CliqueNode > &H,
						  int cn,
						  int un,
						  int level,
						  bbnode *E,
						  bool ch )
{
	//將活結點加入到子集空間樹中并插入到最大堆中
	bbnode *b = new bbnode;
	b->parent = E;
	b->LChild = ch;
	CliqueNode N;
	N.cn = cn;
	N.ptr = b;
	N.un = un;
	N.level = level;
	H.Insert( N );
}

/*
子集樹的根結點是初始擴展結點
對于這個特殊的擴展結點，其cn的值為0
變量i用于表示當前擴展結點在解空間樹中所處的
層次。因此，初始時擴展結點所相應的i值為1
當前最大團的頂點數存儲于變量bestn中
在while循環中，我們不斷從活結點優先隊列中抽取當前
擴展結點并實施對該結點的擴展。while循環的終止條件是遇到子集樹中的
一個葉結點（既n+1層結點）成為當前擴展結點。
對于子集樹中的一個葉結點，我們有un = cn。
此時活結點優先隊列中剩余的結點的un值均不超過當前擴展結點的un值
從而進一步搜索不可能得到更大的團，此時算法已找到一個最優解
*/

/*
由于每一個圖都有最大團
因此在從最大堆中抽取極大元素時不必測試堆是否為空是為什么
算法的while循環僅當遇到一個葉結點時退出
*/

int Clique::BBMaxClique( int bestx[] )
{
	//解最大團問題的優先隊列式分支限界法
	//定義最大堆的容量為1000
	MaxHeap< CliqueNode > H(1000);
	bbnode *E = 0;
	int i = 1;
	int cn = 0;
	int bestn = 0;
	//搜索子集空間樹
	while( i != n + 1 )
	{
		//非葉結點
		//檢查頂點i與當前團中其他頂點之間是否有邊相連
		bool OK = true;
		bbnode *B = E;
		for( int j = i - 1; j > 0; B = B->parent,j-- )
		{
			if ( B->LChild && a[i][j] == 0 )
			{
				OK = false;
				break;
			}
		}
		if ( OK )
		{
			//左兒子結點為可行結點
			if ( cn + 1 > bestn )
			{
				bestn = cn + 1;
			}
			AddLiveNode( H, cn + 1, cn + (n - i + 1), i + 1, E, true );
			//n-i+1是剩余的所有頂點數，所以當前團里的頂點數加上剩余的總的頂點數
			//
		}
		if ( cn + n - i >= bestn )
		{
			//右子樹可能含有最優解
			AddLiveNode( H, cn, cn + n - i, i + 1, E, false );
		}
		//取下一個擴展結點
		CliqueNode N;
		H.DeleteMax( N );
		//堆非空
		E = N.ptr;
		cn = N.cn;
		i = N.level;
	}
	//構造當前最優解
	for ( int j = n; j > 0; --j )
	{
		bestx[j] = E->LChild;
		E = E->parent;
	}
	return bestn;
}

void main()
{
	Clique t;
	int V[6][6] =
	{
		{0,2,0,0,0,0},
		{0,1,1,0,1,1},
		{0,1,1,1,0,1},
		{0,0,1,1,0,1},
		{0,1,0,0,1,1},
		{0,1,1,1,1,1}
	};
	//cout<<*(V+1)<<endl;
	/*
	V指向第0行的首地址
	*V第0行第0列的地址
	**V第0行第0列的元素
	*/
	//cout<<*V<<endl;
	int **a = new int*[6];
	for( int j = 0; j < 6; ++j )
	{
		a[j] = new int[6];
	}
	for( j = 0; j < 6; ++j )
	{
		for( int k = 0; k < 6; ++k )
			a[j][k] = V[j][k];
	}
	//int **a = V;
	//常量指針，不能賦值給變量

	int b[6] = {0,0,0,0,0,0};
	int *c = b;
	int n = 5;
	t.a = a;
	t.n = 5;
	t.BBMaxClique(b);
	for( int i = 0; i <= 5; ++i )
	{
		if ( b[i] == 1 )
		{
			cout<<i<<endl;
		}
	}
	return;
}