//1. Class BiGraph_ME: 
#include "MutuallyExclusive.h"

set<string> mySetIntersection(set<string> s1, set<string> s2)
{
	set<string> L_rets;
	set<string>::iterator iset1,iset2;
	for (iset1 = s1.begin(); iset1 != s1.end(); iset1++)
	{
		iset2 = s2.find(*iset1);
		if (iset2 != s2.end())
		{
			L_rets.insert(*iset1);
		}
	}
	return L_rets;
}

void printSet(set<string> p_s)
{
	set<string>::iterator iset;
	for (iset=p_s.begin(); iset!=p_s.end(); iset++)
	{
		cout<<*iset<<"; ";
	}
	cout<<'\n';
}

list<string> mySplit(string str, string deli)
{
	int st=0;
	list<string> ret;
	int idx1,idx2;
	idx1=-1;
	for (int i=0; i<str.length(); i++)
	{
		int tempSt=0;
		char c=str[i];
		for (int j=0; j<deli.length(); j++)
		{
			if (c==deli[j])
			{
				tempSt=1;
			}
		}
		if (tempSt==1)
		{
			if (st==0)
			{
				st=1;
				idx2=i;
				string tempS1=str.substr(idx1+1,idx2-idx1-1);
				ret.push_back(tempS1);
				idx1=idx2;
			}
			else
			{
				idx1=i;
			}
		}
		else
		{
			st=0;
		}
	}
	if (st==0)
	{
		idx2=str.length();
		string tempS2=str.substr(idx1+1,idx2);
		ret.push_back(tempS2);
	}
	return ret;
}

struct biGraphString
{
	string GoID;
	list<string> edges;
};

class BiGraph_ME
{
	public:
		//int mVertex[maxGraphSize],mVertexStatus[maxGraphSize],mCoverTumorNO[maxGraphSize];
		int mCoverTumorNO[maxGraphSize];
		set<int> mVertex;
		double mWeight[maxGraphSize];
		int mVertexNo;
		set<int> mNeighborOrg[maxGraphSize],mNeighborCur[maxGraphSize];
		string mVertexID2Name[maxGraphSize];
		int tempLevel;
		int mTumorNo;

		BiGraph_ME(const BiGraph_ME& p);
		BiGraph_ME();
		BiGraph_ME(biGraphString& g);

		int findNodeMaxDegree();
		int findKeyNode3Degree();
		int findMidNode4Path();
		BiGraph_ME subGraph(set<int> p_nodes);
		void delete_nodes(set<int> p_nodes);
		void add_nodes(set<int> p_nodes);
		list<BiGraph_ME> connected_components();
		ME_mutation WMEM_cover_2();
		ME_mutation WMEM_cover_3();
		ME_mutation WMEM_cover_main();

		void printGraph();
		void printSolution(ME_mutation p_solu);
		void printSolution_gene(ME_mutation p_solu);


};

BiGraph_ME::BiGraph_ME(const BiGraph_ME& p)
{
	mVertexNo = p.mVertexNo;
	set<int>::iterator iset,inode;
	int i;
	for (inode = (p.mVertex).begin(); inode != (p.mVertex).end(); inode++)
	{
		i = *inode;
		mVertex.insert(i);
		mCoverTumorNO[i] = p.mCoverTumorNO[i];
		mVertexID2Name[i] = p.mVertexID2Name[i];
		mWeight[i] = p.mWeight[i];
		
		for (iset=p.mNeighborOrg[i].begin(); iset!=p.mNeighborOrg[i].end(); iset++)
		{
			mNeighborOrg[i].insert(*iset);
		}
		for (iset=p.mNeighborCur[i].begin(); iset!=p.mNeighborCur[i].end(); iset++)
		{
			mNeighborCur[i].insert(*iset);
		}
	}
}

BiGraph_ME::BiGraph_ME()
{
	mVertexNo = 0;
}

