#include<iostream>
#include<stdio.h>
#include<conio.h>
#include<windows.h>
#include<malloc.h>
#define MAX_VEXTEX_NUM 20
using namespace std;
//==========================================================================================================================//
typedef struct edgenode
{   int endvex;   /*相邻顶点在顶点表中的下标*/
int weight;   /*边的权值*/
struct edgenode *nextedge;   /*链字段*/
}  EdgeNode,*EdgeList;  /*边表中的结点*/

typedef struct
{  int vertex;   /*顶点*/
EdgeList edgelist;   /*边表头指针*/
}  VexNode,AdjList[MAX_VEXTEX_NUM];  /*顶点表中的结点*/

typedef struct{
int vexnum;  /*图的顶点数*/
int arcnum;  /*图的边的个数*/
AdjList vexs;   /*顶点表*/
}  GraphList; /*图的邻接表表示法*/
//==========================================================================================================================//
void FindInDegree(GraphList *G,int *indegree);
int TopoSort(GraphList *G,int *ptopo);  /*拓扑排序*/
int CriticalPath(GraphList *G) ;
//==========================================================================================================================//
int CriticalPath(GraphList *G)
{    int i,j,k,sum=0;   EdgeList p;
int *ee=(int *)malloc(sizeof(int)*G->vexnum);
int *le=(int *)malloc(sizeof(int)*G->vexnum);  
int *l=(int *)malloc(sizeof(int)*G->vexnum);
int *e=(int *)malloc(sizeof(int)*G->vexnum);
int *topo=(int *)malloc(sizeof(int)*G->vexnum);
if(TopoSort(G,topo)==0)
{   printf("The AOE network has a cycle!\n");
getch();
return(0);
}
/*求事件可能的最早发生时间*/
for(i=0; i<G->vexnum; i++)
ee[i]=0;
for(k=0; k<G->vexnum; k++)
{  i=topo[k];
p=G->vexs[i].edgelist;
while(p!=NULL)
{   j=p->endvex;
if(ee[i]+p->weight>ee[j])
ee[j]=ee[i]+p->weight;
p=p->nextedge;
}
}

sum=ee[G->vexnum-1]; /*工程的最短完成时间*/
for(i=0; i<G->vexnum; i++)  /*求事件允许的最迟发生时间*/
le[i]=ee[G->vexnum-1];
for(k=G->vexnum-2; k>=0; k--)
{   i=topo[k];
p=G->vexs[i].edgelist;
while(p!=NULL)
{   j=p->endvex;
if((le[j]-p->weight)<le[i])
le[i]=le[j]-p->weight;
p=p->nextedge;
}
}
k=0;
printf("\nThe Critical Path:\n");
cout<<"各事件的最早发生时间:\n";
for(int q=0;q<G->vexnum;q++)
cout<<ee[q]<<' ';
cout<<endl;
cout<<"各事件的最晚发生时间:\n";
for(q=0;q<G->vexnum;q++)
cout<<le[q]<<' ';
cout<<endl;

/*求活动 ak 的最早开始时间 e(k)和最晚开始时间 l(k)*/
printf("\n|  Active  |  Early |   Late |   L-E  |  IsCritical \n");

for(i=0;i<G->vexnum;i++)
{   p=G->vexs[i].edgelist;
while(p!=NULL)
{   j=p->endvex;
e[k]=ee[i];
l[k]=le[j]-p->weight;
printf("|  <%d,%d>   |  %4d  |  %4d  | %4d   | ",i,j,e[k],l[k],l[k]-e[k]);
 
if(e[k]==l[k])
printf("Critical");
printf("\n");
k++;
p=p->nextedge;
}
}

printf("\nThe shortest time is: %d\n",sum);
getch();
return(1);
}
void InitGraph(GraphList *G) /*初始化图*/
{   int i,vexnum,arcnum,weight=0;
int v1,v2;
EdgeList p;
printf("Please input the vertexnum and the arcnum-->Form:(x,y)\n");
scanf("%d,%d",&vexnum,&arcnum);
G->vexnum=vexnum;
G->arcnum=arcnum;
for(i=0;i<vexnum;i++)
{
G->vexs[i].vertex=i+1;
G->vexs[i].edgelist=NULL;
}
for(i=0;i<arcnum;i++)
{   printf("Please input The %d Edge(For Example: 1,2,10 )\n",i+1);
scanf("%d,%d,%d",&v1,&v2,&weight);
if(v1>G->vexnum||v2>G->vexnum)
{
printf("The Node You Hava Just Input Is Not In The Vexs!!");
getch();
exit(0);
}
p=(EdgeList)malloc(sizeof(EdgeNode));
p->endvex=v2;
p->weight=weight;
p->nextedge=G->vexs[v1].edgelist;
G->vexs[v1].edgelist=p;
}
}
//==========================================================================================================================//
int TopoSort(GraphList *G,int *ptopo)  /*拓扑排序*/
{   EdgeList p;
int i,j,k,nodeno=0,top=-1;
int *indegree=(int *)malloc(sizeof(int)*G->vexnum);
FindInDegree(G,indegree); /*indegree 数组赋初值*/
for(i=0; i<G->vexnum; i++)  /* 将入度为零的顶点入栈*/
if(indegree[i]==0)
{   /*静态链式栈*/
indegree[i]=top;
top=i;
}
while(top!=-1)
{ j=top;
top=indegree[top];  /*取当前栈顶元素并退栈*/
ptopo[nodeno++]=j;  /*将该顶点输出到拓扑序列中*/
p=G->vexs[j].edgelist; /*取该元素边表中的第一个边结点*/
while(p)
{ k=p->endvex;
indegree[k]--;     /*删除以该顶点为起点的边*/
if(indegree[k]==0)
{   indegree[k]=top;  /*将新的入度为零的顶点入栈*/
top=k;
}
p=p->nextedge;
}
}
free(indegree);
if(nodeno<G->vexnum)
return(0);   /*AOV 网中存在回路*/
else
return(1);
}

