main.cpp

Implemented BFS, DFS and A* To compile this project, use the following command: g++ -o search ma

#include <iostream>
#include <fstream>

using namespace std;

int data[100][100];        //store the map
int hypo[100];             //store the heuristic
int n;                     //number of cities, in this project it equals 26

class Node
{

public:
	Node()
	{
	}
	~Node()
	{
	}

	int dist;               //distance from the start city to the city in the node
	int path[500];          //The path from the start city to the city in the node
	int step;               //number of steps 
	Node* nextn;            //pointer to the next node in the queue

};

class ANode :public Node
{

public:
	ANode()
	{
	}
	~ANode()
	{
	}
	
	int estc;      // estc for estimated cost
	ANode* nextn;

};

class GeneralSearch
{
public:
	GeneralSearch()
	{

	}
	~GeneralSearch()
	{
	}
	
	virtual void print(Node * p) { };           //print solution
	virtual void printnodes(Node * fst) {};     //print nodes in the queue
	virtual Node * expend(Node* p, int i){return p;};  //expend node p with city i
	virtual void QueueingFN(Node** fst, Node** lst, Node** tmp){};
	                           //put node *tmp into queue
	virtual int Search(char source, char goal){return 0;};
	                          //search the path from source city to destination city using some algorithms
	
};

class Breadthfirst: public GeneralSearch
{
public:
	Breadthfirst()
	{
	}
	~Breadthfirst()
	{
	}

	void print(Node * p)
	{
		int i;
		cout << "Solution Found!\n";
		cout << "Path: ";
		for (i=0;i<=p->step-1;i++)
		{
			cout << (char)(p->path[i]+'A') << ' ';
		}
		cout << (char)(p->path[p->step]+'A') << endl;
		cout << "Steps: " << p->step << endl;
		cout << "Cost: " << p->dist << endl;  
		
	}

	void printnodes(Node * fst)
	{
		Node * p;
		int i;
		p=fst;
		cout << '[';
		while (p!=NULL)
		{
			cout << '(' << p->dist << ",(";
			for (i=0; i<=p->step; i++)
			{
				cout << char(p->path[i]+'A');
				if (i!=p->step) cout << ' ';
			}
			cout << "))";
			p=p->nextn;
		}
		cout << "]\n";
	}

	Node * expend(Node* p, int i)
	{
		Node * tmp;
		int j,k;
		tmp = new Node;
		tmp->dist=p->dist+data[p->path[p->step]][i];
		tmp->step=p->step+1;
		j=p->step;
		for (k=0;k<=j;k++)    //copy path from the node to be expended
			tmp->path[k]=p->path[k];
		j++;
		tmp->path[j]=i;
		tmp->nextn=NULL;
		return tmp;
	}

	void QueueingFN(Node** fst, Node** lst, Node** tmp)
	{
		(*lst)->nextn=*tmp;   //add to the end of queue
		*lst=(*lst)->nextn;		
	}

	int Search(char source, char goal)
	{
		Node * fst, * lst, * tmp, * p, * q;
		int s,g,flg;
		int i,j;
		cout << "Now Breadthfirst Search Begin:\n";
		s=source-'A';
		g=goal-'A';
		tmp = new Node;    //make the first node in queue
		tmp->dist=0;
		tmp->step=0;
		tmp->path[0]=s;
		tmp->nextn=NULL;
		fst = tmp;
		lst = tmp;
		p = tmp;
		printnodes(fst);
		while (fst != NULL)
		{
			p=fst;
			for (i=0;i<n;i++)
			{
				if (data[fst->path[fst->step]][i]>=0) //if there is a connection
				{
					flg=1;
					for (j=0;j<=fst->step;j++)
						if (i==fst->path[j])
						{
							flg = 0;  //if this city has already expended
							break;
						}
					if (flg)        //if the city has not been expended 
					{
						tmp = expend(fst,i);  //expend it and add to the queue
						QueueingFN(&fst,&lst,&tmp);
						if (i==g)   //test if find a solution
						{
							q=fst;
							fst=fst->nextn;	
							printnodes(fst);
							print(tmp); 
							delete q; 
							return tmp->step;
						}
					}	
				}
			}
			q=fst;              //remove the front node of the queue
			fst=fst->nextn;	
			printnodes(fst);
			delete q;
		}
		
		return -1;  //if do not find a solution, return -1
		
	}

};


