#include "stdio.h"
#include "iostream.h"
#include "fstream.h"                    //輸入輸出流
#include "stdlib.h"
#include "math.h"
#include "time.h"

#define mvnum 100                        //最大頂點數(shù)
#define minint 0
#define maxnum  1600
#define M     0
#define N      2
//#define R      q/c                       //路阻參數(shù)R=q/c,即流量通行能力之比

typedef char vertextype;
typedef int adjmatrix;

struct mgraph
{
	vertextype vexs[mvnum];               //頂點數(shù)組
	adjmatrix arcs[mvnum][mvnum];         //鄰接矩陣
};

int d[mvnum][mvnum],p[mvnum][mvnum];
////////////

//路網(wǎng)構(gòu)造方法函數(shù)
void CreateMgraph(mgraph *G)
{
	//采用鄰接矩陣表示法構(gòu)造無向圖G
	int i,j,k,w;
	ifstream graphlist("map.txt",ios::in  );//定義一個流對象，并且和文件關(guān)聯(lián)
	for(i=1;i<=9;i++)
		G->vexs[i]=(char)i;
	for(i=1;i<=9;i++)
		for(j=1;j<=9;j++)
			G->arcs[i][j]=minint;           //初始化鄰接矩陣		
		for(k=1;k<=12;k++)
		{
			//從磁盤文件接受數(shù)據(jù)構(gòu)造網(wǎng)
			graphlist>>i;
			graphlist>>j;
			graphlist>>w;		   
			G->arcs[i][j]=w;
			G->arcs[j][i]=G->arcs[i][j];    //構(gòu)造無向網(wǎng)
		}
		
		
		//cout<<"圖的存儲結(jié)構(gòu)建立完畢！"<<endl;
		graphlist.close();                  //關(guān)閉文件
}
//道路類型定義
struct Result{
    double x;
	double y;
	int z;
};


struct Result RoadType(int Flag)
{   
	struct Result r;
	
	if (Flag==1)
	{
		r.x=1.726;
		r.y=3.15;
		r.z=68;

	}
	else if (Flag==2)
	{
		r.x=2.076;
		r.y=2.870;
		r.z=56;
	}

	return r;

}

//測試代碼，產(chǎn)生區(qū)間隨機數(shù)
/*int main(void)                        
{
	int i,Y=99,X=0,k;
	time_t t;
	srand((unsigned) time(&t));
	
	cout<<"Ten random numbers from 0 to 99\n\n";
	for(i=0; i<10; i++)
	{k=rand()%(Y-X+1)+X;
	printf("%d\n", k);
	}
	return 0;
}*/

//自定義的隨機數(shù)產(chǎn)生函數(shù)
int MyRand(int X,int Y)               
{

  int k;
  time_t t;
  srand((unsigned) time(&t));
       k=rand()%(Y-X+1)+X;            //產(chǎn)生[X,Y]之間的隨機數(shù)
  return(k);
}

//隨機產(chǎn)生車的數(shù)量及速度并計算其平均速度返回
double CarSpeed(int Flag)                        
{
	int i=0,k=0;
	int carnum,V0;
	double carspeed,sum=0;
	time_t t;
    struct Result r;
    
	srand((unsigned) time(&t));
	carnum=MyRand(0,1600); 
	//cout<<carnum<<endl;                   //隨機產(chǎn)生車輛的數(shù)量

    r=RoadType(Flag);
	V0=r.z;
	carspeed=MyRand(0,V0);
	//carspeed=rand()%(V0+1);
	//cout<<carspeed<<endl;
	/*for (i=0;i<=carnum;i++)
	{
		k=rand()%V0;                     //隨機產(chǎn)生車輛的速度
		//cout<<k<<endl;
		sum+=k;

	}
	
	carspeed=sum/carnum; */                //該路段上車輛的時間平均速度
	//cout<<carspeed<<endl;

	return(carspeed);

}

//測試代碼 二分法求解非線性方程
/*float Erfenfa(float m,float n)
{
	float x0,x1,x2,fx0,fx1,fx2;
	do
	{	x1=m;x2=n;
	fx1=x1*x1*x1-x1-1;
	fx2=x2*x2*x2-x2-1;
	}
	while(fx1*fx2>0);
	do
	{	x0=(x1+x2)/2;
	fx0=x0*x0*x0-x0-1;
	if((fx0*fx1)<0)
	{	x2=x0;
	fx2=fx0;
	}
	else
	{	x1=x0;
	fx1=fx0;
	}
	}
	while(fabs(fx0)>=0.0001);
	return x0;
	
}*/

//非線性方程求解算法
double Erfenfa(double V,double a,double b,int V0)
{
	double n0,n1,n2;
	double x0,x1,x2,fx0,fx1,fx2;
	do
	{	x1=M;x2=N;
	    n1=a+b*pow(x1,3);
		fx1=V0/(1+pow(x1,n1))-V;
		n2=a+b*pow(x2,3);
	    fx2=V0/(1+pow(x2,n2))-V;
	}
	while(fx1*fx2>0);
	do
	{	x0=(x1+x2)/2; 
	    
	    n0=a+b*pow(x0,3);
	    fx0=V0/(1+pow(x0,n0))-V;

	if((fx0*fx1)<0)
	{	x2=x0;
	fx2=fx0;
	}
	else
	{	x1=x0;
	fx1=fx0;
	}
	}
	while(fabs(fx0)>=0.0001);
	return x0;
 

}


