--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/defical-c/src/graphmagic.cpp	Fri Apr 02 23:11:57 2010 +0700
@@ -0,0 +1,433 @@
+#include "graphmagic.h"
+
+semtd::semtd(){}
+
+semtd::semtd(uint32_t graphType,uint32_t NumVer, uint32_t numDef)
+{
+	if(NumVer>3){
+		this->NumVer=NumVer;
+		this->numDef=numDef;
+		this->graphType=graphType;
+		this->TotalVer=NumVer+numDef;
+		this->numEdges=0;
+		this->isSureFail=false;
+		this->edgeLabelAbsoluteMax=this->TotalVer*2-1;
+		//initialize graph array
+		//this->theGraph.resize(this->NumVer+1,vector<bool>(this->NumVer+1,false));
+		for (int i=0; i<1000;i++)
+		{
+			for (int j=0;j<1000;j++)
+			{
+				this->theGraph[i][j]=false;
+			}
+		}
+		draw(this->graphType,1,this->NumVer);
+		resetLabels(0);
+	}
+}
+
+void semtd::draw(uint32_t drawType,uint32_t start,uint32_t end)
+{
+	switch(drawType)
+	{
+	case 0:
+		{
+			for (uint32_t i=start;i<end;i++)
+				connectVertices(i,i+1);
+			break;
+		}
+	case 1:
+		{
+			draw(0,start,end);
+			connectVertices(start,end);
+			break;
+		}
+	case 3:
+		{
+			draw(1,start+1,end);
+			draw(2,start+1,end,start);
+			break;
+		}
+	case 4:
+		{
+			draw(0,start+1,end);
+			draw(2,start+1,end,start);
+			break;
+		}
+	case 5:
+		{
+			draw(4,start+1,end);
+			draw(2,start+2,end,start);
+			break;
+		}
+	}
+}
+
+void semtd::draw(uint32_t drawType,uint32_t start,uint32_t end, uint32_t extra)
+{
+	switch(drawType)
+	{
+	case 2:
+		{
+			for (uint32_t i=start;i<=end;i++)
+				connectVertices(i,extra);
+			break;
+		}
+	}
+}
+
+inline void semtd::connectVertices(uint32_t a,uint32_t b)
+{
+	if(!this->theGraph[a][b])
+	{
+		this->theGraph[a][b]=this->theGraph[b][a]=true;
+		this->numEdges++;
+	}
+}
+
+void semtd::resetLabels(uint32_t mode)
+{
+	if(mode==0)
+	{
+		this->VerLabels.clear();
+		this->VerLabels.resize(this->NumVer+1,0);
+	}
+	this->edgeLabels.clear();
+	this->edgeLabels.resize(NumVer+1,vector<uint32_t>(NumVer+1,0));
+	this->isQuickMode=false;
+	this->scoreCache=-1;
+	//uint32_t *edgeLabelsUsedPtr;
+	//edgeLabelsUsedPtr=(uint32_t*)malloc(this->edgeLabelAbsoluteMax+1*sizeof(uint32_t));
+	this->edgeLabelsUsed.clear();
+	this->edgeLabelsUsed.resize(this->edgeLabelAbsoluteMax+1,0);
+	this->edgeLabelMax=0;this->edgeLabelMin=this->edgeLabelAbsoluteMax;
+	refreshEdgeLabelsMinMax();
+}
+
+void semtd::refreshEdgeLabelsMinMax()
+{
+	uint32_t i;
+	for (i = 1; i <= this->edgeLabelAbsoluteMax; i++)
+	{
+		if (this->edgeLabelsUsed[i] > 0)
+		{
+			this->edgeLabelMin = i;
+			break;
+		}
+	}
+	for (int32_t x = this->edgeLabelAbsoluteMax; x >= 0; x--)
+	{
+		if (this->edgeLabelsUsed[x] > 0)
+		{
+			this->edgeLabelMax = x;
+			break;
+		}
+	}
+}
+
+inline uint32_t semtd::edgeLabelRange()
+{
+	return this->edgeLabelMax-this->edgeLabelMin+1;
+}
+
+void semtd::setEdgeLabels(uint32_t verPos)
+{
+	uint32_t newLabel,i;
+	for (i = 1; i <= this->NumVer; i++)
+	{
+		if (this->VerLabels[i] > 0 && this->theGraph[verPos][i] && i != verPos)
+		{
+			newLabel = this->VerLabels[verPos] + this->VerLabels[i];
+			this->edgeLabels[i][verPos] = this->edgeLabels[i][verPos] = newLabel;
+			this->edgeLabelsUsed[newLabel]++;
+			if (this->edgeLabelsUsed[newLabel] != 1)
+				this->isSureFail = true;
+		}
+	}
+	refreshEdgeLabelsMinMax();
+}
+
+void semtd::removeEdgeLabels(uint32_t verPos)
+{
+	uint32_t i;
+	for (i = 1; i <= this->NumVer; i++)
+	{
+		if (this->VerLabels[i] > 0 && this->theGraph[verPos][i] && i != verPos)
+		{
+			int oldLabel = this->edgeLabels[i][verPos];
+			this->edgeLabelsUsed[oldLabel]--;
+			this->edgeLabels[i][verPos] = this->edgeLabels[verPos][i] = 0;
+		}
+	}
+	refreshEdgeLabelsMinMax();
+}
+
+void semtd::SetVerLabel(uint32_t verPos,uint32_t verLabel)
+{
+	if (this->VerLabels[verPos] > 0) { RemoveVerLabel(verPos); }
+	this->VerLabels[verPos] = verLabel;
+	setEdgeLabels(verPos);
+}
+
+void semtd::RemoveVerLabel(uint32_t verPos)
+{
+	if (this->VerLabels[verPos] > 0)
+	{
+		this->VerLabels[verPos] = 0;
+		removeEdgeLabels(verPos);
+	}
+}
+
+
+
+bool semtd::IsValidToLabel(uint32_t verPos,uint32_t verLabel)
+{
+	uint32_t i,tempLabel;
+	//uint32_t tempMax=this->edgeLabelMax;
+	//uint32_t tempMin=this->edgeLabelMin;
+	for (i = 1; i <= this->NumVer; i++)
+	{
+		tempLabel=this->VerLabels[i] + verLabel;
+		if (i != verPos &&
+			this->theGraph[i][verPos] &&
+			this->VerLabels[i] > 0 &&
+			this->edgeLabelsUsed[tempLabel] == 1)
+		{
+			return false;
+		}
+		/*if(tempLabel>tempMax)
+		tempMax=tempLabel;
+		if(tempLabel<tempMin)
+		tempMin=tempLabel;
+		if(!isValidRange(tempMin,tempMax))
+		return false;*/
+	}
+	return true;
+}
+
+bool semtd::isValidRange(uint32_t min,uint32_t max)
+{
+	uint32_t delta=1+max-min;
+	if(delta<=this->numEdges)
+		return true;
+	return false;
+}
+
+double semtd::SemtScore()
+{
+	//TODO
+	return 0;
+}
+
+void semtd::FixLabel()
+{
+	//TODO
+}
+
+void semtd::SwapLabel()
+{
+	//TODO
+}
+
+string semtd::Print(uint32_t withDual)
+{
+	uint32_t i,j;
+	string ret = "";
+	string n = "\n";
+	bool dualRun=false;
+	bool keepPrinting=true;
+	while (keepPrinting)
+	{
+		ret+="graph: ";
+		switch(this->graphType)
+		{
+		case 3:
+			{
+				ret+="wheel";
+				break;
+			}
+		case 4:
+			{
+				ret+="fan";
+				break;
+			}
+		case 5:
+			{
+				ret+="doublefan";
+				break;
+			}
+		default:
+			{
+				ret+="unknown";
+				break;
+			}
+		}
+		ret+=" | edges: "+uint32_t_to_str(this->numEdges)+" | vertices: " + uint32_t_to_str(this->NumVer)+" | deficiencies: " + uint32_t_to_str(this->numDef) + " | ";
+		uint32_t edgeweight=0,k,edgelabel=0;
+		for (i=1;i<=this->edgeLabelAbsoluteMax;i++)
+		{
+			if(this->edgeLabelsUsed[i])
+			{
+				edgeweight=i;
+				edgelabel=this->numEdges+this->TotalVer;
+				break;
+			}
+		}
+		if(dualRun)
+		{
+			edgeweight=2*(this->TotalVer)+2-edgeweight;
+			edgelabel=2*this->TotalVer+this->numEdges+1-edgelabel;
+		}
+		k=edgeweight+edgelabel;
+		ret+="mnum: "+uint32_t_to_str(k)+" | ";
+		for (i = 1; i <= this->NumVer; i++)
+		{
+			uint32_t theLabel;
+			if(dualRun)
+				theLabel=this->TotalVer+1-this->VerLabels[i];
+			else
+				theLabel=this->VerLabels[i];
+			if(i==1 && this->graphType==3)
+				ret+="c: " + uint32_t_to_str(theLabel) +" | l: ";
+			else if(i==1 && this->graphType==4)
+				ret+="c: " + uint32_t_to_str(theLabel) +" | p: ";
+			else if(i==1 && this->graphType==5)
+				ret+="c: " + uint32_t_to_str(theLabel) + ",";
+			else if(i==2 && this->graphType==5)
+				ret+=uint32_t_to_str(theLabel) + " | p: ";
+			else if(i==this->NumVer)
+				ret+=uint32_t_to_str(theLabel) + " | def: ";
+			else
+				ret+=uint32_t_to_str(theLabel)+",";
+		}
+		if(this->numDef>0)
+		{
+			vector<bool> usedLabels (this->TotalVer+1,false);
+			for(i=1;i<=this->NumVer;i++)
+				usedLabels[this->VerLabels[i]]=true;
+			j=0;
+			for(i=1;i<=this->TotalVer;i++)
+			{
+				uint32_t theLabel;
+				if(!usedLabels[i])
+				{
+					if(dualRun)
+						theLabel=this->TotalVer+1-i;
+					else
+						theLabel=i;
+					if(j==this->numDef-1)
+					{
+						if(dualRun)
+							ret+=uint32_t_to_str(theLabel)+" (dual)"+n;
+						else
+							ret+=uint32_t_to_str(theLabel)+n;
+						j++;
+					}
+					else
+					{
+						ret+=uint32_t_to_str(theLabel)+",";
+						j++;
+					}
+				}
+			}
+		}
+		/*
+		ret += n+"Deficiency: " + uint32_t_to_str(this->numDef);
+		ret += n+"GraphViz code: " + n + "----------------------------------";
+		//tempstr1<<this->graphType; //TODO: graphtype is now integer instead of string. create a convert method
+		ret += n+"graph " + uint32_t_to_str(this->graphType)+ "{";
+		ret += n+"graph[bgcolor=\"transparent\"]";
+		ret += n+"node [fontname=\"Bitstream Vera Sans\", fontsize=\"22.00\", shape=circle, style=\"bold,filled\" fillcolor=white];";
+		ret += n+"edge [style=bold];";
+		ret += n+" ";
+		for (i = 1; i <= this->TotalVer; i++)
+		{
+		ret += uint32_t_to_str(i) + ";";
+		}
+		for (i = 1; i <= this->NumVer; i++)
+		{
+		for (j = i + 1; j <= this->NumVer; j++)
+		{
+		if (this->theGraph[i][j])
+		{
+		uint32_t theLabel;
+		if(dualRun)
+		theLabel=this->TotalVer+1-this->VerLabels[i];
+		else
+		theLabel=this->VerLabels[i];
+		ret += n+uint32_t_to_str(this->VerLabels[i])+ " -- " + uint32_t_to_str(theLabel)+ ";";
+		}
+		}
+		}
+		ret += n+"}";
+		ret += n+"----------------------------------" + n + "End GraphViz code";*/
+		if(withDual==1)
+		{
+			withDual=0;
+			dualRun=true;
+		}else
+			keepPrinting=false;
+	}
+	return ret;
+}
+
+
+
+bool semtd::IsSemt()
+{
+	uint32_t i;
+	if (this->isSureFail) { return false; }
+	else
+	{
+		if (edgeLabelRange() == numEdges)
+		{
+			uint32_t edgeLabelMin = this->edgeLabelMin;
+			uint32_t edgeLabelMax = this->edgeLabelMax;
+			for (i = edgeLabelMin; i <= edgeLabelMax; i++)
+			{
+				if (this->edgeLabelsUsed[i] != 1)
+				{
+					return false;
+				}
+			}
+			return true;
+		}
+	}
+	return false;
+}
+
+uint32_t semtd::MinDef()
+{
+	uint32_t ret=0;
+	switch(this->graphType)
+	{
+	case 3:
+		switch (this->NumVer)
+		{
+		case 3:
+		case 4:
+		case 6:
+		case 7:
+			{
+				ret = 1;
+				break;
+			}
+		default:
+			{
+				ret = 2;
+				break;
+			}
+		}
+	case 4:
+		{
+			ret=1;
+			break;
+		}
+	case 5:
+		{
+			ret = (this->NumVer - 3) / 2;
+			break;
+		}
+	}
+	return ret;
+}