mgraph.cpp

(1) 提供对城市信息进行编辑(添加或删除)的功能.(2) 城市之间有两种交通工具:火车和飞机.提供对列车时刻表和飞机航班进行编辑(增设或删除)的功能.(3) 提供两种最优策略:最快到达或最省钱到达.

#include "Traffic.h"

ArcCell::ArcCell()//无穷大构造
{
	t_info p;
	dis=INFINITE;
	train=new Traffic_Table();
	p=new Traffic_Info(INFINITE,INFINITE,INFINITE);
	train->InsertTable(p);
	plane=new Traffic_Table();
	p=new Traffic_Info(INFINITE,INFINITE,INFINITE);
	plane->InsertTable(p);
}

ArcCell::ArcCell(ArcCell& other)//调用上一级的拷备构造
{
	dis=other.dis;
	train=new Traffic_Table(*(other.train));
	plane=new Traffic_Table(*(other.plane));
}

ArcCell::~ArcCell()
{
	delete train;
	delete plane;
}

int ArcCell::GetDis()
{
	return dis;
}

t_table ArcCell::GetTrain()
{
	return train;
}

t_table ArcCell::GetPlane()
{
	return plane;
}

double ArcCell::ShortestWait_T(double arrive)//最短等待时间
{
	if(arrive>=INFINITE)//处理无穷大的情况
		return INFINITE;
	t_info p;
	p=train->GetHead()->m_Successor();
	double time;
	for(time=arrive;time>=24;time=time-24);
	while(p)
	{
		if((double)p->m_GetStart()>=time) break;//找到合适的列车
		else//没找到
			p=p->m_Successor();
	}
	if(p)
		return (double)p->m_GetStart()-time;//赶上火车
	else
		return (double)train->GetHead()->m_Successor()->m_GetStart()+24-time;//没赶上火车
}

double ArcCell::ShortestWait_P(double arrive)//基本同上
{
	if(arrive>=INFINITE)
		return INFINITE;
	t_info p;
	p=plane->GetHead()->m_Successor();
	double time;
	for(time=arrive;time>=24;time=time-24);
	while(p)
	{
		if((double)p->m_GetStart()>=time) break;
		else
			p=p->m_Successor();
	}
	if(p)
		return (double)p->m_GetStart()-time;//赶上飞机
	else
		return (double)plane->GetHead()->m_Successor()->m_GetStart()+24-time;//没赶上飞机
}

double ArcCell::GetTimeCost_T()
{
	return train->GetHead()->m_Successor()->m_GetCost();
}

double ArcCell::GetTimeCost_P()
{
	return plane->GetHead()->m_Successor()->m_GetCost();
}

double ArcCell::LowestCost_T(int& st)//找出最便宜的列车
{
	double temp=INFINITE;
	t_info p=train->GetHead()->m_Successor();

	while(p)
	{
		if(p->m_GetFee()<temp)
		{
			temp=p->m_GetFee();
			st=p->m_GetStart();
		}
		p=p->m_Successor();
	}

	return temp;
}

double ArcCell::LowestCost_P(int& st)//找出最便宜的飞机
{
	double temp=INFINITE;
	t_info p=plane->GetHead()->m_Successor();
	
	while(p)
	{
		if(p->m_GetFee()<temp)
		{
			temp=p->m_GetFee();
			st=p->m_GetStart();
		}
		p=p->m_Successor();
	}
	
	return temp;
}

int ArcCell::GetFirstTrain()//由于时刻表是时间序，所以第一个结点的列车就是每天的第一趟
{
	return train->GetHead()->m_Successor()->m_GetStart();
}

int ArcCell::GetFirstPlane()//飞机第一趟，同上
{
	return plane->GetHead()->m_Successor()->m_GetStart();
}

//修改函数
void ArcCell::SetArc(int distance,t_table train_table,t_table plane_table)
{
	dis=distance;
	if(train)
		delete train;
	if(plane)
		delete plane;
	train=new Traffic_Table(*train_table);
	plane=new Traffic_Table(*plane_table);
}
/////////////////////////////////////ArcCell类定义完毕////////////////////////////////////////////

