#include "iostream.h"
#include "fstream.h"
#include "SqStack.h"
#include "stdlib.h"


#define MAX 100000
#define  MAX_VERTEX_NUM 20     
typedef enum  {DG,DN,UDG,UDN} GraphKind;
typedef char VertexType;   
typedef struct {                                
 VertexType vexs[MAX_VERTEX_NUM];                      
 int        arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];   
 int        vexnum,arcnum;                                      
 GraphKind  kind;                           
} MGraph;

int LocateVex(MGraph G,VertexType u)
{
  for(int i=0;i<G.vexnum&&G.vexs[i]!=u;i++);
  if(i==G.vexnum) return FALSE;
  else return i;
}
Status CreateGraph(MGraph &G)
{
  int n;
  cout<<" 0. 有向圖  1. 有向網(wǎng)、 "<<endl;
  cout<<" 2. 無向圖  3. 無向網(wǎng)   "<<endl; 
  cout<<"輸入你要建立的圖的類型:"<<endl;
  cin>>n;
  ifstream istrm;
  switch(n)
  {
  case 0:G.kind=DG;istrm.open("DGraph.txt");break;
  case 1:G.kind=DN;istrm.open("DNet.txt");break;
  case 2:G.kind=UDG;istrm.open("UDGraph.txt");break;
  case 3:G.kind=UDN;istrm.open("UDNet.txt");break;
  }
  istrm>>G.vexnum>>G.arcnum;
  int i,j,k,w;
  VertexType v1,v2;
  for(i=0;i<G.vexnum;i++) istrm>>G.vexs[i];
  if(n%2)
  {
    for(i=0;i<G.arcnum;i++)
  for(j=0;j<G.vexnum;j++)
   G.arcs[i][j]=MAX;
 for(k=0;k<G.arcnum;k++)
 { 
  istrm>>v1>>v2>>w;
  i=LocateVex(G,v1);
        j=LocateVex(G,v2);
  G.arcs[i][j]=w;
  if(n/2) G.arcs[j][i]=w;
 }

  }
  else
  {
    for(i=0;i<G.arcnum;i++)
  for(j=0;j<G.vexnum;j++)
   G.arcs[i][j]=0;
 for(k=0;k<G.arcnum;k++)
 { 
  istrm>>v1>>v2;
  i=LocateVex(G,v1);
        j=LocateVex(G,v2);
  G.arcs[i][j]=1;
  if(n/2) G.arcs[j][i]=1;
 }

  }
  return OK;
}
void OutPut(MGraph G)
{
  cout<<"該圖為";
  switch(G.kind)
  {
  case DG:cout<<"有向圖"<<endl;break;
  case DN:cout<<"有向網(wǎng)"<<endl;break;
  case UDG:cout<<"無向圖"<<endl;break;
  case UDN:cout<<"無向網(wǎng)"<<endl;break;
  }
  cout<<"頂點(diǎn)個(gè)數(shù)為"<<G.vexnum<<endl;
  cout<<"邊的條數(shù)為"<<G.arcnum<<endl;
  int i,j;
  if(G.kind/2)
  {
   for(i=0;i<G.vexnum;i++)
         for(j=0;j<i;j++)
   {
    if(G.arcs[i][j]!=0&&G.arcs[i][j]!=MAX)
    {
     cout<<G.vexs[i]<<" "<<G.vexs[j];
     if(G.kind%2) cout<<" "<<G.arcs[i][j];
     cout<<endl;
    }
   }
  }
  else
  {
    for(i=0;i<G.vexnum;i++)
         for(j=0;j<G.vexnum;j++)
   {
    if(G.arcs[i][j]!=0&&G.arcs[i][j]!=MAX)
    {
     cout<<G.vexs[i]<<" "<<G.vexs[j];
     if(G.kind%2) cout<<" "<<G.arcs[i][j];
     cout<<endl;
    }
   }
  }
}
void DFSTraverse(MGraph G)
{
  int visited[MAX_VERTEX_NUM],i;
  for(i=0;i<G.vexnum;i++)
   visited[i]=0;
  for(i=0;i<G.vexnum;i++)
  {
    if(!visited[i]) continue;
 visited[i]=1;
 cout<<G.vexs[i]<<" ";
  }
}
void MiniTree_PRIM(MGraph G,VertexType u)
{
  struct{
       VertexType adjvex;
       int lowcost;
  }closedge[MAX_VERTEX_NUM];
  int k=LocateVex(G,u);
  int i,j,min;
  for(j=0;j<G.vexnum;j++)
   if(j!=k) {closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[k][j];}
  closedge[k].lowcost=0;
  cout<<"最小生成樹為"<<endl;
  for(i=1;i<G.vexnum;i++)
  { min=MAX;
    for(j=0;j<G.vexnum;j++)
 {   if(closedge[j].lowcost)
    if(closedge[j].lowcost<min) {k=j;min=closedge[j].lowcost;}
 }
 cout<<closedge[k].adjvex<<" "<<G.vexs[k]<<endl;
 closedge[k].lowcost=0;
 for(j=0;j<G.vexnum;j++)
  if(G.arcs[k][j]<closedge[j].lowcost)
  {
   closedge[j].adjvex=G.vexs[k];
   closedge[j].lowcost=G.arcs[k][j];
  }
  }
}
Status TopoSort(MGraph G)
{
  cout<<"拓?fù)渑判蛐蛄袨?;
  int indegree[MAX_VERTEX_NUM]={0};
  int i,j;
  VertexType e;
  for(i=0;i<G.vexnum;i++)//FindInDegree
   for(j=0;j<G.vexnum;j++)
   {
     if(G.arcs[j][i]) indegree[i]++;
   }
  SqStack S;
  InitStack(S);
  for(i=0;i<G.vexnum;i++)
  {
   if(!indegree[i]) {Push(S,G.vexs[i]);}
  }
  int count=0;
  //ofstream ostrm;
  //ostrm.open("TopoOrder.txt");
  while(!StackEmpty(S))
  {
    Pop(S,e);
 cout<<e<<" ";count++;
// ostrm<<e<<" ";
 i=LocateVex(G,e);
 for(j=0;j<G.vexnum;j++)
 {
  if(G.arcs[i][j])
  { 
   if(!(--indegree[j])) Push(S,G.vexs[j]);
  }
  
 }
  }

  if(count<G.vexnum) return ERROR;
  else return OK;
  cout<<endl;
}