BiGraph_ME::BiGraph_ME(biGraphString& g)
{
	int count,nIdx;
	set<string> biTumors[maxGraphSize];
	list<string>::iterator inodes,iedges;
	inodes = (g.edges).begin();
	//cout<<"\n----"<<g.GoID<<'\n';
	nIdx = -1;
	mVertexNo = 0;
	while (inodes != (g.edges).end())
	{
		nIdx += 1;
		//cout<<*inodes<<'\n';
		list<string> edges;
		edges = mySplit(*inodes, "|");
		//cout<<"\n----size"<<(edges.size()-2)<<'\n';
		mCoverTumorNO[nIdx] = (edges.size()-2);
		iedges = edges.begin();
		count = -1;
		while(iedges!=edges.end())
		{
			count += 1;
			if (count ==0)
			{
				//cout<<"\n\n-----------Node: "<<*iedges<<"---"<<nIdx<<'\n';
				mVertex.insert(nIdx);
				mVertexNo += 1;
				mVertexID2Name[nIdx] = *iedges;
			}
			else
			{
				if (count == 1)
				{
					//cout<<"  Weight: "<<*iedges<<"\n  Edges: ";
					mWeight[nIdx] = atof((*iedges).c_str());
				}
				else
				{
					//cout<<*iedges<<"; ";
					biTumors[nIdx].insert(*iedges);
				}
			}
			iedges++;
		}
		inodes++;
	}

	//cout<<"\n==================================\n";
	//cout<<mVertex.size()<<"--- "<<mVertexNo<<"\n";
	//cout<<mVertex.size()<<"  "<<mVertexID2Name[86]<<"  "<<mWeight[86]<<"   "<<biTumors[86].size()<<"  "<<mVertexNo<<"  "<<mCoverTumorNO[86]<<'\n';
	set<string> L_tumors;
	set<string>::iterator iL_tumors;
	for (int i=0; i<mVertexNo; i++)
	{
		for (iL_tumors=biTumors[i].begin(); iL_tumors!=biTumors[i].end(); iL_tumors++)
		{
			L_tumors.insert(*iL_tumors);
		}
	}
	mTumorNo = L_tumors.size();

	int countCom = 0;
	for (int i=0; i<mVertexNo-1; i++)
	{
		for (int j=i+1; j<mVertexNo; j++)
		{
			set<string> cset = mySetIntersection(biTumors[i],biTumors[j]);
			if (cset.size()>0)
			{
				mNeighborOrg[i].insert(j);
				mNeighborOrg[j].insert(i);
				mNeighborCur[i].insert(j);
				mNeighborCur[j].insert(i);
				if (countCom<0)
				{
					printSet(biTumors[i]);
					printSet(biTumors[j]);
					printSet(cset);
					//cout<<"------\n";
					countCom += 1;
				}
			}
		}
	}
	//for (int i=0; i<mVertexNo; i++)
	//{
		//cout<<i<<"---"<<mVertexID2Name[i]<<"  "<<mNeighborOrg[i].size()<<"\n";
	//}
}

int BiGraph_ME::findNodeMaxDegree()
{
	int L_rets;
	set<int>::iterator inode;
	inode=mVertex.begin();
	L_rets = *inode;
	for (inode=mVertex.begin(); inode != mVertex.end(); inode++)
	{
		if (mNeighborCur[L_rets].size()<mNeighborCur[*inode].size())
		{
			L_rets = *inode;
		}
	}
	//cout<<"\n----maxDegree: "<<L_rets<<"; "<<mNeighborCur[L_rets].size();
	return L_rets;
}

int BiGraph_ME::findKeyNode3Degree()
{
	int L_rets;
	set<int>::iterator inode;
	inode=mVertex.begin();
	L_rets = *inode;
	for (inode=mVertex.begin(); inode != mVertex.end(); inode++)
	{
		if (mNeighborCur[L_rets].size()>mNeighborCur[*inode].size())
		{
			L_rets = *inode;
		}
	}
	if (mNeighborCur[L_rets].size()>=3)
	{
		return L_rets;
	}
	int countLen = 1;
	set<int> tpNode;
	tpNode.insert(L_rets);
	while (countLen>0)
	{
		for (inode = mNeighborCur[L_rets].begin(); inode != mNeighborCur[L_rets].end(); inode++)
		{
			if (tpNode.find(*inode)==tpNode.end())
			{
				L_rets = *inode;
				tpNode.insert(*inode);
				break;
			}
		}
		if (mNeighborCur[L_rets].size()==3)
		{
			break;
		}
	}
	//cout<<"\n----node33"<<L_rets<<"; "<<mNeighborCur[L_rets].size()<<'\n';
	return L_rets;
}


