DFS---another practical approach

A.First Edition

This is another more practical approach for searching problem---depth-first-search which uses almost constant size

of memory. However, DFS may not give you the best solution and even cannot guarantee you a solution. Last year, I 

wrote DFS once with array, now it is linked list which is my favourite.

There are some similar functions from BFS. I clear up memory when a node is evaluated and the result is recorded.

B.The problem

How many ways are there to travel in xyzw space from the origin (0,0,0,0) to the point (4,3,5,4) by taking steps 

one unit in the positive x, positive y, positive z, or positive w direction?

No matter how complicated a problem may become, we can divide and conquer it by counting! And depth-first-search

is one of the simplest way to do it.

As DFS uses very small memory, I don't need to reduce the size of problem, but the program wrote into my disk with 

a file size of more than 800M until my disk runs out of free space. Then I change the program not to output all 

outcomes, instead only the total number of solutions. However, it runs more than one hour and still there is no

result!

D.The major functions

1. virtual bool validateOption(int sonData);

This is the place where user-defined methods are implemented to determine if the data (integer)	will be verified 

to be able to be added.

2. bool DFS::doGenerate()

This is user-defined way that cases are generated. Method validateOptions will be combined with it to determine 

which cases should be added.

3. void DFS::onLeave()

This method allows you to do specific job when you visit all leaf points which is a solution such as delete node. 

#include <iostream>

using namespace std;

const int MaxSonCount=8;

const int MaxLevel =20;

const int MaxOptions = 10;

enum AxisName
{X, Y, Z, W};

int limit[4] = {4,3,5,4};

char* directionString[4] = {"X", "Y", "Z", "W"};

int axis[4] = {X,Y,Z,W};

int number=0;

class DFS
{
private:
	static DFS root;
	static bool findAll;
	static int level;
	static int optionArray[MaxOptions];
	static int optionCount;
	static int maxLevel;
	int depth;
	DFS* parent;
	DFS* sonArray[MaxSonCount];
	int data;
	int sonCount;
	int sonIndex;
	void addSon(int sonData);
	DFS* findBrother();
	DFS* findUncle();
	bool hasBrother();
	DFS* nextBrother();
	void initialize();
	bool touchDown();
	DFS* generate();
	void setMaxLevel(int max) { maxLevel = max;}

protected:
	bool doGenerate();
	virtual bool validateOption(int sonData);	
	virtual void onLeave();
	bool evaluate();
	void collectResult();
public:
	void setOptions(int* array, int size);
	void beginCount(int max, bool findall=false);
};

bool DFS::findAll = false;
int DFS::maxLevel = 0;
int DFS::optionCount = 0;
int DFS::optionArray[MaxOptions] = {0};
int DFS::level = 0;
DFS DFS::root;


int main()
{
	DFS R;
	R.setOptions(axis, 4);
	R.beginCount(16, true);
	cout<<"Number is"<<number<<endl;

	return 0;
}

//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;
	delete ptr;
}

void DFS::collectResult()
{
	int temp[MaxLevel] = {0};
	DFS* ptr = this;

	while (ptr->parent!=NULL)
	{
		temp[ptr->depth-1] = ptr->data;
		ptr = ptr->parent;
	}
	cout<<"The route is:";
	for (int i=0; i<depth; i++)
	{
		cout<<directionString[temp[i]]<<", ";
	}
	cout<<"It is number:"<<number++;
	cout<<endl;
}

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

bool DFS::doGenerate()
{
	bool result = false;
	for (int i=0; i< optionCount; i++)
	{
		if (validateOption(optionArray[i]))
		{
			addSon(optionArray[i]);
			result = true;
		
		}
	}
	if (result)
	{
		level++;
	}
	return result;
}

bool DFS::validateOption(int sonData)
{
	int counter[4]={0}; //count all axis advances
	DFS* ptr= this;

	while (ptr->parent!=NULL)
	{
		counter[ptr->data]++; //data is axis
		ptr = ptr->parent;
	}

	return counter[sonData]<limit[sonData];
}

DFS* DFS::findBrother()
{
	DFS* ptr= this;
	DFS* dummy=ptr;
	while (!(ptr->hasBrother()))
	{
		dummy = ptr; //keep the clue
		ptr = ptr->parent;
		level--;
		if (dummy!=&root)
		{
			dummy->onLeave(); //clear
		}
		if (ptr==NULL)
		{
			return NULL;
		}
	}
	dummy = ptr;  //keep clue
	ptr = ptr->nextBrother();
	dummy->onLeave(); //clear 
	return ptr;
}

void DFS::beginCount(int max, bool findall)
{
	DFS* ptr = &root;
	setMaxLevel(max);
	findAll = findall; //setup if want all result
	initialize();
	while (true)
	{		
		ptr = ptr->generate();
		if (ptr==NULL)
		{
			if (number==0)
			{
				cout<<"No solution!";
			}
			break;
		}
		if (ptr->evaluate())
		{
			ptr->collectResult();
			if (!findAll)
			{
				break;
			}
		}
		ptr = ptr->findBrother();
		if (ptr==NULL)
		{
		
			if (number==0)
			{
				cout<<"No solution!";
			}
			break;
		}
	}
}
		
DFS* DFS::generate()
{
	DFS* ptr= this;
	while(!ptr->touchDown())
	{
		if (!ptr->doGenerate())
		{
			ptr=ptr->findBrother();
			if (ptr==NULL)
			{
				break;
			}
		}
		else
		{
			ptr = ptr->sonArray[0];
		}
	}
	return ptr;
}



void DFS::addSon(int sonData)
{	
	if (sonCount+1<MaxSonCount)
	{
		DFS* ptr = new DFS;
		ptr->data = sonData;
		ptr->sonCount = 0;
		ptr->parent = this;
		ptr->depth = depth+1;
		sonArray[sonCount] = ptr;		
		ptr->sonIndex = sonCount;
		sonCount++;
	}
	else
	{
		cout<<"Exceed max of sons!";
	}
}

void DFS::initialize()
{
	root.depth = 0;
	root.sonCount = 0;
	root.sonIndex = -1;
	root.parent = NULL;
	root.data = 0;
	level = 0;
}

bool DFS::hasBrother()
{
	if (parent!=NULL)
	{
		if (parent->sonCount > sonIndex+1)//has little brother
		{
			return true;
		}
	}
	return false;
}

DFS* DFS::nextBrother()
{
	if (parent!=NULL)
	{
		if (parent->sonCount > sonIndex+1)//has little brother
		{
			return parent->sonArray[sonIndex+1]; //next little brother
		}
	}
	return NULL;
}

The result is 50450400