algraph.cpp

来自「全国交通咨询系统源代码」· C++ 代码 · 共 522 行

// ALGraph.cpp: implementation of the ALGraph class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "map.h"
#include "ALGraph.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////


ALGraph::ALGraph():m_arcnum(0),m_vexnum(0),ID(5555)
{
	m_nowtime=0;
	isformed=NULL;
	m_tatol=0;
}

ALGraph::~ALGraph()
{
	if(isformed!=NULL) delete[] isformed;

}

bool ALGraph::InsertCity(CString cityname)
{
	if(CityLocal(cityname)) return false;
	m_vertices.SetSize(m_vertices.GetSize()+1);
	m_vertices[m_vertices.GetUpperBound()].GetCityName()=cityname;
	m_vexnum++;
	return true;
}

bool ALGraph::CityLocal(CString cityname)
{
	if(m_vertices.GetUpperBound()==-1) return false; 
	for(int i=0;i<=m_vertices.GetUpperBound();i++)
	{
		if(m_vertices[i].GetCityName()==cityname) return true;
	}
	return false;
}

bool ALGraph::InsertCity(CString city1,CString city2,InfoNode cityinfo)
{
	int pos1=-1,pos2=-1;
	POSITION temp1(NULL),temp2(NULL);
	if(!(CityLocal(city1,pos1)&&CityLocal(city2,pos2))) return false;
	cityinfo.GetCityNum()=pos2;
	CList<InfoNode,InfoNode &> & plist1=m_vertices[pos1].GetList();
	temp1=plist1.Find(cityinfo,temp1);
	if(temp1!=NULL) return false;
	plist1.AddTail(cityinfo);
	cityinfo.GetCityNum()=pos1;
	CList<InfoNode,InfoNode &> & plist2=m_vertices[pos2].GetList();
	plist2.AddTail(cityinfo);
	m_arcnum+=2;
	return true;
}

bool ALGraph::CityLocal(CString cityname, int & j)
{
	if(m_vertices.GetUpperBound()==-1) return false; 
	for(int i=0;i<=m_vertices.GetUpperBound();i++)
	{
		if(m_vertices[i].GetCityName()==cityname) {j=i;return true;}
	}
	return false;
}

bool ALGraph::DeleteCity(CString cityname)
{
	int pos=-1;
	int num=0;
	if(!CityLocal(cityname,pos)) return false;
	num=m_vertices[pos].GetList().GetCount();
	if(num!=0)
		for(int i=0;i<=m_vertices.GetUpperBound();i++)
		{
			POSITION tip;
			if(pos==i) continue;
			CList<InfoNode,InfoNode &> & plist=m_vertices[i].GetList();
			tip=plist.GetHeadPosition();
			while(tip==NULL)
			{
				if(pos==plist.GetAt(tip).GetCityNum()) 
				{plist.RemoveAt(tip);m_arcnum-=2;break;}
				plist.GetNext(tip);
			}
		}
	 m_vertices.RemoveAt(pos);
	 m_vexnum--;
	 return true;
}

	





bool ALGraph::DeleteCity(CString city1, CString city2)
{
	int i=-1,j=-1;
	if(!(CityLocal(city1,i)&&CityLocal(city2,j))) return false;
	bool temp=false;
	POSITION tp1,tp2;
	CList<InfoNode,InfoNode &> & plist1=m_vertices[i].GetList();
	CList<InfoNode,InfoNode &> & plist2=m_vertices[j].GetList();
	tp1=plist1.GetHeadPosition();
	while(tp1!=NULL)
	{
		if(plist1.GetAt(tp1).GetCityNum()==j)
		{
			POSITION temppos=tp1;
			plist1.GetNext(temppos);
			plist1.RemoveAt(tp1);
			temp=true;
			tp1=temppos;
		}
		else plist1.GetNext(tp1);
	}
	if(temp) 
	{
		for(tp2=plist2.GetHeadPosition();tp2!=NULL;)
		{
			if(plist2.GetAt(tp2).GetCityNum()==i)
			{
				POSITION temppos=tp2;
				plist2.GetNext(temppos);
				plist2.RemoveAt(tp2);
				tp2=temppos;
			}
			else plist2.GetNext(tp2);
		}
	m_arcnum-=2;
	}
	else return false;
	return true;
}

