routing1.cpp

实现最短路径算法。 实现最短路径算法。

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//This file implement file of the routing program
//It concain functions declared in the roufun.h file
//Program designer：chaidengfeng
//Zhejiang University,Hangzhou,Zhejiang
//e_mail:[e-mail]
//Any question about the program can be asked by sending e_mail to [e-mail]
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include "stdio.h"
#include "stdlib.h"
#include "memory.h"
#include "roufun.h"

DllExport bool routing_short(char *vexFile,char *topoFile,char *attrFile,double xSou,double ySou,double xDes,double yDes,PathsNode **pathDis,PathsNode **pathTim,int N)
{
	
	bool createFlag;
	VexNode *graph;

	graph = (VexNode *)malloc(sizeof(VexNode));
	if(graph == 0)
		return false;

   //	createFlag = graph_construct(vexFile,topoFile,attrFile,&graph);
	createFlag = create_test(&graph,vexFile,topoFile);
	if(!createFlag)
	{
		graph_destruct(graph);
		return false;
	}

        int souNo,desNo;
        bool shortFlag;
	souNo = get_vexNo(graph,xSou,ySou);
	desNo = get_vexNo(graph,xDes,yDes);
	if(souNo == NOVERTEX || desNo == NOVERTEX )
	{
		graph_destruct(graph);
		return false;
	}
        
	//DISTANCE
	shortFlag = graph_Dij_N(graph,souNo,desNo,DISTANCE,pathDis,N);
	//TIME
	shortFlag = graph_Dij_N(graph,souNo,desNo,TIME,pathTim,N);

	graph_destruct(graph);
	if(shortFlag)
		return true;
	else
		return false;
}
/////////////////////////////////////////////////////////////////
//
/////////////////////////////////////////////////////////////////
bool graph_construct(char *vexFile,char *topoFile,char *attrFile,VexNode **graph)
{
	//file name is null
	if(!vexFile || !topoFile || !attrFile)
		return false;
	
	//open files
	FILE *vexFp,*topoFp,*attrFp;
	if(!(vexFp = fopen(vexFile,"r")))
		return false;
	if(!(topoFp = fopen(topoFile,"r")))
		return false;
	if(!(attrFp = fopen(attrFile,"r")))
		return false;
	
	//construct the graph
	if(!(Set_Vex(vexFp,graph)))
		return false;
	if(!(Set_Topo(topoFp,graph)))
		return false;
	if(!(Set_Attr(attrFp,graph)))
		return false;
	if(!(complement(graph)))
		return false;
	
	//close files
	if(vexFp)
		fclose(vexFp);
	if(topoFp)
		fclose(topoFp);
	if(attrFp)
		fclose(attrFp);

	return true;
}
/////////////////////////////////////////////////////////////////
//graph destroy function
/////////////////////////////////////////////////////////////////
DllExport bool graph_destruct(VexNode *graph)
{
	VexNode *currVex,*nextVex;
	ArcNode *currArc,*nextArc;
	currVex = graph;
	while(currVex)
	{
		nextVex = currVex->nextVex;
		currArc = currVex->firstArc;
		while(currArc)
		{
			nextArc = currArc->nextArc;
			free(currArc);
			currArc = nextArc;
		}
		free(currVex);
		currVex = nextVex;
	}
	return true;
}
/////////////////////////////////////////////////////////////////
//path destroy function
/////////////////////////////////////////////////////////////////
DllExport bool path_destruct(PathsNode *path)
{
	PathsNode *currPaths,*nextPaths;
	PathNode  *currPath ,*nextPath;
	currPaths = path;
	while(currPaths)
	{
		nextPaths = currPaths->next;
		currPath = currPaths->path;
		while(currPath)
		{
			nextPath = currPath->next;
			free(currPath);
			currPath = nextPath;
		}
		free(currPaths);
		currPaths = nextPaths;
	}
	return true;
}
/////////////////////////////////////////////////////////////////
//This is the function that find the nearest vertex to point(x,y)
/////////////////////////////////////////////////////////////////
DllExport int get_vexNo(VexNode *graph,double x,double y)
{
	double distance,minDis;
	double dx,dy;
	VexNode *currVex,*minVex;
	currVex = graph;
	if(currVex == 0)
		return NOVERTEX;
	dx = currVex->info.x - x;
	dy = currVex->info.y - y;
	minDis = dx*dx+dy*dy;
	minVex = currVex;
	currVex = currVex->nextVex;
	while(currVex)
	{
		dx = currVex->info.x - x;
		dy = currVex->info.y - y;
		distance = dx*dx+dy*dy;
		if(distance < minDis)
		{
			minDis = distance;
			minVex = currVex;
		}
		currVex = currVex->nextVex;
	}
	return minVex->vexNo;
}
///////////////////////////////////////////////////////////////
//N_shortest path find function
///////////////////////////////////////////////////////////////
DllExport bool graph_Dij_N(VexNode *graph,int souNo,int desNo,int kind,PathsNode **pathCost,int N)
{
	int i,j,k,kk;
	int short_count = 0;
	int headVexNo,tailVexNo;
	double tempCost[MAX_LENGTH],minCost;

	int cut_headNo[MAX_N][MAX_LENGTH],cut_temp_head[MAX_LENGTH];
	int cut_tailNo[MAX_N][MAX_LENGTH],cut_temp_tail[MAX_LENGTH];
	
	ArcNode *currArc;
	VexNode *currVex;
	PathsNode *currPaths,*nextPaths,*insertPaths;
	PathNode  *currPath, *nextPath ,*tempPath;

	///////////////////////////////////////////////
	//initialize
	///////////////////////////////////////////////
	for(i=0;i<MAX_N;i++)
	{
		for(j=0;j<MAX_LENGTH;j++)
		{
			cut_headNo[i][j] = NOVERTEX;
			cut_tailNo[i][j] = NOVERTEX;
		}
	}
	for(j=0;j<MAX_LENGTH;j++)
	{
		cut_temp_head[j] = NOVERTEX;
		cut_temp_tail[j] = NOVERTEX;
	}
	//get paths
	do{
		//get 1-shortest 
		if(short_count == 0)
		{
			tempPath = (PathNode*)malloc(sizeof(PathNode));
			if(tempPath == 0)
				return false;
			if(!(graph_Dij(graph,souNo,desNo,&minCost,kind,&tempPath)))
				return false;
			if(tempPath == 0)
			{
				*pathCost = 0;
				break;
			}
			insertPaths = (PathsNode*)malloc(sizeof(PathsNode));
			if(insertPaths == 0)
				return false;
			insertPaths->pathNo   = 1;
			if(kind == DISTANCE)
			{
				insertPaths->distance = minCost;
				insertPaths->time = 0;
			}
			else
			{
				insertPaths->distance = 0;
				insertPaths->time = minCost;
			}
			insertPaths->path     = tempPath;
			insertPaths->next     = 0;
			*pathCost = insertPaths;

		}
		//get 2 3 . . .-shortest 
		else
		{
			//get path;
			currPaths = *pathCost;
			while(currPaths && currPaths->pathNo != short_count)
				currPaths = currPaths->next;
			if(currPaths == 0)
				break;
			else
			{
				currPath = currPaths->path;
				while(currPath->next)
				{
					//record the head and tail vertex No.
					nextPath = currPath->next;
					headVexNo = currPath->vexNo;
					tailVexNo = nextPath->vexNo;
					int cut_count = 0;
					for(j=0;j<MAX_LENGTH;j++)
					{
						cut_count++;
						cut_temp_head[j] = cut_headNo[short_count-1][j];
						cut_temp_tail[j] = cut_tailNo[short_count-1][j];
						if(cut_temp_tail[j] == NOVERTEX)
						{
							//add to cut arc recorder
							cut_temp_head[j] = headVexNo;
							cut_temp_tail[j] = tailVexNo;
							break;
						}
					}
					//cut arcs recorded by the cut recorder
					for(j=0;j<cut_count;j++)
					{
						headVexNo = cut_temp_head[j];
						tailVexNo = cut_temp_tail[j] ;
						currVex = graph;
						while(currVex && currVex->vexNo != headVexNo)
							currVex = currVex->nextVex;
						currArc = currVex->firstArc;
						while(currArc && currArc->info.tailVexNo != tailVexNo)
							currArc = currArc->nextArc;
						if(currVex->vexNo == headVexNo && currArc->info.tailVexNo == tailVexNo)
						{
							if(kind == DISTANCE)
							{
								tempCost[j] = currArc->info.distance;
								currArc->info.distance = MAXCOST;
							}
							else if(kind == TIME)
							{
								tempCost[j] = currArc->info.time;
								currArc->info.time = MAXCOST;
							}
						}
					}
					//get shortest path in the state of arcs cutted
					tempPath = (PathNode*)malloc(sizeof(PathNode));
					if(tempPath == 0)
						return false;
					if(!(graph_Dij(graph,souNo,desNo,&minCost,kind,&tempPath)))
						return false;
					//come back to fore state
					for(j=0;j<cut_count;j++)
					{
						headVexNo = cut_temp_head[j];
						tailVexNo = cut_temp_tail[j] ;
						currVex = graph;
						while(currVex && currVex->vexNo != headVexNo)
							currVex = currVex->nextVex;
						currArc = currVex->firstArc;
						while(currArc && currArc->info.tailVexNo != tailVexNo)
							currArc = currArc->nextArc;
						if(currVex->vexNo == headVexNo && currArc->info.tailVexNo == tailVexNo)
						{
							if(kind == DISTANCE)
							{
								currArc->info.distance = tempCost[j];
								tempCost[j] = 0.0;
							}
							else if(kind == TIME)
							{
								currArc->info.time = tempCost[j];
								tempCost[j] = 0.0;
							}
						}
					}
					//compare and exchange
					if(tempPath != 0)
					{
						//continue;
						currPaths = *pathCost;
						if(kind == DISTANCE)
						{
							while(currPaths->next && currPaths->next->distance < minCost)
								currPaths = currPaths->next;
						}
						else if(kind == TIME)
						{
							while(currPaths->next && currPaths->next->time < minCost)
								currPaths = currPaths->next;
						}
						if(currPaths->pathNo < N)
						{
							nextPaths = currPaths->next;
							insertPaths = (PathsNode*)malloc(sizeof(PathsNode));
							if(insertPaths == 0)
								return false;
							insertPaths->pathNo   = currPaths->pathNo+1;
							if(kind == DISTANCE)
							{
								insertPaths->distance = minCost;
								insertPaths->time = 0;
							}
							else
							{
								insertPaths->distance = 0;
								insertPaths->time = minCost;
							}
							insertPaths->path     = tempPath;
							insertPaths->next     = nextPaths;
							currPaths->next = insertPaths;
							currPaths = nextPaths;
							while(currPaths)
							{
								currPaths->pathNo++;
								if(currPaths && currPaths->pathNo>N)
								{
									path_destruct(currPaths);
									break;
								}
								else
									currPaths = currPaths->next;
							}
							for(k = N-1;k >= insertPaths->pathNo;k--)
							{
								for(kk=0;kk<MAX_LENGTH;kk++)
								{
									cut_headNo[k][kk] = cut_headNo[k-1][kk];
									cut_tailNo[k][kk] = cut_tailNo[k-1][kk];
								}
							}
							for(kk=0;kk<MAX_LENGTH;kk++)
							{
								cut_headNo[insertPaths->pathNo-1][kk] = cut_temp_head[kk];
								cut_tailNo[insertPaths->pathNo-1][kk] = cut_temp_tail[kk];
							}
							break;
						}
					}
					currPath = nextPath;
				}
			}
		}
		short_count++;
	}while(short_count < N);
	return true;
}
/////////////////////////////////////////////////////////////////////
//construct graph
/////////////////////////////////////////////////////////////////////
bool Set_Vex(FILE *vexFp,VexNode **graph)
{
	int      vexNo,count;
	char     vexName[MAXNAME],desp[MAXDESCRIPTION];
	double   x,y;
	VexNode  *currVex,*nextVex;

	count = 0;
	nextVex = 0;
	while(!feof(vexFp))
	{
		memset(vexName,'\0',MAXNAME);
		if(fscanf(vexFp,"%d %s %lf %lf %s",&vexNo,vexName,&x,&y,desp) == 5)//扔掉一个变量
		{
			nextVex  = (VexNode *)malloc(sizeof(VexNode));
			if(nextVex == 0)
				return false;
			nextVex->vexNo  = vexNo;
			memcpy(nextVex->info.vexName,vexName,MAXNAME);
			nextVex->info.x = x;
			nextVex->info.y = y;
			nextVex->firstArc = 0;
			nextVex->nextVex = 0;
			if(count == 0)
			{
				*graph = nextVex;
				currVex = nextVex;
			}
			else
			{
				currVex->nextVex = nextVex;
				currVex = nextVex;
			}
			count++;
		}
		else
			return false;
	}
	return true;
}
//////////////////////////////////////////////////////////////////
//topo information 
//this function is really construct the graph
/////////////////////////////////////////////////////////////////
bool Set_Topo(FILE *topoFp,VexNode **graph)
{
	int      i;
	bool     addFlag;
	int      arcNo,souNo,desNo;
	char     arcName[MAXNAME];
	double   x1,y1,x2,y2;
	VexNode  *currVex;
	ArcNode  *currArc,*nextArc;
	currArc = 0;
	nextArc = 0;
	while(!feof(topoFp))
	{
		memset(arcName,'\0',MAXNAME);
		if(fscanf(topoFp,"%d %s %d %lf %lf %d %lf %lf",&arcNo,arcName,&souNo,&x1,&y1,&desNo,&x2,&y2) == 8)
		{
			currVex = *graph;
			while(currVex->vexNo != souNo && currVex->nextVex)
				currVex = currVex->nextVex;
			if(currVex->vexNo != souNo)
				return false;
			addFlag = false;
			currArc = currVex->firstArc;
			if(!currArc)
				addFlag = true;
			else
			{
				while(currArc->nextArc && currArc->arcNo != arcNo)
					currArc = currArc->nextArc;
				if(currArc->arcNo == arcNo)
				{
					currArc->arcNo   = arcNo;
					currArc->info.tailVexNo    = desNo;
					memcpy(currArc->info.arcName,arcName,MAXNAME);