//* * * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :5  (5_4)                     *
//*PROGRAM          :關鍵路徑	                  *
//*CONTENT          :拓撲排序，關鍵路徑           *
//* * * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 30 //圖的最大頂點數
#define MAX 30            //棧的最大容量
#define INFINITY 30000;   //定義最大的最遲發生時間
enum BOOL {False,True};
typedef struct ArcNode
{int adjvex;              //該弧所指向的頂點的位置
 int weight;              //該弧所代表的活動的持續時間
 struct ArcNode *nextarc; //指向下一條弧的指針
}ArcNode;       //弧結點
typedef struct
{int indegree[MAX_VERTEX_NUM]; //存放各頂點的入度
 ArcNode* AdjList[MAX_VERTEX_NUM]; //指向第一條依附該頂點的弧的指針
 int vexnum,arcnum;                //圖的當前頂點和弧數
}Graph;
typedef struct    //定義堆棧結構
{int elem[MAX];   //棧區
 int top;         //棧頂指針
}Stack;
int ve[MAX_VERTEX_NUM];  //全局變量，存放各頂點的最早發生時間
void CreateGraph(Graph &);    //生成圖的鄰接表
BOOL CriticalPath(Graph);     //求圖的關鍵路徑
BOOL TopologicalSort(Graph,Stack &T);  //進行拓撲排序
void FindInDegree(Graph&);    //求圖各頂點的入度
void Initial(Stack &);     //初始化一個堆棧
BOOL Push(Stack &,int);  //將一個元素入棧
BOOL Pop(Stack&,int &);  //將一個元素出棧
BOOL Gettop(Stack,int&); //得到棧頂元素
BOOL StackEmpty(Stack);  //判斷堆棧是否為空
void main()
{Graph G;  //采用鄰接表結構的圖
 char j='y';
 BOOL temp;
 textbackground(3);  //設定屏幕顏色
 textcolor(15);
 clrscr();
 //------------------程序解說----------------------------
 printf("本程序將演示構造圖的關鍵路徑.\n");
 printf("首先輸入圖的頂點數和弧數.\n格式：頂點數，弧數；例如:6,8\n");
 printf("接著輸入各弧(弧尾,弧頭)和權值.\n格式：弧尾，弧頭，權值；例如:\n1,2,3\n1,3,2\n");
 printf("2,5,3\n5,6,1\n2,4,2\n4,6,2\n3,4,4\n3,6,3\n");
 printf("程序將會構造該圖并找出其關鍵路徑.\n");
 printf("關鍵路徑:\n1->3  2\n3->4  4\n4->5  2\n");
 //------------------------------------------------------
 while(j!='N'&&j!='n')
      {CreateGraph(G);          //生成鄰接表結構的圖
       temp=CriticalPath(G);    //尋找G的關鍵路徑
       if(temp==False) printf("該圖有回路!\n");
		 //若返回為False,表明該圖存在有環路
       else printf("該圖沒有回路!\n");
       printf("關鍵路徑演示完畢，繼續進行嗎?(Y/N)");
       scanf(" %c",&j);
     }
}

BOOL CriticalPath(Graph G)
{//G為有向網，輸出G的各項關鍵活動
 int j,dut,k,ee,el;
 int vl[MAX_VERTEX_NUM]; //存放各頂點的最遲發生時間
 Stack T;     //堆棧T存放拓撲排序的頂點序列
 ArcNode*p;
 Initial(T);  //初始化堆棧T
 if(!TopologicalSort(G,T)) return False; 
    //利用拓撲排序求出各頂點的最早發生時間，并用T返回拓撲序列，
    //若返回False，表明該網有回路
 printf("Critical Path:\n");
 Gettop(T,k); //k取得拓撲序列的最后一個頂點，即該網的匯點
 vl[k]=ve[k]; //匯點的vl=ve
 for(j=1;j<=G.vexnum;j++) if(j!=k) vl[j]=INFINITY; //將其他的頂點的vl置為IFINITY
 while(!StackEmpty(T)) //按拓撲逆序求各頂點的vl值
  {Pop(T,j);
   for(p=G.AdjList[j];p;p=p->nextarc)
     {k=p->adjvex;
      dut=p->weight;
      if(vl[k]-dut<vl[j]) vl[j]=vl[k]-dut;  
         //vl的求法：vl(i)=Min{vl(j)-dut(<i,j>)} <i,j>∈S,i=n-2,...0
     }
  }
 for(j=1;j<=G.vexnum;j++)  //求每條弧的最早開始時間ee和最遲開始時間el
   for(p=G.AdjList[j];p;p=p->nextarc)
      {k=p->adjvex;
       dut=p->weight;
       ee=ve[j];
       el=vl[k]-dut;
       if(ee==el) printf("%d->%d%5d\n",j,k,dut); //若ee=el，則該弧為關鍵活動
      }
 return True;
}
void CreateGraph(Graph &G)
{//構造鄰接表結構的圖G
 int i;
 int start,end,arcweight;
 ArcNode *s;
 printf("請輸入頂點數和弧數(頂點數，弧數):");
 scanf("%d,%d",&G.vexnum,&G.arcnum); //輸入圖的頂點數和弧數
 for(i=1;i<=G.vexnum;i++) G.AdjList[i]=NULL; //初始化指針數組
 printf("請輸入各弧和權值，格式:弧尾,弧頭,權值\n");
 for(i=1;i<=G.arcnum;i++)
   {scanf("%d,%d,%d",&start,&end,&arcweight); 
        //輸入弧的起點和終點即該弧所代表的活動的持續時間
    s=(ArcNode *)malloc(sizeof(ArcNode)); //生成一個弧結點
    s->nextarc=G.AdjList[start]; //插入到鄰接表中
    s->adjvex=end;
    s->weight=arcweight;
    G.AdjList[start]=s;
   }
}