bool ALGraph::EditArc(CString city1, CString city2, InfoNode cityinfo)
{
	int num1=-1,num2=-1;
	if(!(CityLocal(city1,num1)&&CityLocal(city2,num2))) return false;
	POSITION tp;
	bool temp=false;
	for(tp=m_vertices[num1].GetList().GetHeadPosition();tp!=NULL;m_vertices[num1].GetList().GetNext(tp))
	{
		InfoNode &ptoinfo=m_vertices[num1].GetList().GetAt(tp);
		if(num2==ptoinfo.GetCityNum())
		{
			temp=true;
			ptoinfo.GetCar()=cityinfo.GetCar();
			ptoinfo.GetDistance()=cityinfo.GetDistance();
			ptoinfo.GetPlain()=cityinfo.GetPlain();
			ptoinfo.GetTrain()=cityinfo.GetTrain();
		}
	}
	if(!temp) return false;
	for(tp=m_vertices[num2].GetList().GetHeadPosition();tp!=NULL;m_vertices[num2].GetList().GetNext(tp))
	{
		InfoNode &ptoinfo=m_vertices[num2].GetList().GetAt(tp);
		if(num1==ptoinfo.GetCityNum())
		{
			ptoinfo.GetCar()=cityinfo.GetCar();
			ptoinfo.GetDistance()=cityinfo.GetDistance();
			ptoinfo.GetPlain()=cityinfo.GetPlain();
			ptoinfo.GetTrain()=cityinfo.GetTrain();
		}
	}
	return true;
}

InfoNode ALGraph::CreatInofNode(Info car, Info plain, Info train,int distance,int citynum)
{
	InfoNode temp;
	temp.GetCityNum()=citynum;
	temp.GetDistance()=distance;
	temp.GetCar()=car;
	temp.GetPlain()=plain;
	temp.GetTrain()=train;
	return temp;
}	

Info ALGraph::CreatInfo(int fee, int time, int timespend)
{
	Info temp;
	temp.SetFee(fee);
	temp.SetTime(time);
	temp.SetTimeSpend(timespend);
	return temp;

}

//DEL bool ALGraph::SaveALGraph(CStdioFile & temp)
//DEL {
//DEL 	CFileStatus status;
//DEL 	if(!temp.GetStatus(status)) return false;
//DEL 	if(temp.GetLength()!=0) return false;
//DEL 	temp.Write(&ID,sizeof(UINT));
//DEL 	temp.Write(&m_vexnum,sizeof(int));
//DEL 	temp.Write(&m_arcnum,sizeof(int));
//DEL 	for(int i=0;i<m_vexnum;i++)
//DEL 	{
//DEL 		int arc=-1;
//DEL 		ArrayElem & array=m_vertices[i];
//DEL 		temp.WriteString(array.GetCityName());
//DEL 		CList<InfoNode,InfoNode &> &list=array.GetList();
//DEL 		arc=list.GetCount();
//DEL 		temp.Write(&arc,sizeof(int));
//DEL 		POSITION pos;
//DEL 		if((pos=list.GetHeadPosition())==NULL) continue;
//DEL 		do{
//DEL 			InfoNode &node=list.GetAt(pos);
//DEL 			temp.Write(&node.GetCityNum(),sizeof(int));
//DEL 			temp.Write(&node.GetDistance(),sizeof(int));
//DEL 			node.GetCar()>>temp;
//DEL 			node.GetPlain()>>temp;
//DEL 			node.GetTrain()>>temp;
//DEL 			list.GetNext(pos);
//DEL 		}while(pos!=NULL);
//DEL 	}
//DEL 	return true;
//DEL }