//利用交通流理論中的速度流量模型計算路阻參數(shù)R
double CalR(int Flag)
{
	double R;
	double V;
	double a,b;
	int V0;
	struct Result r;
	
   	V=CarSpeed(Flag);
	r=RoadType(Flag);
	a=r.x;
	b=r.y;
	V0=r.z;
    //cout<<a<<endl;
    //cout<<b<<endl;
	//cout<<V0<<endl;
	//cout<<v<<endl;
	R=Erfenfa(V,a,b,V0);             //速度流量模型，利用速度反推流量  
	//cout<<R<<endl;
              
	return(R);
	
}
 
//利用路阻參數(shù)判斷交通流狀態(tài)
void StaJud(int Flag)                               
{
	double R;
	R=CalR(Flag);
	
	if (R<0.4)
	{
		cout<<"非常暢通";
		cout<<" ";
	}
	else if (R>0.4&&R<0.6)
	{
		cout<<"暢通    ";
		cout<<" ";
	}
	else if (R>0.6&&R<0.75)
	{
		cout<<"一般暢通";
		cout<<" ";
	}
	else if (R>0.75&&R<0.9)
	{
        cout<<"擁堵    ";
		cout<<" ";
	}
	else if(R>0.9&&R<1.0)
	{
        cout<<"非常擁擠";
		cout<<" ";
		
	}
	else if (R>1.0)
	{
		 cout<<"堵塞    ";
		 cout<<" ";
	}
	else
	{
		cout<<"DO NOTHING"<<endl;
	}
 
}

//路網(wǎng)操作函數(shù),單條路段上仿真擁堵狀況
void RoadSinOper(mgraph *G,int v,int w)
{
	int i,j;
	for(i=1;i<=9;i++)
		for(j=1;j<=9;j++)
		{
			if(G->arcs[i][j]!=minint)
				p[i][j]=j;
			else
				p[i][j]=0;
			d[i][j]=G->arcs[i][j];    //路段的權(quán)值即道路類型存入數(shù)組
		}
        
		if (d[v][w]==0)
		{
			cout<<"無此路段，重新輸入!"<<endl;
		}
		else
		{
			StaJud(d[v][w]);
			cout<<""<<endl;
		}
   

}
//顯示整個路網(wǎng)每條路段擁堵
void RoadAllOper(mgraph *G)
{
	int i,j;
    int count=0; 
	for(i=1;i<=9;i++)
		for(j=1;j<=9;j++)
		{
			if(G->arcs[i][j]!=minint)
				p[i][j]=j;
			else
				p[i][j]=0;
			d[i][j]=G->arcs[i][j];    
		}

	for(i=1;i<=9;i++)
		for(j=i;j<=9;j++)
		{
			if (d[i][j]==0)
			{
				cout<<"";
				continue;
			}
			else
			{ 
				if (count%4==0)
				{
					cout<<""<<endl;
				}
			
				cout<<"節(jié)點"<<i;
				cout<<"->節(jié)點"<<j;
			    StaJud(d[i][j]);
				count++;
			}

		}
		cout<<""<<endl;
		cout<<""<<endl;
        cout<<""<<endl;
}

//主函數(shù),顯示整個路網(wǎng)每個路段的擁堵狀況及查詢特定路段擁堵
void main()
  {
	mgraph *G;
	int v,w,k;
	int xz=1;
 
	G=(mgraph *)malloc(sizeof(mgraph));         //為路網(wǎng)分配存儲空間
	cout<<"歡迎進入道路網(wǎng)實時擁堵狀態(tài)顯示查詢系統(tǒng)."<<endl;
	cout<<endl;
	cout<<"節(jié)點名稱及編號如下"<<endl;
	cout<<" 1 節(jié)點1   2 節(jié)點2  3 節(jié)點3  "<<endl;
	cout<<" 4 節(jié)點4   5 節(jié)點5  6 節(jié)點6  "<<endl;
	cout<<" 7 節(jié)點7   8 節(jié)點8  9 節(jié)點9  "<<endl;
	CreateMgraph(G);

	while(xz!=0)
	{
		cout<<"**********實時擁堵狀態(tài)顯示**********"<<endl;
		cout<<"================================"<<endl;
		cout<<"請選擇：1  顯示   2   查詢   0  結(jié)束"<<endl;
		cout<<"================================"<<endl;
		cin>>xz;
		cout<<endl;
		if(xz==2)
		{   
		
            cout<<"請輸入源點和終點: "<<endl;
			cin>>v>>w; 
			k=G->arcs[v][w];
		//	cout<<k<<endl;
            cout<<"該路段的擁堵狀態(tài)："<<endl;
			RoadSinOper(G,v,w);
		}
		else if (xz==1)
		{

			RoadAllOper(G);
		} 
		else if (xz==0)
		{
              cout<<"謝謝使用，祝您生活愉快！"<<endl;
		}

	}

}