BOOL TopologicalSort(Graph G,Stack &T)
{//有向網G采用鄰接表存儲結構，求各頂點事件的最早發生時間ve，
 //T為拓撲序列頂點棧，S為零入度頂點棧。
 //若G無回路，則用棧返回G的一個拓撲序列，且函數返回True,否則返回False
 int i,k;
 int count; //計數器
 ArcNode* p;
 Stack S;
 FindInDegree(G); //求出圖中各頂點的入度
 Initial(S);      //堆棧初始化，存放入度為零的頂點
 for(i=1;i<=G.vexnum;i++)
  if(!G.indegree[i]) Push(S,i); //入度為零的頂點入棧
 count=0;     //對輸出頂點記數
 for(i=1;i<=G.vexnum;i++)
   ve[i]=0;   //ve初始化 
 while(!StackEmpty(S))
  {Pop(S,i);  //i號頂點出S棧并入T棧，count記數
   Push(T,i); 
   count++;
   for(p=G.AdjList[i];p;p=p->nextarc)
     {k=p->adjvex;       //對i號頂點的每個鄰接頂點的入度減一
      if(!(--G.indegree[k])) Push(S,k); //若入度為零，入棧
      if((ve[i]+p->weight)>ve[k]) ve[k]=ve[i]+p->weight;
             //修改k號頂點的最遲發生時間
             //ve的求法：ve(j)=Max{ve(i)+dut(<i,j>)} <i,j>∈S,j=1,2,…,n-1
     }
  }
 if(count<G.vexnum) return False; //如輸出頂點數少于圖中頂點數，則該圖有回路
 else return True;
}
void FindInDegree(Graph &G)
{//求出圖G的各頂點的入度，存放在G.indegree[1..G.vexnum]中
 int i;
 ArcNode* p;
 for(i=1;i<=G.vexnum;i++)
   G.indegree[i]=0;
 for(i=1;i<=G.vexnum;i++)
    {
     for(p=G.AdjList[i];p;p=p->nextarc)
       G.indegree[p->adjvex]++;  //弧頭頂點的入度加一
    }
}
void Initial(Stack &S)
{S.top=-1;   //棧頂指針初始化為-1
}

BOOL Push(Stack &S,int ch)
{//將元素ch入棧，成功返回True,失敗返回False
 if(S.top>=MAX-1) return False;//判斷是否棧滿
 else {S.top++;               //棧頂指針top加一
       S.elem[S.top]=ch;      //入棧
       return True;
      }
}

BOOL Pop(Stack &S,int &ch)
{//將棧頂元素出棧,成功返回True，并用ch返回該元素值，失敗返回False
 if(S.top<=-1) return False;//判斷是否棧空
 else {S.top--;                                //棧頂指針減一
       ch=S.elem[S.top+1];
       return True;
      }
}
BOOL Gettop(Stack S,int &ch)
{//取得棧頂元素，成功返回True，并用ch返回該元素值，失敗返回False
 if(S.top<=-1)
    return False;
 else {ch=S.elem[S.top];//顯示棧頂元素
       return True;
      }
}
BOOL StackEmpty(Stack S)
{//判斷堆棧是否已空，若空返回True,不空返回False
 if(S.top<=-1) return True;
 else return False;
}