critical.c

该文件夹中包含了大部分经典的算法的源程序代码

/* 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--]);
}