//DEL bool ALGraph::OpenALGraph(CStdioFile & temp)
//DEL {
//DEL 	
//DEL 	UINT tip=0;
//DEL 	temp.Read(&tip,sizeof(UINT));
//DEL 	if(tip!=55555) return false;
//DEL 	temp.Read(&m_vexnum,sizeof(int));
//DEL 	temp.Read(&m_arcnum,sizeof(int));
//DEL 	for(int i=0;i<m_vexnum;i++)
//DEL 	{
//DEL 		int listnum=-1;
//DEL 		ArrayElem array;
//DEL 		temp.ReadString(array.GetCityName());
//DEL 		CList<InfoNode,InfoNode &> &list=array.GetList();
//DEL 		temp.Read(&listnum,sizeof(int));
//DEL 		for(int j=1;j<=listnum;j++)
//DEL 		{
//DEL 			InfoNode node;
//DEL 			temp.Read(&node.GetCityNum(),sizeof(int));
//DEL 			temp.Read(&node.GetDistance(),sizeof(int));
//DEL 			node.GetCar()<<temp;
//DEL 			node.GetPlain()<<temp;
//DEL 			node.GetTrain()<<temp;
//DEL 			list.AddTail(node);
//DEL 		}
//DEL 		m_vertices.Add(array);		
//DEL 	}
//DEL 	return true;
//DEL }

ALGraph::ALGraph(const ALGraph & temp)
{
	int num=-1;
	ID=temp.ID;
	m_arcnum=temp.m_arcnum;
	m_vexnum=temp.m_vexnum;
	num=temp.m_vertices.GetSize();
	m_vertices.SetSize(num);
	for(int i=0;i<num;i++) m_vertices[i]=temp.m_vertices[i];
}

ALGraph & ALGraph::operator =(ALGraph & temp)
{
	int num=-1;
	ID=temp.ID;
	m_arcnum=temp.m_arcnum;
	m_vexnum=temp.m_vexnum;
	num=temp.m_vertices.GetSize();
	m_vertices.SetSize(num);
	for(int i=0;i<num;i++) m_vertices[i]=temp.m_vertices[i];
	return *this;
}

void ALGraph::Serialize(CArchive &archive)
{
//	CObject::Serialize(archive);
	if(archive.IsStoring())
	{
		archive<<ID<<m_arcnum<<m_vexnum;
		for(int i=0;i<m_vexnum;i++) m_vertices[i].Serialize(archive);
	}
    else
	{
        archive>>ID>>m_arcnum>>m_vexnum;
		if(m_vexnum!=0) m_vertices.SetSize(m_vexnum);
		for(int i=0;i<m_vexnum;i++) m_vertices[i].Serialize(archive);
	}
}

//DEL int ALGraph::MatrixToInt(int, int)
//DEL {
//DEL 
//DEL }

int ALGraph::MatrixToInt(int num1, int num2)
{
	if(num1<0||num2<0) return(-1);
	return(num1*m_vexnum+num2);
}

void ALGraph::GetMGraph(int kind)//1代表距离
//2代表汽车费用,3代表汽车耗时,4代表汽车到达时刻
//5代表飞机费用,6代表飞机耗时,7代表飞机到达时刻
//8代表火车费用,9代表火车耗时,10代表火车到达时刻
{
	if(m_vexnum<=0) return;
	int *matrix=new int[m_vexnum*m_vexnum];
	for(int j=0;j<m_vexnum*m_vexnum;j++) matrix[j]=0;
	for(int i=0;i<m_vexnum;i++)
	{
		CList<InfoNode,InfoNode &> &list=m_vertices[i].GetList();
		POSITION pos;
		pos=list.GetHeadPosition();
		while(pos!=NULL)
		{
			InfoNode &temp=list.GetAt(pos);
			switch(kind)
			{
			case 1:
				{
					matrix[MatrixToInt(i,temp.GetCityNum())]=temp.GetDistance();
					break;
				}
			case 2:
				{
					matrix[MatrixToInt(i,temp.GetCityNum())]=temp.GetCar().GetFee();
					break;
				}
			case 3:
				{
					matrix[MatrixToInt(i,temp.GetCityNum())]=temp.GetCar().GetTimeSpend();
					break;
				}
			case 4:
				{
					break;
				}
			case 5:
				{
					matrix[MatrixToInt(i,temp.GetCityNum())]=temp.GetPlain().GetFee();
					break;
				}
			case 6:
				{
					matrix[MatrixToInt(i,temp.GetCityNum())]=temp.GetPlain().GetTimeSpend();
					break;
				}
			case 7:
				{
					break;
				}
			case 8:
				{
					matrix[MatrixToInt(i,temp.GetCityNum())]=temp.GetTrain().GetFee();
					break;
				}
			case 9:
				{
					matrix[MatrixToInt(i,temp.GetCityNum())]=temp.GetTrain().GetTimeSpend();
					break;
				}
			case 10:
				{
					break;
				}
			default:
				{
					isformed=NULL;
					return;
				}
			}
			list.GetNext(pos);
		}
	}
	isformed=matrix;
}