class Depthfirst: public GeneralSearch
{

public:

	int visited[100];    //mark if the city has been expended
	Node * bottom, * top; //the bottom and top pointer of the stack(queue)

	Depthfirst()
	{
		int i;
		for (i=0;i<100;i++)
		{
			visited[i]=0; //mark all cities unexpended
		}
	}
	~Depthfirst()
	{
	}

	void print(Node * top)
	{
		int i;
		cout << "Solution Found!\n";
		cout << "Path: ";
		for (i=0;i<top->step;i++)
		{
			cout << (char)(top->path[i]+'A') << ' ';
		}
		cout << (char)(top->path[top->step]+'A') << endl;
		cout << "Steps: " << top->step << endl;
		cout << "Cost: " << top->dist << endl; 
		
	}

	void printnodes(Node * fst)
	{
		Node * p;
		int i;
		p=fst;
		cout << '[';
		while (p!=NULL)
		{
			cout << '(' << p->dist << ",(";
			for (i=0; i<=p->step; i++)
			{
				cout << char(p->path[i]+'A');
				if (i!=p->step) cout << ' ';
			}
			cout << "))";
			p=p->nextn;
		}
		cout << "]\n";
	}

	Node * expend(Node * p, int i)
	{
		Node * tmp;
		int j,k;
		tmp = new Node;
		tmp->dist=p->dist+data[p->path[p->step]][i];
		tmp->step=p->step+1;
		j=p->step;
		for (k=0;k<=j;k++)
			tmp->path[k]=p->path[k];
		j++;
		tmp->path[j]=i;
		tmp->nextn=NULL;
		return tmp;
			
	}

	void QueueingFN(Node** fst, Node** lst, Node** tmp)
	{
		(*lst)->nextn=*tmp;    //add to the front of the queue
		*tmp=*lst;             //here *lst is the front pointer of the queue
		*lst=(*lst)->nextn;
	}

	int findpath(int s, int g) //implement depthfirst algorithm recursively
	{
		int i,k;
		Node * tmp;
		char ch;
		if (s==g)              //goal test
		{
			print(top);
			return top->step;	//return the steps	
		}
		for (i=0; i<n; i++)
		{
			if ((data[s][i]>=0)&&(visited[i]==0))
			{
				visited[i]=1;   //mark the city is already expended
				ch=i+'A';
				tmp = expend(top,i);
				QueueingFN(&bottom, &top, &tmp);
				printnodes(bottom);
				k=findpath(i,g);
				if (k>=0) return top->step;
				delete top;
				top=tmp;
				top->nextn=NULL;
				visited[i]=0;

			}
		}
		return -1;
	}

	int Search(char source, char goal)
	{
		int s,g;
	
		cout << "Now Depthfirst Search Begin:\n";
		s=source-'A';
		g=goal-'A';

		visited[s]=1;       //mark the source city expended
		bottom = new Node;
		bottom->step=0;
		bottom->dist=0;
		bottom->path[bottom->step]=s;
		bottom->nextn=NULL;
		top=bottom;
		printnodes(bottom);
		if (findpath(s,g)>=0) return top->step;
		
		return -1;

	}


};


class Astar: public GeneralSearch
{

public:
	Astar()
	{
	}
	~Astar()
	{
	}
  	void print(ANode * p)
	{
		int i;
		cout << "Solution Found!\n";
		cout << "Path: ";
		for (i=0;i<=p->step-1;i++)
		{
			cout << (char)(p->path[i]+'A') << ' ';
		}
		cout << (char)(p->path[p->step]+'A') << endl;
		cout << "Steps: " << p->step << endl;
		cout << "Cost: " << p->dist << endl;  
		
	}
	
