/* file name: critical.c */
/*如何找出關鍵路徑*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define MAX_V  100    /*最大節點數*/
#define MAX(x,y) (x < y ) ? y : x
#define MIN(x,y) (x > y ) ? y : x
#define empty -1

/*鄰接節點數據結構*/
typedef struct node_tag {
	int vertex;
	int duration;
	struct node_tag *link;
}  Node;

/*鄰接表頭數據結構*/
typedef struct headnode_tag {
	int count;
	Node *link;
}  HeadNode;

struct Stackstruct {
	int top;
	int item[MAX_V+1];
};

HeadNode *adjlist1[MAX_V+1];     /*鄰接表*/
HeadNode *adjlist2[MAX_V+1];     /*反鄰接表*/
struct Stackstruct Stack1 = { empty }; 
struct Stackstruct Stack2 = { empty };
int N;   /*頂點總數*/
/*起始頂點,終點頂點,最早及最晚時間*/
int source,sink,ES[MAX_V+1],LC[MAX_V+1];
int CriticalNode[MAX_V+1] ,node_count,path_count;

void initial_ES();
void initial_LC();
void build_adjlist();
void show_adjlist(HeadNode *[]);
void Toplogical_sort( HeadNode *[],int []);
void print_steps(int [],int);
void print_critical_node();
void print_critical_path();
void print_ES_LC();
void print_path_node(Node *,int);
void Push(struct Stackstruct *,int );
int  Pop(struct Stackstruct * );

void main()
{
	build_adjlist();
	show_adjlist(adjlist1);           /*顯示鄰接表*/
	initial_ES();                     /*起始ES(最早時間)*/
	Toplogical_sort(adjlist1,ES);   /*以拓樸排序法求出ES*/
	initial_LC();                     /*起始LC(最晚時間)*/
	show_adjlist(adjlist2);           /*顯示反鄰接表*/
	Toplogical_sort(adjlist2,LC);    /*以拓樸排序法求出LC*/
	print_ES_LC();	 	     /*列出最早及最晚時間*/
	print_critical_node();             /*列出關鍵點*/
	print_critical_path();             /*列出臨路徑*/
}

void build_adjlist()
{
	FILE *fptr;
	int vi,vj,w;
	Node *node;

	fptr = fopen("critical.dat","r");
	if ( fptr == NULL )
	{
		perror("critical.dat");
		exit(1);
	}

	fscanf(fptr,"%d",&N);
	/*起始鄰接表,count為前驅的數目 */
	for ( vi = 1; vi <= N; vi++)
	{
		adjlist1[vi] = (HeadNode *)malloc(sizeof(HeadNode));
		adjlist2[vi] = (HeadNode *)malloc(sizeof(HeadNode));
		adjlist1[vi]->count = 0;
		adjlist2[vi]->count = 0;
		adjlist1[vi]->link = NULL;
		adjlist2[vi]->link = NULL;
	}

	/* 讀取vi到vj的權w(duration)并串至鄰接表及反鄰接表 */
	while( fscanf(fptr,"%d %d %d",&vi,&vj,&w) !=EOF)
	{
		node = (Node *)malloc(sizeof(Node));
		node->vertex = vj;
		node->duration = w;
		node->link = adjlist1[vi]->link;
		adjlist1[vi]->link = node;
		adjlist1[vj]->count++;      /*前驅數加1*/
		node = (Node *)malloc(sizeof(Node));
		node->vertex = vi;
		node->duration = w;
		node->link = adjlist2[vj]->link;
		adjlist2[vj]->link = node;
		adjlist2[vi]->count++;      /*前驅數加1*/
	}
	fclose(fptr);

	/*找出開始頂點*/
	for (vi =1; vi <= N; vi++ )
		if ( adjlist1[vi]->count == 0 )
		{
			source = vi;
			break;
		}
	/*找出結束結點*/
	for ( vi = 1;vi <= N; vi++ )
		if ( adjlist1[vi]->link == NULL )
		{
			sink = vi;
			break;
		}
}
/*顯示鄰接表函數*/
void show_adjlist(HeadNode *adjlist[])
{
	int v;
	Node *ptr;

	/*判斷為鄰接表adjlist1或反鄰接表adjlist2*/
	if ( adjlist == adjlist1)
		puts("\nThe adjacency lists [adjlist1] of the Graph");
	else
		puts("\n\nThe inverse adjaccny list [adjlist2] of the Graph");
	puts("Headnodes    adjacency nodes");
	puts("  /count        /duration   ");
	puts("------------------------------");
	for (v = 1; v <= N; v++)
	{
		printf("V%d: %d",v,adjlist[v]->count);
		ptr = adjlist[v]->link;
		while ( ptr != NULL )
		{
			printf(" --> V%d(%d)",ptr->vertex,ptr->duration);
			ptr = ptr->link;
		}
		printf("\n");
	}
}

