#include"圖.h"

void InitGraph(Graph&g)
{
  g.vexNum=0;
  g.edgeNum=0;
  for(int i=0;i<MAXVTXNUM;i++)
  {
    g.Adjmulist[i].firstEdge=NULL;
  }
}

int LocateVex(Graph&g,char*uname)
{
  int i;
  for(i=0;i<g.vexNum;i++)
  {if(!(strcmp(uname,g.Adjmulist[i].data.name)))return --i;}
  return -1;
}

void GetVex(Graph g,int i,VertexType&v)
{
  v=g.Adjmulist[i].data;
}

EdgePtr FirstEdge(Graph g,int vi)
{
	//返回個(gè)中指向依附于頂點(diǎn)vi的第一條邊的指針
  return g.Adjmulist[vi].firstEdge;
}//FirstEdge

void NextEdge(Graph g,int vi,EdgePtr p,EdgePtr&q)
{
	//以vj返回g中依附于頂點(diǎn)vi的一條邊的另一端點(diǎn)
	//以q返回g中依附于頂點(diǎn)vi相對(duì)于p所指邊的下一條邊
	if(p->elem.ivex==vi){ q=p->ilink; }
	else {q=p->jlink; }
}//NextEdge

void InsertVex(Graph&g,VertexType v)
{
	//在圖g的鄰接多重表中添加一個(gè)頂點(diǎn)e
  g.Adjmulist[g.vexNum].data=v;
  g.Adjmulist[g.vexNum].firstEdge=NULL;
  g.vexNum++;
}//InsertVex

void InsertEdge(Graph&g,EdgeType e)
{
    //在圖g的鄰接多重表中添加一條邊e
  EdgePtr p=(EdgePtr)malloc(sizeof(EdgeNode));
  p->elem=e;
  p->ilink=FirstEdge(g,e.ivex);
  p->jlink=FirstEdge(g,e.jvex);
  p->tag=0;
  g.Adjmulist[e.ivex].firstEdge=p;
  g.Adjmulist[e.jvex].firstEdge=p;
  g.edgeNum++;
}//InsertEdge

int CreateGraph(Graph&g,char*str)
{
	//建立圖的多重鄰接表
  ifstream fin(str);
  if(fin.fail()){cout<<"輸入的文件名錯(cuò)誤！";return 0;}
  int vn,en;
  fin>>vn>>en;
  VertexType v;
  EdgeType e;
  for(int i=0;i<vn;i++)
  {
    fin>>v.name>>v.info;
	InsertVex(g,v);
  }
  for(i=0;i<en;i++)
  {
    fin>>e.ivex>>e.jvex>>e.length;
	if(e.length)InsertEdge(g,e);
  }
  fin.close();
  return 1;
}//CreateGraph

void ShowVex(Graph g,int vi)
{
	if(vi>=g.vexNum){cout<<"\n此處景點(diǎn)是不存在的！"; return;}
    cout<<endl<<"此處景點(diǎn)名為："<<g.Adjmulist[vi].data.name<<endl<<"次處景點(diǎn)信息："<<g.Adjmulist[vi].data.info<<endl;
}//ShowVex

void ShowGraph(Graph&g)
{
  EdgePtr e=NULL,p=NULL;
  if(g.vexNum==0){cout<<"\n校園景點(diǎn)信息還沒有創(chuàng)建！";return;}
  cout<<"\n已經(jīng)創(chuàng)建好了的的校園景點(diǎn)以及其路徑如下所示：\n";
  cout<<"\n景點(diǎn)的編號(hào)\t景點(diǎn)的名稱\n";
  for(int i=0;i<g.vexNum;i++)
  { 
    cout<<i<<"\t\t"<<g.Adjmulist[i].data.name<<endl;
  }
  cout<<"\n路徑（景點(diǎn)1編號(hào)，景點(diǎn)2編號(hào)）\t路徑長度\n";
  for(i=0;i<g.vexNum;i++)
  {
	 e=FirstEdge(g,i);
     while(e!=NULL)
	 {   
		 if(e->tag==0)
		 {
			cout<<"\n（"<<e->elem.ivex<<","<<e->elem.jvex
		    	<<"）\t\t\t\t"<<e->elem.length ;
		 }
		 e->tag=1;
		 NextEdge(g,i,e,e);
	 }
  }
  cout<<endl;
}//ShowGraph