DFSArray

A.First Edition
This is my first edition of my DFS class implemented with an array. Or you can call it second version of standard
DFS, third version of original DFS class. 
B.The problem
Does anybody regard array has higher efficiency than linked list? Yes, I think so. Linked list is using pointer
 
to access an address then the value, or the address is used to access real value. This is typical indirect
 
addressing mode, right? However, array is simply a kind of offset from beginning address of an array. This the
 
reason why I want to re-implement my DFS class with array instead of linked list.
 
C.The idea of program
There is nothing special about this new version except that an internal static array of DFS* is used to store 
all nodes and all nodes is accessed with the index of this array. Most features of old standard DFS class were
kept. 
D.The major functions
1. void DFS::beginCount(int max, bool findall)
This major public function sets up the searching maximum depth and option if all result should be searched.
Whenever a new level of new nodes are generated, move first to the first son node and test user-defined function--
evaluate() to see if result reached. After show result, test if all result should be searched. Then test if user-
defined maximum level is reached. If yes, try next brother node, then rebound for higher level nodes. When going
upper level, delete all those visited nodes to save memory. 
2. void DFS::backTrack()
This utility function is quite useful and maybe used repeatedly in different situations. It save all data of nodes
in an internal array.
E.Further improvement
1. Are you kidding? For such a trivial program?
 
#include <iostream>

using namespace std;

const int MaxSonCount=8;

const int MaxLevel =20;

const int MaxOptions = 10;

const int MaxNodeCount = 1000;

class DFS
{
private:
	void initialize(DFS* now);
	static DFS* nodeList[MaxNodeCount];
	static bool findAll;
	static int optionArray[MaxOptions];
	static int optionCount;
	static char** nameString;
	static int solutionCount;
	static int maxLevel;
	static int domino;
	void addSon(int sonData);
	bool touchDown();
	void setMaxLevel(int max) { maxLevel = max;}
	DFS* upDate();
	bool hasBrother();
	DFS* nextBrother();
	bool generate();
	DFS* findNext();
	DFS* getNode(int theIndex){return nodeList[theIndex];}
	void putNode(int theIndex) { nodeList[theIndex] = this;}
	DFS* getParent(){return getNode(parent);}
	bool hasParent(){return parent!=-1;}
protected:
	int parent;
	int sonCount;
	int sonIndex;
	int son;
	int depth;
	int index;//index in nodeList
	int data;
	void backTrack();
	static int trackRecord[MaxLevel];
	virtual DFS* createSon();
	virtual bool validateOption(int sonData);	
	virtual void onLeave();
	virtual bool evaluate();
	virtual void collectResult();
public:
	int getSolutionCount(){ return solutionCount;}
	void setOptions(int* array, int size);
	void setNameStr(char** str){nameString = str;}
	void beginCount(int max, bool findall=false);
};

int DFS::domino = 0;
bool DFS::findAll = false;
int DFS::maxLevel = 0;
int DFS::optionArray[MaxOptions] = {0};
char** DFS::nameString=NULL;
int DFS::solutionCount = 0;
int DFS::optionCount = 0;
DFS* DFS::nodeList[MaxNodeCount] = {NULL};
int DFS::trackRecord[MaxLevel]= {0};


enum AxixType
	{X,Y,Z};
char* directionString[3] = {"X","Y","Z"};
int restrict[3] = {3, 2, 4};
int axis[3] = {X,Y,Z};

class SpaceSpider: public DFS
{
protected:
	virtual DFS* createSon();
	virtual bool validateOption(int sonData);	
//	virtual void onLeave();
	virtual bool evaluate();
//	virtual void collectResult();

};


int main()
{
	SpaceSpider R;
	R.setOptions(axis, 3);
	R.setNameStr(directionString);
	R.beginCount(9, true);
	cout<<"Total number is "<<R.getSolutionCount()<<endl;

	return 0;
}





DFS* SpaceSpider::createSon()
{
	DFS* ptr= new SpaceSpider;
	return ptr;
}