/////////////////////////////////////MGraph类/////////////////////////////////////////////////////
MGraph::MGraph(ALGraph &graph)
{
	int i,len,pos,distance;
	aNode p;
	//复制个数
	vexnum=graph.GetvSize();
	arcnum=graph.GetaSize();
	//复制名字
	//vexs和arcs都是指向指针的指针，但两者类型不同
	vexs=new char*[vexnum];
	for(i=0;i<vexnum;i++)
	{
	//  len=strlen((graph.vertices[i])->GetName());这样是错的，因为vertices是ALGraph的保护变量。
		len=strlen((graph.GetVertices())[i]->GetName());
   		
		vexs[i]=new char[len+1];
		strcpy(vexs[i],(graph.GetVertices())[i]->GetName());
		(vexs[i])[len]='\0';
	}
	//申请矩阵空间
	arcs=new aCell[vexnum];
	for(i=0;i<vexnum;i++)
		arcs[i]=new ArcCell[vexnum];
	//复制弧，不存在弧的用distance=INFINITE表示
	for(i=0;i<vexnum;i++)
	{
		if((graph.GetVertices())[i])///这样做测试是因为跳过已删除的城市的顶点接点
		{
			for(p=(graph.GetVertices())[i]->GetFirst();p;p=p->Successor())
			{
				//求得位置
				pos=p->GetAdjvex()-1;
				//求出距离
				distance=(int)(p->GetTrain()->GetHead()->m_Successor()->m_GetCost()*TRAINSPEED);
				//整体设置
				arcs[i][pos].SetArc(distance,p->GetTrain(),p->GetPlane());
			}
		}
	}
}

MGraph::~MGraph()
{
	int i;
	for(i=0;i<vexnum;i++)
	{
		delete []vexs[i];
		delete []arcs[i];
	}

	delete []vexs;
	delete []arcs;
}

void MGraph::ShowGraph()//测试用显示函数
{
	int i,j;
	for(i=0;i<vexnum;i++)
	{
		for(j=0;j<vexnum;j++)
		{
			cout<<arcs[i][j].GetDis()<<" ";
		}
		cout<<endl;
	}
}

//最少中转


//最少火车时间
//需要求出最短路径
void MGraph::ShortestTime_T(int st,int nd)//注意－1
										 ///st为源地，nd为目的地
										 ///参照书本迪杰斯特拉算法P_189

///final[v]=TRUE时即已经求得从st到v的最短路径dist[xx]
///path[x][w]为TRUE时则w是从x到w当前求得最短路径上的顶点
{
	int i,j,v,w;
	double min;
	double* dist=new double[vexnum];
	bool* final=new bool[vexnum];
	bool** path=new bool*[vexnum];
	for(i=0;i<vexnum;i++)
		path[i]=new bool[vexnum];
	for(v=0;v<vexnum;v++)
	{
		final[v]=false;
		dist[v]=arcs[st][v].GetTimeCost_T() + arcs[st][v].GetFirstTrain();////for循环后dist[x]已经包含了城市间的花费时间
		                                                                  ////和第一趟车出发时间
		
		for(w=0;w<vexnum;w++)
			path[v][w]=false;//设空路径
		if(dist[v]<INFINITE)
		{
			path[v][st]=true;
			path[v][v]=true;
		}
	}
	dist[st]=0;    // 设置初始值，
	final[st]=true;// st当然属于最短路径集合
	//开始主循环
	for(i=1;i<vexnum;i++)
	{
		min=INFINITE;
		for(w=0;w<vexnum;w++)
			if(!final[w])
				if(dist[w]<min)
				{
					v=w;
					min=dist[w];
				}
		final[v]=true;
		for(w=0;w<vexnum;w++)///更新当前耗费时间及最少等候时间
		{
			if(!final[w] && (min + arcs[v][w].GetTimeCost_T() + arcs[v][w].ShortestWait_T(dist[v]) < dist[w]))
			{
				dist[w]=min+arcs[v][w].GetTimeCost_T()+arcs[v][w].ShortestWait_T(dist[v]);
				for(j=1;j<vexnum;j++)
					path[w][j]= path[v][j]; 
				path[w][w]=true;
			}
		}
	}
	if(dist[nd]>=INFINITE)
		cout<<"从"<<vexs[st]<<"无法到达"<<vexs[nd]<<endl;
	else
		ShowPath_Ttime(path[nd],st,nd);
}

//最少飞机时间
void MGraph::ShortestTime_A(int st,int nd)//注意－1
{
	int i,j,v,w;
	double min;
	double* dist=new double[vexnum];
	bool* final=new bool[vexnum];
	bool** path=new bool*[vexnum];
	for(i=0;i<vexnum;i++)
		path[i]=new bool[vexnum];
	for(v=0;v<vexnum;v++)
	{
		final[v]=false;
		dist[v]=arcs[st][v].GetTimeCost_P()+arcs[st][v].GetFirstPlane(); 
		for(w=0;w<vexnum;w++)
			path[v][w]=false;
		if(dist[v]<INFINITE)
		{
			path[v][st]=true;
			path[v][v]=true;
		}
	}
	dist[st]=0;//设置初始值
	final[st]=true;
	//开始主循环
	for(i=1;i<vexnum;i++)
	{
		min=INFINITE;
		for(w=0;w<vexnum;w++)
			if(!final[w])
				if(dist[w]<min)
				{
					v=w;
					min=dist[w];
				}
		final[v]=true;
		for(w=0;w<vexnum;w++)
		{
			if(!final[w] && (min+arcs[v][w].GetTimeCost_P()+arcs[v][w].ShortestWait_P(dist[v])<dist[w]))
			{
				dist[w]=min+arcs[v][w].GetTimeCost_P()+arcs[v][w].ShortestWait_P(dist[v]);
				for(j=1;j<vexnum;j++)
					path[w][j]= path[v][j]; 
				path[w][w]=true;
			}
		}
	}
	if(dist[nd]>=INFINITE)
		cout<<"从"<<vexs[st]<<"无法到达"<<vexs[nd]<<endl;
	else
		ShowPath_Atime(path[nd],st,nd);
}