//==========================================================================================================================//
void FindInDegree(GraphList *G,int *indegree) /*求出图中所有顶点的入度*/
{   int i;
EdgeList p;
for(i=0; i<G->vexnum; i++)
indegree[i]=0;
for(i=0; i<G->vexnum; i++)
{   p=G->vexs[i].edgelist;
while(p)
{
++indegree[p->endvex];
p=p->nextedge;
}
}
}
//==========================================================================================================================//


void TopoSortMenu(void)
{ int *ptopo;
int i;
GraphList *Graph=(GraphList *)malloc(sizeof(GraphList));
system("CLS");
InitGraph(Graph);
ptopo=(int *)malloc(sizeof(int)*Graph->vexnum);
if(TopoSort(Graph,ptopo)!=0)
{    printf("\nTopSort Result:\n");
for(i=0;i<Graph->vexnum-1;i++)
printf("v%d-->",ptopo[i]);/* 打印前 n-1 个 ( 有 -->)*/
printf("v%d",ptopo[i]);  /*打印最后一个(没有-->)*/
}
else
printf("The AOV network has a cycle!\n");
getch();
free(ptopo);
free(Graph);
}
//==========================================================================================================================//
void CriticalMenu(void)
{     GraphList *Graph=(GraphList *)malloc(sizeof(GraphList));
system("CLS");
InitGraph(Graph);
CriticalPath(Graph);
free(Graph);
}
void TopoCriticalMenu(void)
{    char ch;
while(1)
{   system("CLS");
printf("1.Topo Sort\n2.Critical Path\n0.Exit\n");
ch=getch();
switch(ch-'0')
{   case 0: exit(0);
case 1: TopoSortMenu(); break;
case 2: CriticalMenu(); break;
default:  system("CLS"); continue;
}
}
}
//==========================================================================================================================//
void main(void)
{
TopoCriticalMenu();
}