bool SpaceSpider::validateOption(int sonData)
{
	int temp[3] = {0};
	backTrack();
	temp[sonData]++;
	for (int i=0; i<depth; i++)
	{
		temp[trackRecord[i]]++;
		if (temp[trackRecord[i]]>restrict[trackRecord[i]])
		{
			return false;
		}
	}
	return true;
}

bool SpaceSpider::evaluate()
{
	return depth==9;
}

//I don't know what extra work to be for the time being
bool DFS::evaluate()
{
	return true;
}

bool DFS::touchDown()
{
	return depth==maxLevel;
}

void DFS::onLeave()
{
	DFS* ptr =this;
	int end = ptr->index;
	int start;
	if (ptr->hasParent())
	{
		start = ptr->getParent()->son;
		for (int i= start; i<=end;i++)
		{
			ptr = getNode(i);
			delete ptr;
			nodeList[i] = NULL;
		}
		domino = domino + start - end -1;
	}	
}

void DFS::backTrack()
{
	DFS* ptr = this;

	while (ptr->hasParent())
	{
		trackRecord[ptr->depth-1] = ptr->data;
		ptr = ptr->getParent();
	}
}


//a stack
void DFS::collectResult()
{
	backTrack();
	cout<<"The route is:";
	for (int i=0; i<depth; i++)
	{
		cout<<nameString[trackRecord[i]]<<", ";
	}
	cout<<"It is number:"<<solutionCount++;
	cout<<endl;
}

void DFS::setOptions(int *array, int size)
{
	optionCount = size;
	for (int i=0; i<size; i++)
	{
		optionArray[i] = *(array+i);
	}
}


//this is supposed to be overrided by user
bool DFS::validateOption(int sonData)
{
	return true;
}

void DFS::beginCount(int max, bool findall)
{
	DFS* ptr = this;
	setMaxLevel(max);
	findAll = findall; //setup if want all result
	initialize(this);

	while (ptr!=NULL)
	{
		if (ptr->generate())
		{
			ptr = ptr->upDate();//move to first son
			if (ptr->evaluate())
			{
				ptr->collectResult();
				if (!findAll)
				{
					break;
				}
				else
				{
					ptr = ptr->findNext();
				}
			}
			else
			{
				if (ptr->touchDown())
				{
					ptr=ptr->findNext();
				}
			}
		}
		else
		{
			ptr = ptr->findNext();
		}
	}
	if (solutionCount==0)
	{
		cout<<"no solution!";
	}		
}
	
DFS* DFS::findNext()
{
	DFS* ptr = this;
	DFS* dummy;
	while (ptr!=NULL)
	{
		if (ptr->hasBrother())
		{
			return getNode(ptr->index+1);//next brother			
		}
		else
		{
			if (ptr->hasParent())
			{
				dummy = ptr;
				ptr = ptr->getParent(); //if 
				dummy->onLeave(); //only clear when go up one level
			}
			else
			{
				break;
			}
		}
	}
	return NULL;
}

bool DFS::generate()
{
	DFS* ptr= this;
	bool result = false;
	//this is preorder and I don't bother to 
	//give choices for midorder or postorder
	for (int i=0; i< optionCount; i++)
	{
		if (validateOption(optionArray[i]))
		{
			addSon(optionArray[i]);
			result = true;		
		}
	}
	return result;
}

DFS* DFS::upDate()
{
	//return first son
	return getNode(son);
}

//must be override by user when inherited
DFS* DFS::createSon()
{
	DFS* ptr = new DFS;
	return ptr;
}

void DFS::addSon(int sonData)
{	
	if (sonCount+1<MaxSonCount)
	{
		if (domino==MaxNodeCount)
		{
			cout<<"Exceeds limit of node list"<<endl;
			return;
		}
		DFS* ptr = createSon();
		ptr->index = domino;//
		ptr->putNode(domino);		

		if (sonCount==0)//if it is the first son
		{
			son = domino;//first son 
		}
		domino++;
		ptr->data = sonData;
		ptr->sonCount = 0;
		ptr->son = -1;//temporarily
		ptr->parent = index;
		ptr->depth = depth+1;
		ptr->sonIndex = sonCount;
		sonCount++;
	}
	else
	{
		cout<<"Exceed max of sons!";
	}
}

