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.
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.
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