/*以拓樸排序法計算最早時間(ES)及最晚時間(LC)*/
void Toplogical_sort(HeadNode *adjlist[],int ES_LC[])
{
	int vi,vj ,k,dur;
	Node *ptr;

	/*將沒有前驅的頂點推入堆棧*/
	for ( vi = 1; vi <= N; vi++ )
		if ( adjlist[vi]->count == 0 )
			Push(&Stack1,vi);
	print_steps(ES_LC,0);    /*列出堆棧及ES_LC狀況*/
	for ( k=1; k<= N; k++ )
	{
		if (  Stack1.top == empty )
		{
			printf("\nCyclic Path found....\n");
			exit(1);
		}
		/*從堆棧彈出頂點*/ 
		vi = Pop(&Stack1);
		ptr = adjlist[vi]->link;    /*ptr指向vi的鄰接邊表*/
		while ( ptr != NULL )
		{
			vj = ptr->vertex;     /*vj為vi的立即后行者*/
			dur = ptr->duration;  
			adjlist[vj]->count--;   /*vj 前驅數減1*/
			if ( adjlist[vj]->count == 0 )
				Push(&Stack1,vj);
			if ( adjlist == adjlist1 )  /*判斷計算ES或LC*/
				ES_LC[vj] = MAX(ES_LC[vj],ES_LC[vi]+dur);
			else
				ES_LC[vj] = MIN(ES_LC[vj],ES_LC[vi]-dur);
			ptr = ptr->link;
		}
		print_steps(ES_LC,vi);
	}
}

/*顯示目前堆棧狀況及ES或LC值*/
void print_steps(int ES_LC[],int v)
{
	int i;

	if ( v == 0 )
	{
		printf("\nComputation of ES_LC :\n");
		printf("----------------------\n");
		printf("ES_LC[N]  : ");
		for (i = 1;i <= N; i++ ) printf(" [%d]",i);
		printf("     Current Stack");
		printf("\ninitial   :");
	}
	else
		printf("\nPopout V%d :",v);
	for ( i = 1; i <= N; i++ )
		printf(" %3d",ES_LC[i]);
	printf("     ");
	for ( i =0; i <= Stack1.top; i++ )
		printf(" %d,",Stack1.item[i]);
}

/*顯示各頂點的最早時間(ES)及早晚時間(LC)值*/
void print_ES_LC()
{
	int i;

	printf("\n");
	for ( i = 1; i<= N; i++ )
		printf("\nES(%d) = %3d   LC(%d) = %3d ES  - LC = %3d",
					i,ES[i],i,LC[i],ES[i] - LC[i]);
}
/*列出關鍵點*/
void print_critical_node()
{
	int v;

	for ( v =1; v<= N;v++ )
		if ( LC[v] == ES[v] )     /*當LC == ES 時頂點為關鍵點*/
			CriticalNode[++node_count] = v;
	printf("\n\nThe Critical Nodes of the Graph :\n");
	for ( v = 1; v<= node_count; v++ )
		printf("%d,",CriticalNode[v]);
}

/*列出界路徑*/
void print_critical_path()
{
	printf("\n\nThe Critical Paths of the Graph :");
	/*從起始頂點開始找尋關鍵路徑*/
	print_path_node(adjlist1[source]->link,source);
}

void print_path_node(Node *ptr,int v)
{
	int  i;

	/* 判斷鄰接頂點是否為關鍵點，將關鍵點推入堆棧
  并從該關鍵點繼續遞歸呼叫print_path_node() */
	while ( ptr != NULL )
	{
		for ( i = 1;i<= node_count;i++)
			if ( CriticalNode[i] == ptr->vertex && LC[ptr->vertex]-LC[v] == ptr->duration )
			{
				Push(&Stack1,(int)ptr);
				Push(&Stack2,v);
				v = ptr->vertex;
				ptr = adjlist1[v]->link;
				print_path_node(ptr,v);
			}
		ptr = ptr->link;
	}

	if ( v == source )
	{
		printf("\n\nThere are %d Critical paths from %d to %d\n",
				path_count,source,sink);
		exit(0);
	}
	/* 當到達終點節點時即找到一關鍵路徑 */
   /* 列出堆棧Stack1所存放的關鍵點
   及Stack2所存放的關鍵活動        */
	if ( v == sink )
	{
		printf("\n");
		for ( i = 0;i <= Stack2.top; i++)
		{
			v = Stack2.item[i];
			ptr =(Node *) Stack1.item[i];
			printf("V%d--%d-->",v,ptr->duration);
		}
		printf("V%d",sink);
		path_count++;
	}

	/* 彈出堆棧中的前一層關鍵頂點及關鍵活動 */
/* 繼續搜索其鄰接頂點是否有關鍵路徑 */ 
	ptr = (Node *)Pop(&Stack1);
	ptr = ptr->link;
	v = Pop(&Stack2);
	print_path_node(ptr,v);
}

/*起始ES初值*/
void initial_ES()
{
	int i;
	for ( i = 1;i <= N; i++ ) ES[i] = 0;
}

/*起始LC初值,LC初值為ES最大值*/
void initial_LC()
{
	int i ,max = 0;
	for ( i = 1; i <= N; i++ ) max= MAX(max,ES[i]);
	for ( i = 1; i <= N; i++ ) LC[i] = max;
}

void Push( struct Stackstruct *stack,int value )
{
	if ( stack->top >= MAX_V)
	{
		printf("Stack is Overflow!!\n");
		exit(1);
	}
	else
		stack->item[++stack->top] = value;
}

int Pop(struct Stackstruct *stack)
{
	if ( stack->top == empty )
	{
		printf("Stack is empty!!");
		exit(1);
	}
	else
		return (stack->item[stack->top--]);
}