int * ALGraph::GetVector()
{
	int * temp=new int[m_vexnum];
	return temp;
}

bool ALGraph::ShortestPath(const int v, const int e,CList<int,int &> & list,int kind)
{
	if(isformed!=NULL) {delete[] isformed;isformed=NULL;}
	GetMGraph(kind);
	const int MAXNUM=2147483647;
	int fail=-10;
	if(isformed==NULL||v==e) {list.AddHead(fail);return false;}
	for(int i=0;i<m_vexnum*m_vexnum;i++) 
	{
		if(isformed[i]==0) 
			isformed[i]=MAXNUM;
	}
	int * dist=GetVector();
	int * path=GetVector();
	int * S=GetVector();
	for(i=0;i<m_vexnum;i++) path[i]=-1;
	for(i=0;i<m_vexnum;i++)
	{
		dist[i]=isformed[MatrixToInt(v,i)];
		S[i]=0;
		if(i!=v&&dist[i]<MAXNUM) path[i]=v;
		else path[i]=-1;
	}
	S[v]=1;dist[v]=0;
	for(i=0;i<m_vexnum-1;i++)
	{
		int min=MAXNUM;int u=v;
		for(int j=0;j<m_vexnum;j++)
		{
			if(!S[j]&&dist[j]<min)
			{
				u=j;
				min=dist[j];
			}
		}
		S[u]=1;
		for(int w=0;w<m_vexnum;w++)
		{
			if(!S[w]&&isformed[MatrixToInt(u,w)]<MAXNUM&&dist[u]+isformed[MatrixToInt(u,w)]<dist[w])
			{
				dist[w]=dist[u]+isformed[MatrixToInt(u,w)];
				path[w]=u;
			}
		}
	}
	i=e;
	list.AddHead(i);
	bool tip=false;
	do
	{
		i=path[i];
		list.AddHead(i);
		if(i==v) {tip=true;break;}
	}while(i!=-1);
	if(!tip) {list.RemoveAll();list.AddHead(fail);return false;}
	m_tatol=dist[e];
	delete[] dist;
	delete[] path;
	delete[] S;
	return true;
}


BOOL ALGraph::SeekShort(CString cityfirst, CString citysecond, CString & result,int kind)
{
	int v=-1,e=-1;
	if(!CityLocal(cityfirst,v)) return false;
	if(!CityLocal(citysecond,e)) return false;
	CList<int,int &> resultlist;
	if(!ShortestPath(v,e,resultlist,kind)) return false;
	const CString tip="##";
	int num=resultlist.GetCount();
	if(num==0) return false;
	POSITION pos;
	pos=resultlist.GetHeadPosition();
	result=_T("");
	while(pos!=NULL) result=result+tip+m_vertices[resultlist.GetNext(pos)].GetCityName();
	CString uite;
	MakeString(kind,uite);
	CString uites;
	uites="总共";
	uites.Format("%d",m_tatol);
	uites=uites+uite;
	result=result+tip+uites;//需要修改
	return true;
}

void ALGraph::MakeString(const int kind,CString & temp)
{
//2代表汽车费用,3代表汽车耗时,4代表汽车到达时刻
//5代表飞机费用,6代表飞机耗时,7代表飞机到达时刻
//8代表火车费用,9代表火车耗时,10代表火车到达时刻
	switch(kind)
	{
	case 1:
		{
			temp="公里";
			break;
		}
	case 5:
	case 8:
	case 2:
		{
			temp="元";
			break;
		}
	case 6:
	case 9:
	case 3:
		{
			temp="分";
			break;
		}
	case 10:
	case 7:
	case 4:
		{
			temp="分";
			break;
		}
	default:
		break;
	}
}