int BiGraph_ME::findMidNode4Path()
{
	int L_rets,st;
	set<int>::iterator inode;
	inode=mVertex.begin();
	L_rets = *inode;
	if (mVertex.size()<=2)
	{
		return L_rets;
	}
	st = 0;
	for (inode=mVertex.begin(); inode != mVertex.end(); inode++)
	{
		if (mNeighborCur[*inode].size()==1)
		{
			L_rets = *inode;
			st = 1;
			break;
		}
	}
	if (st == 0)
	{
		return L_rets;
	}
	int countLen = (mVertex.size()/2);
	set<int> tpNode;
	tpNode.insert(L_rets);
	while (countLen>0)
	{
		for (inode = mNeighborCur[L_rets].begin(); inode != mNeighborCur[L_rets].end(); inode++)
		{
			if (tpNode.find(*inode)==tpNode.end())
			{
				L_rets = *inode;
				tpNode.insert(*inode);
				countLen -= 1;
				break;
			}
		}
	}
	//cout<<"----"<<L_rets<<"; "<<mNeighborCur[L_rets].size()<<'\n';
	return L_rets;
}

BiGraph_ME BiGraph_ME::subGraph(set<int> p_nodes)
{
	BiGraph_ME L_subGraph;
	int i;
	set<int>::iterator iset,inode;
	for (inode = p_nodes.begin(); inode != p_nodes.end(); inode++)
	{
		i = *inode;
		L_subGraph.mVertex.insert(i);
		L_subGraph.mCoverTumorNO[i] = mCoverTumorNO[i];
		L_subGraph.mWeight[i] = mWeight[i];
		L_subGraph.mVertexID2Name[i] = mVertexID2Name[i];
		for (iset=mNeighborCur[i].begin(); iset!=mNeighborCur[i].end(); iset++)
		{
			L_subGraph.mNeighborOrg[i].insert(*iset);
			L_subGraph.mNeighborCur[i].insert(*iset);
		}
	}
	L_subGraph.mVertexNo = mVertexNo;
	//cout<<"\n========\n";
	//L_subGraph.printGraph();
	return L_subGraph;
}

void BiGraph_ME::delete_nodes(set<int> p_nodes)
{
	set<int>::iterator iset,iset2,iset3;
	for (iset=p_nodes.begin(); iset != p_nodes.end(); iset++)
	{
		mVertex.erase(*iset);
	}
	for (iset=p_nodes.begin(); iset != p_nodes.end(); iset++)
	{
		for (iset2 = mNeighborCur[*iset].begin(); iset2 != mNeighborCur[*iset].end(); iset2++)
		{
			iset3 = mVertex.find(*iset2);
			if (iset3 != mVertex.end())
			{
				mNeighborCur[*iset2].erase(*iset);
			}
		}
	}
}

void BiGraph_ME::add_nodes(set<int> p_nodes)
{
	set<int>::iterator iset,iset2,iset3;
	for (iset=p_nodes.begin(); iset != p_nodes.end(); iset++)
	{
		mVertex.insert(*iset);
	}
	for (iset=p_nodes.begin(); iset != p_nodes.end(); iset++)
	{
		for (iset2 = mNeighborCur[*iset].begin(); iset2 != mNeighborCur[*iset].end(); iset2++)
		{
			iset3 = mVertex.find(*iset2);
			if (iset3 != mVertex.end())
			{
				mNeighborCur[*iset2].insert(*iset);
				mNeighborCur[*iset].insert(*iset2);
			}
		}
	}
}

list<BiGraph_ME> BiGraph_ME::connected_components()
{
	list<BiGraph_ME> L_rets;
	int tempStatus[maxGraphSize];
	set<int>::iterator iset;
	for (int i = 0; i<mVertexNo; i++)
	{
		iset = mVertex.find(i);
		if (iset != mVertex.end())
		{
			tempStatus[i] = 1;
		}
		else
		{
			tempStatus[i] = -1;
		}
	}

	for (int i = 0; i<mVertexNo; i++)
	{
		if (tempStatus[i]>0)
		{
			set<int> t_nodes,nei_old,nei_new;
			set<int>::iterator inei_old,inei_new;
			nei_old.insert(i);
			while (nei_old.size()>0)
			{
				for (inei_old = nei_old.begin(); inei_old != nei_old.end(); inei_old++)
				{
					tempStatus[*inei_old] = -1;
					t_nodes.insert(*inei_old);
					for (inei_new = mNeighborCur[*inei_old].begin(); inei_new != mNeighborCur[*inei_old].end(); inei_new++)
					{
						if (tempStatus[*inei_new]>0)
						{
							nei_new.insert(*inei_new);
						}
					}
				}
				nei_old.clear();
				for (inei_new=nei_new.begin(); inei_new!=nei_new.end(); inei_new++)
				{
					nei_old.insert(*inei_new);
				}
				nei_new.clear();
			}
			BiGraph_ME tGraph = subGraph(t_nodes);
			//cout<<"\n========+++\n";
			//tGraph.printGraph();
			L_rets.push_back(tGraph);
		}
	}
	/*
	list<BiGraph_ME>::iterator iret;
	for (iret=L_rets.begin(); iret!=L_rets.end(); iret++)
	{
		cout<<"\n-----comp:";
		(*iret).printGraph();
	}*/
	return L_rets;
}