Status TopoOrder(MGraph G,SqStack &T,int ve[])
{
  int indegree[MAX_VERTEX_NUM]={0};
  int i,j;
  VertexType e;
  for(i=0;i<G.vexnum;i++)//FindInDegree
   for(j=0;j<G.vexnum;j++)
   {
     if(G.arcs[j][i]!=MAX) indegree[i]++;
   }
  SqStack S;
  InitStack(S);
  for(i=0;i<G.vexnum;i++)
  {
   if(!indegree[i]) {Push(S,G.vexs[i]);}
  }
  int count=0;
  for(i=0;i<G.vexnum;i++)
   ve[i]=0;
  //ofstream ostrm;
  //ostrm.open("TopoOrder.txt");
  while(!StackEmpty(S))
  {
    Pop(S,e);Push(T,e);
    count++;
// ostrm<<e<<" ";
 i=LocateVex(G,e);
 for(j=0;j<G.vexnum;j++)
 {
  if(G.arcs[i][j]!=MAX)
  { 
   if(!(--indegree[j])) Push(S,G.vexs[j]);
   if(ve[i]+G.arcs[i][j]>ve[j]) {ve[j]=ve[i]+G.arcs[i][j];}
   
  }
  
 }
  }
   
  if(count<G.vexnum) return ERROR;
  else return OK;
  cout<<endl;
}
Status CriticalPath(MGraph G)
{
  SqStack T;
  InitStack(T);
  int i,j,k;
  int ee,el;
  int ve[MAX_VERTEX_NUM],vl[MAX_VERTEX_NUM];
  VertexType e;
  if(!TopoOrder(G,T,ve)) return ERROR;
 
  for(i=0;i<G.vexnum;i++)  vl[i]=ve[G.vexnum-1];
  while(!StackEmpty(T))
  {
    Pop(T,e);k=LocateVex(G,e);
 for(j=0;j<G.vexnum;j++)
 {
      if(G.arcs[k][j]!=MAX) 
    if(vl[j]-G.arcs[k][j]<vl[k]) vl[k]=vl[j]-G.arcs[k][j];
 }
  }
  //for(i=0;i<G.vexnum;i++) cout<<" "<<vl[i];exit(1);
  for(i=0;i<G.vexnum;i++)
   for(j=0;j<G.vexnum;j++)
     if(G.arcs[i][j]!=MAX)
  {
    ee=ve[i];el=vl[j]-G.arcs[i][j];
    char tag=(ee==el)?'*':'+';
    cout<<G.vexs[i]<<" "<<G.vexs[j]<<" "<<G.arcs[i][j]<<" "<<tag<<endl;
  }
   return OK;
  
}
void ShortestPath_DIJ(MGraph G,VertexType u)
{
  int v0=LocateVex(G,u);
  bool final[MAX_VERTEX_NUM];
  int P[MAX_VERTEX_NUM],D[MAX_VERTEX_NUM];
  int i,j,min,v;
  for(i=0;i<G.vexnum;i++)
  {
   final[i]=FALSE;D[i]=G.arcs[v0][i];
   if(G.arcs[v0][i]!=MAX) P[i]=v0;
   else P[i]=MAX;
  }
  final[v0]=TRUE;
  P[v0]=v0;
  D[v0]=0;
  for(i=1;i<G.vexnum;i++)
  {
    min=MAX;
 for(j=0;j<G.vexnum;j++)
  if(!final[j])
   if(D[j]<min) {v=j;min=D[j];}
 final[v]=TRUE;
 for(j=0;j<G.vexnum;j++)
  if(!final[j]&&(min+G.arcs[v][j]<D[j]))
  {
    D[j]=min+G.arcs[v][j];
    P[j]=v;
  }//if
  }//for
  for(i=0;i<G.vexnum;i++)
  {
    cout<<G.vexs[i]<<" ";
 j=i;
 while(j!=v0)
 {
   j=P[j];
   cout<<G.vexs[j]<<" ";
  
 }
 cout<<D[i]<<endl;
  }
}//DIJ