void DFS::initialize(DFS* now)
{
	now->index =0;	
	now->depth = 0;
	now->sonCount = 0;
	now->sonIndex = -1;
	now->parent = -1;
	now->data = 0;
	now->putNode(0); //put in list
	domino++;
}

bool DFS::hasBrother()
{
	if (hasParent())
	{
		if (getParent()->sonCount > sonIndex+1)//has little brother
		{
			return true;
		}
	}
	return false;
}


Running result of program:
I want to test my new class, so I choose the old problem---the space spider who is crawling in 3-D for 9 steps in which it can only
go X-axis 3 steps, Y-axis 2 steps, Z-axis 4 steps. This problem has been solved before.
...
...
The route is:Z, Z, Z, X, Z, Y, X, X, Y, It is number:1227
The route is:Z, Z, Z, X, Z, Y, X, Y, X, It is number:1228
The route is:Z, Z, Z, X, Z, Y, Y, X, X, It is number:1229
The route is:Z, Z, Z, Y, X, X, X, Y, Z, It is number:1230
The route is:Z, Z, Z, Y, X, X, X, Z, Y, It is number:1231
The route is:Z, Z, Z, Y, X, X, Y, X, Z, It is number:1232
The route is:Z, Z, Z, Y, X, X, Y, Z, X, It is number:1233
The route is:Z, Z, Z, Y, X, X, Z, X, Y, It is number:1234
The route is:Z, Z, Z, Y, X, X, Z, Y, X, It is number:1235
The route is:Z, Z, Z, Y, X, Y, X, X, Z, It is number:1236
The route is:Z, Z, Z, Y, X, Y, X, Z, X, It is number:1237
The route is:Z, Z, Z, Y, X, Y, Z, X, X, It is number:1238
The route is:Z, Z, Z, Y, X, Z, X, X, Y, It is number:1239
The route is:Z, Z, Z, Y, X, Z, X, Y, X, It is number:1240
The route is:Z, Z, Z, Y, X, Z, Y, X, X, It is number:1241
The route is:Z, Z, Z, Y, Y, X, X, X, Z, It is number:1242
The route is:Z, Z, Z, Y, Y, X, X, Z, X, It is number:1243
The route is:Z, Z, Z, Y, Y, X, Z, X, X, It is number:1244
The route is:Z, Z, Z, Y, Y, Z, X, X, X, It is number:1245
The route is:Z, Z, Z, Y, Z, X, X, X, Y, It is number:1246
The route is:Z, Z, Z, Y, Z, X, X, Y, X, It is number:1247
The route is:Z, Z, Z, Y, Z, X, Y, X, X, It is number:1248
The route is:Z, Z, Z, Y, Z, Y, X, X, X, It is number:1249
The route is:Z, Z, Z, Z, X, X, X, Y, Y, It is number:1250
The route is:Z, Z, Z, Z, X, X, Y, X, Y, It is number:1251
The route is:Z, Z, Z, Z, X, X, Y, Y, X, It is number:1252
The route is:Z, Z, Z, Z, X, Y, X, X, Y, It is number:1253
The route is:Z, Z, Z, Z, X, Y, X, Y, X, It is number:1254
The route is:Z, Z, Z, Z, X, Y, Y, X, X, It is number:1255
The route is:Z, Z, Z, Z, Y, X, X, X, Y, It is number:1256
The route is:Z, Z, Z, Z, Y, X, X, Y, X, It is number:1257
The route is:Z, Z, Z, Z, Y, X, Y, X, X, It is number:1258
The route is:Z, Z, Z, Z, Y, Y, X, X, X, It is number:1259
Total number is 1260
Press any key to continue

 
	

			


                                 back.gif (341 bytes)       up.gif (335 bytes)         next.gif (337 bytes)

Hosted by www.Geocities.ws

1