A Star algorithm

				
//**************************************
// Name: A Star algorithm
// Description:This program demonstrates the working of A Star algorithm which uses heuristics search in state space.
// By: Puneet Jindal
//
//This code is copyrighted and has// limited warranties.Please see http://www.Planet-Source-Code.com/vb/scripts/ShowCode.asp?txtCodeId=13834&lngWId=3//for details.//**************************************

#include<iostream>
#include<vector>
#include<cstring>
#include<cmath>
class Vertex;
using namespace std;
class Edge
{	
	public:
		int a,b;
		int cost;
		Edge(int c = 0)
		{
			a = b = -1;
			cost = c;
		} 
		
		bool operator ==(Edge &e) { return a == e.a && b == e.b;}
};
class Vertex
{
	public:
		float x,y;
		vector<int> edge;
		char label;
		char status;//	Degree is size of edge
		float gn,fn;
		string path;
		
		Vertex(char ch = '-')
		{
			x = y = 0.0;
			gn = fn = 0.0;
			label = ch;
			status = 'u';
			path = "";
		}
		
		bool operator == (Vertex &v) {return (label == v.label && x == v.x && y == v.y);}
void Display()
{
//cout<<"x,y ->"<<x<<","<<y<<endl;
//cout<<"Label ->"<<label<<endl;
//cout<<"Status ->"<<status<<endl;
//cout<<"Path ->"<<path<<endl;
//cout<<"gn and fn ->"<<gn<<"\t"<<fn<<endl;
}
};
class Graph
{
	public:
		vector<Vertex> Vertices;
		vector<Edge> Edges;
		Graph(){}
		
		int Find(char ch = '-')
		{
			for(int i = 0 ; i < Vertices.size() ; ++i)
				if(ch == Vertices[i].label)
					return i;
			cerr<<"Unknown vertex encountered"<<endl;
			return -1;
		}
		
		void Draw()
		{
			//cout<<"Enter label of the vertices and their co-ordinates.Press '.' to stop entering vertices"<<endl;
			
			while(true)
			{
				char label = ' ';
				//cout<<"Label ->";
				cin>>label;
				if(label == '.')
					break;
				//cout<<"Co-ordinates(x,y) ->";
				float x = 0, y = 0;
				cin>>x>>y;
				
				Vertex v(label);
				v.x = x;
				v.y = y;
				Vertices.push_back(v);
			}
			for(int i = 0 ; i < Vertices.size() ; ++i)	
			{
				//cout<<"Enter adjacent vertices to the vertex '"<<Vertices[i].label<<"' one by one. Press '.' to stop entering."<<endl;
				while(1)
				{
					//cout<<"Adjacent vertex ->";
					char other = '.';
					cin>>other;
					if(other == '.')
						break;
					else
					{
						//cout<<"Enter cost of edge ("<<Vertices[i].label<<","<<other<<")"<<endl;
						int cost = 0;
						cin>>cost;
						Edge curr_edge(cost);
curr_edge.a = i;
cost = Find(other);
curr_edge.b = cost;
Edges.push_back(curr_edge);
Vertices[i].edge.push_back(Edges.size()-1);
Vertices[cost].edge.push_back(Edges.size()-1);
					}
				}
				
			}
		}//	Graph drawn
};
float Calculate(Vertex &start, Vertex &goal)
{
	return sqrt( (start.x - goal.x)*(start.x - goal.x) + (start.y - goal.y)*(start.y - goal.y));
}
int Min_fn_from_Open(Graph &g)
{
int min = 0;
for(int i = 0 ; i < g.Vertices.size() ; ++i)
if(g.Vertices[i].status == 'o' && g.Vertices[i].fn < g.Vertices[min].fn)
min = i;
return min;
}
bool OpenEmpty(Graph &g)
{
for(int i = 0 ; i < g.Vertices.size() ; ++i)
if(g.Vertices[i].status == 'o')
return false;
return true;
}
string astar(Vertex &start, Vertex &goal, Graph &g)
{
	start.gn = 0;
	start.fn = Calculate(start, goal);
	start.status = 'o';
	start.path = start.label;
	do
	{
		int curr_state_index = Min_fn_from_Open(g);
		g.Vertices[curr_state_index].status = 'c';
g.Vertices[curr_state_index].Display();
		if(g.Vertices[curr_state_index] == goal)
		{
			//cout<<"Goal found"<<endl;
			return g.Vertices[curr_state_index].path;
		}
		for(int i = g.Vertices[curr_state_index].edge.size()-1 ; i >= 0 ; --i)
		{
			int new_gn = g.Vertices[curr_state_index].gn + g.Edges[g.Vertices[curr_state_index].edge[i]].cost;
			g.Vertices[curr_state_index].fn = Calculate(g.Vertices[curr_state_index], goal);
			
			int descendent_index = -1;
			if(g.Vertices[g.Edges[g.Vertices[curr_state_index].edge[i]].a] == g.Vertices[curr_state_index])
				descendent_index = g.Edges[g.Vertices[curr_state_index].edge[i]].b;
			else
				descendent_index = g.Edges[g.Vertices[curr_state_index].edge[i]].a;
g.Vertices[descendent_index].Display();
			if(g.Vertices[descendent_index].status == 'c' && new_gn < g.Vertices[descendent_index].gn)
			{
				g.Vertices[curr_state_index].status = 'u';
				g.Vertices[descendent_index].status = 'o';
				g.Vertices[descendent_index].path = g.Vertices[curr_state_index].path + g.Vertices[descendent_index].label;
				g.Vertices[descendent_index].gn = new_gn;	//	Common
			}
			else if(g.Vertices[descendent_index].status == 'o' && new_gn < g.Vertices[descendent_index].gn)
			{
				g.Vertices[descendent_index].path = g.Vertices[curr_state_index].path + g.Vertices[descendent_index].label;
				g.Vertices[descendent_index].gn = new_gn;	//	Common
			}
			else if(g.Vertices[descendent_index].status != 'o')
			{
				g.Vertices[descendent_index].path = g.Vertices[curr_state_index].path + g.Vertices[descendent_index].label;
				g.Vertices[descendent_index].status = 'o';
				g.Vertices[descendent_index].gn = new_gn;	//	Common
			}
			g.Vertices[descendent_index].fn = Calculate(g.Vertices[descendent_index], goal);
		}
		
	}while(OpenEmpty(g) == false);
	return "";
}
int main()
{
	Graph G;
	G.Draw();
	char s,g;
	cin>>s>>g;
	cout<<astar(G.Vertices[G.Find(s)], G.Vertices[G.Find(g)],G)<<endl;
	return 0;
}