	void printnodes(ANode * fst)
	{
		ANode * p;
		int i;
		p=fst;
		cout << '[';
		while (p!=NULL)
		{
			cout << '(' << p->estc << ',' << p->dist << ",(";
			for (i=0; i<=p->step; i++)
			{
				cout << char(p->path[i]+'A');
				if (i!=p->step) cout << ' ';
			}
			cout << "))";
			p=p->nextn;
		}
		cout << "]\n";
	}

	ANode * expend(ANode* p, int i)
	{
		ANode * tmp;
		int j,k;
		tmp = new ANode;
		tmp->dist=p->dist+data[p->path[p->step]][i];
		tmp->step=p->step+1;
		j=p->step;
		for (k=0;k<=j;k++)
			tmp->path[k]=p->path[k];
		j++;
		tmp->path[j]=i;
		tmp->estc=tmp->dist+hypo[i]; //caculate the estimated cost
		tmp->nextn=NULL;
		return tmp;
	}

	void QueueingFN(ANode** fst, ANode** lst, ANode** tmp)
	{
		ANode *p, *q;
		if ((*fst)->nextn==NULL)  //if queue is empty, add to the end
		{
			(*lst)->nextn=*tmp;
			*lst=(*lst)->nextn;
		}
		else 
		{
			p=(*fst)->nextn;
			q=(*fst);
			while (p!=NULL)  //find p q that q->estc<=*tmp->estc<=q->estc
			{
				if (p->estc > (*tmp)->estc)
					break;
				p=p->nextn;
				q=q->nextn;
			}
			q->nextn=*tmp;  //insert *tmp between p q
			(*tmp)->nextn=p;
		}
	}

	int Search(char source, char goal)
	{
		ANode * fst, * lst, * tmp, * p, * q;
		int s,g,flg; 
		int i,j;
		cout << "Now A* Search Begin:\n";
		s=source-'A';
		g=goal-'A';
		tmp = new ANode;
		tmp->dist=0;
		tmp->step=0;
		tmp->path[0]=s;
		tmp->nextn=NULL;
		tmp->estc = tmp->dist + hypo[s];
		fst = tmp;
		lst = tmp;
		p = tmp;
		printnodes(fst);
		while (fst != NULL)
		{
			p=fst; 
			for (i=0;i<n;i++)
			{
				if (data[fst->path[fst->step]][i]>=0)
				{
					flg=1;
					for (j=0;j<=fst->step;j++)
						if (i==fst->path[j])
						{
							flg = 0;
							break;
						}
					if (flg)
					{
						tmp = expend(fst,i);
						QueueingFN(&fst, &lst, &tmp);
						if (i==g)    //goal test
						{
							q=fst;
							fst=fst->nextn;	
							printnodes(fst);
							print(tmp);
							delete q;
							return tmp->step;
						}
					}	
				}
			}
			
			q=fst;
			fst=fst->nextn;
			printnodes(fst);
			delete q;
		}
		
		return -1;
		
	}

};
	

int main()
{
	int i,j,k;
	char ss,gg,aa,bb;
	ifstream fp("in.txt");           //input data and initialize state

	for (i=0; i<100; i++)
		for (j=0;j<100;j++)
			data[i][j]=-1;
	fp >> ss >> gg;                  //input source and destinition cities for Breadth-first and Depth-first
	fp >> j;                         //read number of connections
	for (i=0;i<j;i++)
	{
		fp >> k >> aa >> bb;
		data[aa-'A'][bb-'A']=k;
		data[bb-'A'][aa-'A']=k;
	}
	
	n=26;                            //number of cities

	GeneralSearch * GS;

	GS = new Breadthfirst;           //do breadth first search
	GS->Search(ss,gg);

	GS = new Depthfirst;             //do depth first search
	GS->Search(ss,gg);

	fp >> ss >> gg;                  //input source and destinition cities for A*
	fp >> j;                         //read number of heuristic
	for (i=0; i<j; i++)
	{
		fp >> aa >> k;
		hypo[aa-'A']=k;
	}

	GS = new Astar;                  //do A* search
	GS->Search(ss,gg);

	return 0;
}