#include<iostream>
using namespace std;

typedef int Status;
typedef int InfoType;
typedef int VertexType;
typedef int SElemType;
const int MAX_VERTEX_NUM=10;
const int OK=1;
const int STACK_INIT_SIZE=10;
const int OVERFLOW=-2;
const int STACKINCREMENT=5;
const int ERROR=0;
int ArcArray[16]={1,2,1,3,2,4,2,5,3,4,3,6,4,6,5,6};
int InfoArray[8]={3,2,2,3,4,3,2,1};
int *ve=NULL;
int *vl=NULL;
unsigned short InfoPlace=0;



typedef struct ArcNode									//表結點
{
	int				adjvex;								//該弧所指向頂點的位置
	struct ArcNode	*nextarc;							//指向下一條弧的位置
	InfoType		info;								//該弧相關信息的指針
}ArcNode;
typedef struct VNode								
{
	VertexType		data;								//頂點信息
	ArcNode			*firstarc;								
}VNode,AdjList[MAX_VERTEX_NUM];							//指向第一條依附該頂點的弧的指針
typedef struct 
{
	AdjList vertices;									 
	int		vexnum,arcnum;								//圖的當前頂點　數各弧數
	int		kind;										//圖的種類標志
}ALGraph; 
typedef class
{
public:
	SElemType *base;
	SElemType *top;											//指向待插入元素的位置
	int Stacksize;
}SqStack;

Status CreateALGraph(ALGraph &G);
void FindInDegree(ALGraph);
Status FindInDegree(ALGraph G,int indegree[]);
int Locate(int i);
Status InitStack(SqStack &S);
Status Pop(SqStack &S,SElemType &e);
Status Push(SqStack &S,SElemType e);
Status StackEmpty(SqStack S);
Status CriticalPath(ALGraph G);

