DFS---Standardized
A.Second Edition
This is second edition of my DFS base class. Like BFS, I standardized all virtual method and correct a couple of
small mistakes.
How many ways are there to travel in xyzw space from the origin (0,0,0,0) to the point (3,2,3,1) 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!
There are several significant changes in new Standardized DFS class:
1. root is no longer a static object, so it is possible to be inherited by overriding virtual function "createSon".
2. MaxLevel is only a bottom line for DFS to touch down. A bug is corrected so that it will give correct result
even searching does not touch down.
3. evaluate method must be implemented by user to justify if result is what he is looking for.
4. validateOption remains same to be necessary to be implemented by user.
5. beginCount need one more parameter---nameStr, a char**. So that display method is standardize and no more
attention is needed. User simply passes the user-defined string array (char**) by second parameter in beginCount.
6. A member counter solutionCounter is used to count the number of solutions.
7. setOption still needs to be called before beginCount() to set up the options array.
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()
I made a small change in this function: a touchDown check is preceded to all option-check, because this is major
difference with BFS. User prefers to set up the maximum searching levels.
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.
4. DFS* DFS::generate()
This function is also modified as "evaluate" check becomes the only judgement for return. This makes it possible
that even searching does not reach maximum searching level, correct results still can be got as long as it justifies
"evaluate" check.
#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] = {3,2,3,1};
char* directionString[4] = {"X", "Y", "Z", "W"};
int axis[4] = {X,Y,Z,W};
class DFS
{
private:
static DFS* root;
static bool findAll;
static int level;
static int optionArray[MaxOptions];
static int optionCount;
static int maxLevel;
static char** nameString;
static int solutionCount;
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(DFS* now);
bool touchDown();
DFS* generate();
void setMaxLevel(int max) { maxLevel = max;}
bool doGenerate();
void setNameStr(char** str){nameString = str;}
protected:
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 beginCount(int max, char** str, 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 = NULL;
char** DFS::nameString=NULL;
int DFS::solutionCount = 0;
int main()
{
DFS R;
R.setOptions(axis, 4);
R.beginCount(16, directionString, true);
cout<<"Total number is "<<R.getSolutionCount()<<endl;
return 0;
}
//I don't know what extra work to be for the time being
bool DFS::evaluate()
{
return depth == 9;
}
bool DFS::touchDown()
{
return depth==maxLevel;
}
void DFS::onLeave()
{
DFS* ptr =this;
delete ptr;
}
//a stack
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<<nameString[temp[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);
}
}
bool DFS::doGenerate()
{
bool result = false;
if (touchDown())
{
return 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, char** str, bool findall)
{
setNameStr(str);
DFS* ptr = this;
setMaxLevel(max);
findAll = findall; //setup if want all result
initialize(this);
while (true)
{
ptr = ptr->generate();
if (ptr==NULL)
{
if (solutionCount==0)
{
cout<<"No solution!";
}
break;
}
if (ptr->evaluate())
{
ptr->collectResult();
if (!findAll)
{
break;
}
}
ptr = ptr->findBrother();
if (ptr==NULL)
{
if (solutionCount==0)
{
cout<<"No solution!";
}
break;
}
}
}
DFS* DFS::generate()
{
DFS* ptr= this;
while (!ptr->evaluate())
{
if (!ptr->doGenerate())
{
ptr=ptr->findBrother();
if (ptr==NULL)
{
break;
}
}
else
{
ptr = ptr->sonArray[0];
}
}
return ptr;
}
DFS* DFS::createSon()
{
DFS* ptr = new DFS;
return ptr;
}
void DFS::addSon(int sonData)
{
if (sonCount+1<MaxSonCount)
{
DFS* ptr = createSon();
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(DFS* now)
{
root = now;
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 5040
กก