void BiGraph_ME::printGraph()
{
	set<int>::iterator iset;
	int i;
	for (iset = mVertex.begin(); iset != mVertex.end(); iset++)
	{
		i = *iset;
		set<int>::iterator inei;
		cout<<"\n--"<<mVertexID2Name[i]<<"|"<<mWeight[i]<<": ";
		for (inei=mNeighborCur[i].begin(); inei!=mNeighborCur[i].end(); inei++)
		{
			cout<<mVertexID2Name[*inei]<<"; ";
		}
	}
}

void BiGraph_ME::printSolution(ME_mutation p_solu)
{
	cout<<"Mutation: ";
	for (int i=0; i<p_solu.size; i++)
	{
		cout<<mVertexID2Name[p_solu.mutation[i]]<<"; ";
	}
	cout<<"\nWeight: "<<p_solu.weight;
	cout<<"\nSize: "<<p_solu.size;
	cout<<"\nCoverNo: "<<p_solu.coverNo<<"/"<<mTumorNo<<"\n\n";
}

void BiGraph_ME::printSolution_gene(ME_mutation p_solu)
{
	cout<<"Mutation: ";
	for (int i=0; i<p_solu.size; i++)
	{
		cout<<mVertexID2Name[p_solu.mutation[i]]<<"; ";
	}
	//cout<<"\nWeight: "<<p_solu.weight;
	//cout<<"\nSize: "<<p_solu.size;
	//cout<<"\nCoverNo: "<<p_solu.coverNo<<"/"<<mTumorNo<<"\n\n";
}


ME_mutation BiGraph_ME::WMEM_cover_2()
{
	tempLevel += 1;
	ME_mutation solution;
	if (mVertex.size()==0)
	{
		tempLevel -= 1;
		return solution;
	}
	list<BiGraph_ME> L_comp = connected_components();
	//int tp = 1;
	//if (tp<0)
	if (L_comp.size()>1)
	{
		list<BiGraph_ME>::iterator icomp;
		for (icomp=L_comp.begin(); icomp!=L_comp.end(); icomp++)
		{
			BiGraph_ME sGraph(*icomp);
			//cout<<"\n2==="<<L_comp.size();
			//sGraph.printGraph();
			ME_mutation sSolution = sGraph.WMEM_cover_2();
			solution.addMutation(sSolution);
		}
		return solution;
	}
	else
	{
		int midx;
		set<int> lset1;
		set<int>::iterator iset1;
		midx = findMidNode4Path();
		//cout<<"\n***mid="<<midx;
		lset1.insert(midx);
		delete_nodes(lset1);
		//cout<<"\n1**----- "<<tempLevel;
		//printGraph();

		ME_mutation solution1 = WMEM_cover_2();
		add_nodes(lset1);
		//cout<<"\n2**-----"<<tempLevel;
		//printGraph();
		for (iset1 = mNeighborCur[midx].begin(); iset1 != mNeighborCur[midx].end(); iset1++)
		{
			lset1.insert(*iset1);
		}
		delete_nodes(lset1);
		//cout<<"\n3**-----"<<tempLevel;
		//printGraph();

		ME_mutation solution2 = WMEM_cover_2();
		add_nodes(lset1);
		//cout<<"\n4**-----"<<tempLevel;
		//printGraph();
		solution2.addMutation(midx,mWeight[midx],mCoverTumorNO[midx]);
		tempLevel -= 1;

		if (solution1<solution2)
		{
			return solution1;
		}
		else
		{
			return solution2;
		}
	}
}