void main()
{
	cout<<"\t\t\t*******************************"<<endl;
	cout<<"\t\t\t　　　  　圖--關鍵路徑　　　　　"<<endl;
	cout<<"\t\t\t    海川工作室出品(2007.6.27)　"<<endl;
	cout<<"\t\t\t*******************************"<<endl;
	ALGraph G;
	CreateALGraph(G);
	CriticalPath(G);

	
	
/*	for(;;)
	{
		cout<<"(1).創建鄰接表。(書186頁)"<<endl;
		cout<<"請輸入你的選擇:"<<endl;
		unsigned short choose;
		cin>>choose;
	
		
	}*/

}
/**************************/
Status TopologicalOrder(ALGraph G,SqStack &T)
{
	//有向圖G采用鄰接表存儲結構　，求各頂點事件的最早發生時間ve(全局變量)。
	//T為拓撲序列頂點棧，S為零入度頂點棧。
	//若G無回路，則用棧T返回G的一個看不順眼撲序列，且函數值為OK，否則為ERROR
	//算法7.13
	unsigned short count=0;
	int *indegree=new int[G.vexnum];
	FindInDegree(G,indegree);
	InitStack(T);
	count=0;
	ve=new int[G.vexnum];
	for(unsigned short place=0;place<G.vexnum;place++)
	{
		ve[place]=0;
	}
	
	SqStack S;
	S.base=NULL;
	S.top=NULL;
	S.Stacksize=0;
	int j=0;
	for(int i=0;i<G.vexnum;i++)
	{
		if(!indegree[i])
		{
			Push(S,i);
		}
	}
	count=0;
	while (!StackEmpty(S))
	{
		int k=0;
		for(ArcNode *p=G.vertices[i].firstarc;p;p=p->nextarc)
		{
			
			k=p->adjvex;
			if(!(--indegree[k]))
			{
				Push(S,k);
			}
		
		}
	}
	count++;
	while(!StackEmpty(S))
	{
		Pop(S,j);
		Push(T,j);
		count++;
		for(ArcNode *p=G.vertices[j].firstarc;p;p=p->nextarc)
		{
			int k=p->adjvex;
			if(--indegree[k]==0)
			{
				Push(S,k);
			}
			if(ve[j]+(p->info)>ve[k])
			{
				ve[k]=ve[j]+(p->info);
			}
		}
	}
	if(count<G.vexnum)
	{
		return ERROR;
	}
	else
	{
		return OK;
	}
}
/****************************/
Status CreateALGraph(ALGraph &G)
{
	//創建一個書上P183頁的圖
	cout<<"創建書上P183頁的圖."<<endl;
	cout<<"創建的圖一共有9個結點."<<endl;
	G.vexnum=6;
	cout<<"創建的圖一共有11調弧."<<endl;
	G.arcnum=8;
	for(unsigned short place=0;place<G.vexnum;place++)
	{
		G.vertices[place].data=place+1;
		G.vertices[place].firstarc=NULL;
	}
	place=0;
	for(unsigned short counter=1;counter<=G.arcnum;counter++)
	{
	
		cout<<"第"<<counter<<"條弧:";
		int head=Locate(ArcArray[place]);
		cout<<"尾結點是"<<ArcArray[place];
		place++;
		cout<<"頭結點是"<<ArcArray[place]<<endl;
		int rail=Locate(ArcArray[place]);
		place++;
		ArcNode *pNode=new ArcNode;
		pNode->adjvex=rail;
		pNode->info=InfoArray[InfoPlace];
		InfoPlace++;
		pNode->nextarc=G.vertices[head].firstarc;
		G.vertices[head].firstarc=pNode;
}
	return OK;
}
int Locate(int i)
{
	return i-1;
}
/***************************/
Status CriticalPath(ALGraph G)
{
	//G為有向網，輸出G的各項關鍵活動。
	//算法7.14
	vl=new int[G.vexnum];
	SqStack T;
	if(!TopologicalOrder(G,T))
	{
		return ERROR;
	}
	for(unsigned short place=0;place<G.vexnum;place++)
	{
		vl[place]=ve[G.vexnum];
	}
	while(!StackEmpty(T))
	{
		int j=0,k=0,dut=0;
		Pop(T,j);
		for(ArcNode *p=G.vertices[j].firstarc;p;p=p->nextarc)
		{
			k=p->adjvex;
			dut=p->info;
			if(vl[k]-dut<vl[j])
			{
				vl[j]=vl[k]-dut;
			}
		}
		for(j=0;j<G.vexnum;j++)
		{
			int ee,el;
			char tag;
			for(p=G.vertices[j].firstarc;p;p=p->nextarc)
			{
				k=p->adjvex;
				dut=p->info;
				ee=ve[j];
				el=vl[k]-dut;
				tag=(ee==el) ? '*' : ' ';
				cout<<j<<k<<dut<<ee<<el<<tag<<endl;
			
			}
		}
	}
	return OK;
}
/****************/
Status FindInDegree(ALGraph G,int indegree[])
{
	for(unsigned short counter=1;counter<=G.vexnum;counter++)
	{
		unsigned short sum=0;
		unsigned short place=0;
		ArcNode *p;
		for(unsigned short i=0;i<G.vexnum;i++)
		{
			
			for(p=G.vertices[i].firstarc;p!=NULL;p=p->nextarc)
			{
				if(p->adjvex==Locate(counter))
				{
					sum++;
				}
			}
		}
		indegree[Locate(counter)]=sum;
	}
	return OK;
}
/*********************************創建一個棧**********************************************/
Status InitStack(SqStack &S)
{
	//構造一個空棧
	S.base=new SElemType[STACK_INIT_SIZE];					//初始化一個大小100的棧
	if(!S.base)
	{
		exit(OVERFLOW);
	}
	S.top=S.base;
	S.Stacksize=STACK_INIT_SIZE;
	return OK;
}
//********************************壓入一個元素******************************************/
Status Push(SqStack &S,SElemType e)
{
	//插入元素e為新棧頂元素
	if(S.top-S.base>=S.Stacksize)							//如果棧滿
	{	
		SElemType *exchange=new SElemType[S.Stacksize+STACKINCREMENT];
		for(unsigned short counter=0;counter<S.top-S.base;counter++)
		{
			exchange[counter]=S.base[counter];				
		}
		delete []S.base;
		S.base=exchange;							
		if(!S.base)
		{
			exit(OVERFLOW);
		}
		S.top=S.base+S.Stacksize;							//S.top為待插入元素的位置	
		S.Stacksize=S.Stacksize+STACKINCREMENT;
	}
	*S.top=e;												//S.top始終指向帶插入元素的位置
	S.top++;
	return OK;
}
/**********************************彈出一個元素***************************************/
Status Pop(SqStack &S,SElemType &e)
{
	//若棧不空,則刪除S的棧頂元素，用e返回其值，并返回OK，否則返回ERROR
	if(S.top==S.base)
	{
		cout<<"彈出失敗，這個棧什么都沒有."<<endl<<endl;
		return ERROR;
	}
	S.top--;
	e=*S.top;
	return OK;
}
/*******************************判斷一個棧空不空******************************************/
Status StackEmpty(SqStack S)
{

	if(S.base==S.top)
	{
		return OK;
	}
	else
	{
		return ERROR;
	}
}