//最少火车费用
void MGraph::ShortestCost_T(int st,int nd)//注意－1
{
	int i,j,v,w,temp;
	double min;
	double* dist=new double[vexnum];
	bool* final=new bool[vexnum];
	bool** path=new bool*[vexnum];
	for(i=0;i<vexnum;i++)
		path[i]=new bool[vexnum];
	for(v=0;v<vexnum;v++)
	{
		final[v]=false;
		dist[v]=arcs[st][v].LowestCost_T(temp); 
		for(w=0;w<vexnum;w++)
			path[v][w]=false;
		if(dist[v]<INFINITE)
		{
			path[v][st]=true;
			path[v][v]=true;
		}
	}
	dist[st]=0;//设置初始值
	final[st]=true;
	//开始主循环
	for(i=1;i<vexnum;i++)
	{
		min=INFINITE;
		for(w=0;w<vexnum;w++)
			if(!final[w])
				if(dist[w]<min)
				{
					v=w;
					min=dist[w];
				}
		final[v]=true;
		for(w=0;w<vexnum;w++)
		{
			if(!final[w] && (min+arcs[v][w].LowestCost_T(temp)<dist[w]))
			{
				dist[w]=min+arcs[v][w].LowestCost_T(temp);
				for(j=1;j<vexnum;j++)
					path[w][j]= path[v][j]; 
				path[w][w]=true;
			}
		}
	}
	if(dist[nd]>=INFINITE)
		cout<<"从"<<vexs[st]<<"无法到达"<<vexs[nd]<<endl;
	else
		ShowPath_Tcost(path[nd],st,nd);
}

//最少飞机费用
void MGraph::ShortestCost_A(int st,int nd)
{
	int i,j,v,w,temp;
	double min;
	double* dist=new double[vexnum];
	bool* final=new bool[vexnum];
	bool** path=new bool*[vexnum];
	for(i=0;i<vexnum;i++)
		path[i]=new bool[vexnum];
	for(v=0;v<vexnum;v++)
	{
		final[v]=false;
		dist[v]=arcs[st][v].LowestCost_P(temp); 
		for(w=0;w<vexnum;w++)
			path[v][w]=false;
		if(dist[v]<INFINITE)
		{
			path[v][st]=true;
			path[v][v]=true;
		}
	}
	dist[st]=0;//设置初始值
	final[st]=true;
	//开始主循环
	for(i=1;i<vexnum;i++)
	{
		min=INFINITE;
		for(w=0;w<vexnum;w++)
			if(!final[w])
				if(dist[w]<min)
				{
					v=w;
					min=dist[w];
				}
		final[v]=true;
		for(w=0;w<vexnum;w++)
		{
			if(!final[w] && (min+arcs[v][w].LowestCost_P(temp)<dist[w]))
			{
				dist[w]=min+arcs[v][w].LowestCost_P(temp);
				for(j=1;j<vexnum;j++)
					path[w][j]= path[v][j]; 
				path[w][w]=true;
			}
		}
	}
	if(dist[nd]>=INFINITE)
		cout<<"从"<<vexs[st]<<"无法到达"<<vexs[nd]<<endl;
	else
		ShowPath_Acost(path[nd],st,nd);
}

/////////////////////////////////////////5个显示输出函数/////////////////////////////////////////

bool MGraph::PathEmpty(bool* Path)
{
	int i;
	for(i=0;i<vexnum;i++)
		if(Path[i]==true)
			return false;
	return true;
}