ME_mutation BiGraph_ME::WMEM_cover_3()
{
	tempLevel += 1;
	ME_mutation solution;
	if (mVertex.size()==0)
	{
		tempLevel -= 1;
		return solution;
	}
	list<BiGraph_ME> L_comp = connected_components();
	//int tp = 1;
	//if (tp<0)
	if (L_comp.size()>1)
	{
		list<BiGraph_ME>::iterator icomp;
		for (icomp=L_comp.begin(); icomp!=L_comp.end(); icomp++)
		{
			BiGraph_ME sGraph(*icomp);
			//cout<<"\n3==="<<L_comp.size();
			//sGraph.printGraph();
			ME_mutation sSolution = sGraph.WMEM_cover_3();
			solution.addMutation(sSolution);
		}
		return solution;
	}
	else
	{
		int midx,midx1;
		set<int> lset1;
		set<int>::iterator iset1;
		midx1 = findNodeMaxDegree();
		//cout<<"\n***max= "<<midx1<<"; "<<mNeighborCur[midx1].size()<<"\n";
		if (mNeighborCur[midx1].size()<=2)
		{
			ME_mutation solution0 = WMEM_cover_2();
			return solution0;
		}
		else
		{
			midx = findKeyNode3Degree();
			lset1.insert(midx);
			delete_nodes(lset1);
			//cout<<"\n1**----- "<<tempLevel;
			//printGraph();

			ME_mutation solution1 = WMEM_cover_3();
			add_nodes(lset1);
			//cout<<"\n2**-----"<<tempLevel;
			//printGraph();
			for (iset1 = mNeighborCur[midx].begin(); iset1 != mNeighborCur[midx].end(); iset1++)
			{
				lset1.insert(*iset1);
			}
			delete_nodes(lset1);
			//cout<<"\n3**-----"<<tempLevel;
			//printGraph();

			ME_mutation solution2 = WMEM_cover_3();
			add_nodes(lset1);
			//cout<<"\n4**-----"<<tempLevel;
			//printGraph();
			solution2.addMutation(midx,mWeight[midx],mCoverTumorNO[midx]);
			tempLevel -= 1;

			if (solution1<solution2)
			{
				return solution1;
			}
			else
			{
				return solution2;
			}
		}
	}
}

ME_mutation BiGraph_ME::WMEM_cover_main()
{
	tempLevel += 1;
	ME_mutation solution;
	if (mVertex.size()==0)
	{
		tempLevel -= 1;
		return solution;
	}
	list<BiGraph_ME> L_comp = connected_components();
	//int tp = 1;
	//if (tp<0)
	if (L_comp.size()>1)
	{
		list<BiGraph_ME>::iterator icomp;
		for (icomp=L_comp.begin(); icomp!=L_comp.end(); icomp++)
		{
			BiGraph_ME sGraph(*icomp);
			//cout<<"\nm==="<<L_comp.size();
			//sGraph.printGraph();
			ME_mutation sSolution = sGraph.WMEM_cover_main();
			solution.addMutation(sSolution);
		}
		return solution;
	}
	else
	{
		int midx;
		set<int> lset1;
		set<int>::iterator iset1;
		midx = findNodeMaxDegree();
		//cout<<"\n***max= "<<midx<<"; "<<mNeighborCur[midx].size()<<"\n";
		if (mNeighborCur[midx].size()<=3)
		{
			ME_mutation solution0 = WMEM_cover_3();
			return solution0;
		}
		else
		{
			lset1.insert(midx);
			delete_nodes(lset1);
			//cout<<"\n1**----- "<<tempLevel;
			//printGraph();

			ME_mutation solution1 = WMEM_cover_main();
			add_nodes(lset1);
			//cout<<"\n2**-----"<<tempLevel;
			//printGraph();
			for (iset1 = mNeighborCur[midx].begin(); iset1 != mNeighborCur[midx].end(); iset1++)
			{
				lset1.insert(*iset1);
			}
			delete_nodes(lset1);
			//cout<<"\n3**-----"<<tempLevel;
			//printGraph();

			ME_mutation solution2 = WMEM_cover_main();
			add_nodes(lset1);
			//cout<<"\n4**-----"<<tempLevel;
			//printGraph();
			solution2.addMutation(midx,mWeight[midx],mCoverTumorNO[midx]);
			tempLevel -= 1;

			if (solution1<solution2)
			{
				return solution1;
			}
			else
			{
				return solution2;
			}
		}
	}
}