--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/defical-c/src/backtrack.cpp	Fri Apr 02 23:11:57 2010 +0700
@@ -0,0 +1,121 @@
+#include "backtrack.h"
+
+namespace bt{
+	backtrack::backtrack() {}
+
+	backtrack::backtrack(uint32_t graphType,uint32_t numVer,uint32_t numDef,uint32_t firstLabel,bool isAll)
+	{
+		this->theGraph=new semtd(graphType,numVer,numDef);
+		this->graphType=graphType;
+		this->usedLabels.resize(this->theGraph->TotalVer+1,false);
+		this->IsSemt=false;
+		setLabel(1,firstLabel);
+		this->firstLabel=firstLabel;
+		this->Result="";
+		this->RecurseAll=isAll;
+		this->pathLabel=this->startPath=this->endPath=0;
+		switch(graphType)
+		{
+		case 4:
+			{
+				this->startPath=2;
+				this->endPath=this->theGraph->NumVer;
+				break;
+			}
+		case 3:
+		case 5:
+			{
+				this->startPath=3;
+				this->endPath=this->theGraph->NumVer;
+				break;
+			}
+		}
+	}
+
+	inline void backtrack::setLabel(uint32_t verPos,uint32_t verLabel)
+	{
+		this->usedLabels[verLabel]=true;
+		this->theGraph->SetVerLabel(verPos,verLabel);
+	}
+
+	inline void backtrack::removeLabel(uint32_t verPos)
+	{
+		this->usedLabels[this->theGraph->VerLabels[verPos]]=false;
+		this->theGraph->RemoveVerLabel(verPos);
+	}
+
+	void backtrack::walk(uint32_t currentLevel)
+	{
+		if (this->IsProcessing)
+		{
+			if (currentLevel > this->theGraph->NumVer)
+			{
+				if (this->theGraph->IsSemt())
+				{
+					if(!this->RecurseAll)
+					{
+						this->IsProcessing = false;
+					}
+					this->Result += this->theGraph->Print(1);
+					//setDual();
+					//this->Result+="\nDual:\n"+this->theGraph->Print()+"\n";
+					//setDual(); //undo the damage
+					this->IsSemt = true;
+				}
+				removeLabel(currentLevel - 1);
+			}
+			else
+			{
+				//List<int> availableLabels = new List<int>();
+				vector<uint32_t> availableLabels;
+				uint32_t start=1;
+				uint32_t end=this->theGraph->TotalVer;
+				if(currentLevel==2 && this->firstLabel != this->theGraph->TotalVer)
+				{
+					if(this->graphType==3)
+						start=end; //optimization for wheel
+					else if(this->graphType==5)
+						start=this->firstLabel+1;
+				}
+				else if(this->startPath!=0)
+				{
+					if(currentLevel==this->endPath)
+						start=this->pathLabel+1; //remove possibility for reversed path labeling
+					else if(currentLevel==this->startPath && start<end)
+						end=this->theGraph->TotalVer-1; //no need to test last label as it'll be checked already on all previous cases
+				}
+				for (uint32_t i = start; i <= end; i++)
+					if (!this->usedLabels[i])
+						availableLabels.push_back(i);
+				if(availableLabels.size()>0)
+				{
+					for (int32_t x = availableLabels.size()-1; x >= 0; x--)
+					{
+						if((this->startPath!=0) && (currentLevel==this->startPath))
+							this->pathLabel=availableLabels[x];
+						if (this->theGraph->IsValidToLabel(currentLevel, availableLabels[x]))
+						{
+							setLabel(currentLevel,availableLabels[x]);
+							walk(currentLevel + 1);
+						}
+						if (!this->IsProcessing)
+							break;
+					}
+				}
+				if (currentLevel != 2) { removeLabel(currentLevel - 1); }
+			}
+		}
+	}
+	void backtrack::Walk()
+	{
+		if(this->theGraph->numDef>=this->theGraph->MinDef())
+		{
+			this->IsProcessing=true;
+			walk(2);
+		}
+		else
+		{
+			this->IsSemt=false;
+		}
+	}
+}