/*void MGraph::ShowPath_Transfer(bool* &Path,int st,int nd)
{
	int curvex,i,j,times=0;

	for(i=0;i<vexnum;i++)
		if(Path[i]==true)
			times++;

	cout<<"城市：";
	cout<<vexs[st];
	Path[st]=false;
	Path[nd]=false;
	curvex=st;

	while(!PathEmpty(Path))
	{
		for(i=0;i<vexnum;i++)
			for(j=0;j<vexnum;j++)
				if(arcs[curvex][i].GetDis()!=INFINITE && Path[j]==true && i==j)
				{
					cout<<setw(12)<<vexs[j];
					Path[j]=false;
					curvex=j;
				}
	}

	cout<<setw(8)<<vexs[nd]<<endl
		<<"总共中转："<<times-1<<"次"<<endl;
}
*/
void MGraph::ShowPath_Ttime(bool* &Path,int st,int nd)
{
	int curvex,i;
	double time,start,temp,last;
	bool *copy=new bool[vexnum];
	
	for(i=0;i<vexnum;i++)
		copy[i]=Path[i];

	for(i=0;i<vexnum;i++)
		if(arcs[st][i].GetDis()!=INFINITE && Path[i]==true)
		{
			time=arcs[st][i].GetFirstTrain();
			start=time;
		}
	cout<<setw(14)<<"出发站："<<setw(12)<<"车次："<<setw(12)<<"目的地："<<setw(12)<<"耗时："<<endl;

	curvex=st;
		
	while(!PathEmpty(Path))
	{
		for(i=0;i<vexnum;i++)
			if(arcs[curvex][i].GetDis()!=INFINITE && Path[i]==true)
			{
				last=time;
				time+=arcs[curvex][i].GetTimeCost_T();
				temp=time;
				time+=arcs[curvex][i].ShortestWait_T(time);
				cout<<setw(12)<<vexs[curvex]<<setw(12)<<(int)last%24
					<<setw(12)<<vexs[i]<<setw(12)<<temp-start<<endl;
				Path[curvex]=false;
				curvex=i;
				if(i==nd) 
					return;
			}
	}
}

void MGraph::ShowPath_Atime(bool* &Path,int st,int nd)
{
	int curvex,i;
	double time,start,temp,last;
	bool *copy=new bool[vexnum];
	
	for(i=0;i<vexnum;i++)
		copy[i]=Path[i];
	
	for(i=0;i<vexnum;i++)
		if(arcs[st][i].GetDis()!=INFINITE && Path[i]==true)
		{
			time=arcs[st][i].GetFirstPlane();
			start=time;
		}

		cout<<setw(14)<<"出发站："<<setw(12)<<"班次："<<setw(12)<<"目的地："<<setw(12)<<"耗时："<<endl;

		curvex=st;
		
		while(!PathEmpty(Path))
		{
			for(i=0;i<vexnum;i++)
				if(arcs[curvex][i].GetDis()!=INFINITE && Path[i]==true)
				{
					last=time;
					time+=arcs[curvex][i].GetTimeCost_P();
					temp=time;
					time+=arcs[curvex][i].ShortestWait_P(time);
					cout<<setw(12)<<vexs[curvex]<<setw(12)<<(int)last%24
						<<setw(12)<<vexs[i]<<setw(12)<<temp-start<<endl;
					Path[curvex]=false;
					curvex=i;
					if(i==nd) 
						return;
				}
		}
}

void MGraph::ShowPath_Tcost(bool* &Path,int st,int nd)
{
	int curvex,i,start;
	double cost=0;
	bool *copy=new bool[vexnum];
	
	for(i=0;i<vexnum;i++)
		copy[i]=Path[i];
		
	cout<<setw(14)<<"出发站："<<setw(12)<<"车次："<<setw(12)<<"目的地："<<setw(12)<<"费用："<<endl;
		
	curvex=st;
		
	while(!PathEmpty(Path))
	{
		for(i=0;i<vexnum;i++)
			if(arcs[curvex][i].GetDis()!=INFINITE && Path[i]==true)
			{
				cost+=arcs[curvex][i].LowestCost_T(start);
				cout<<setw(12)<<vexs[curvex]<<setw(12)<<start
					<<setw(12)<<vexs[i]<<setw(12)<<cost<<endl;
				Path[curvex]=false;
				curvex=i;
				if(i==nd) 
					return;
			}
	}
}

void MGraph::ShowPath_Acost(bool* &Path,int st,int nd)
{
	int curvex,i,start;
	double cost=0;
	bool *copy=new bool[vexnum];
	
	for(i=0;i<vexnum;i++)
		copy[i]=Path[i];
	
	cout<<setw(14)<<"出发站："<<setw(12)<<"班次："<<setw(12)<<"目的地："<<setw(12)<<"费用："<<endl;
	
	curvex=st;
	
	while(!PathEmpty(Path))
	{
		for(i=0;i<vexnum;i++)
			if(arcs[curvex][i].GetDis()!=INFINITE && Path[i]==true)
			{
				cost+=arcs[curvex][i].LowestCost_P(start);
				cout<<setw(12)<<vexs[curvex]<<setw(12)<<start
					<<setw(12)<<vexs[i]<<setw(12)<<cost<<endl;
				Path[curvex]=false;
				curvex=i;
				if(i==nd) 
					return;
			}
	}
}