aoe网络.cpp

我自己写的AOE网络算法

//	自己设计一个项目，排出AOE网络，
//	并将数据输入计算机，用程序进行分析。
//  这一题我不会做，参考了陈文晖同学的代码

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


struct Edgenode
{
	int adjvex,time;
	Edgenode *next;
};

struct Vexnode
{
	int projectname,indegree;
	Edgenode *firstarc;
};

struct Stack
{
	Vexnode Gra;
	Stack *next,*pre;
};

struct LinkStack
{
	Stack *base;
	Stack *top;
	int stacksize;
};

void InitStack(LinkStack &s)
{
	s.base=new Stack;
	if(!s.base) exit(1);
	s.base->next=NULL;
	s.base->pre=NULL;
	s.top=s.base;
	s.stacksize=0;
}

void Push( LinkStack &s,int i,Vexnode *Graph)
{
	Stack *p=new Stack;
	p->next=NULL;
	p->pre=s.top;
	p->Gra=Graph[i];
	s.top->next=p;
	s.top=p;
	s.stacksize+=1;
}

void Pop(LinkStack &s,int &j)
{
	Stack *p;
	if(s.top==s.base) return;
	j=s.top->Gra.projectname;
	p=s.top;
	s.top=s.top->pre;
	s.top->next=NULL;
	delete p;
}

bool StackEmpty(LinkStack &s)
{
	if(s.top==s.base) return 1;
	else return 0;
}

void CreateGraph(Vexnode *Graph, int vexnum, int arcnum)
{
	int begin,end,duttem;
	Edgenode *p; 
    for(int i=0;i<vexnum;i++) 
    { 
		Graph[i].projectname=i; 
		Graph[i].indegree =0; 
		Graph[i].firstarc =NULL; 
    } 
	cout<<"某项目的开始到结束在图中的节点输入<vi,vj,dut>\n";
	cout<<"如：3 4 9 回车表示第三节点到第四节点之间的活动用了9个单位时间\n";
	for(int j=0;j<arcnum;j++)
	{
		cin>>begin>>end>>duttem;
		p=new Edgenode;
		p->adjvex=end-1;
		p->time=duttem;
		Graph[end-1].indegree++;
		p->next=Graph[begin-1].firstarc;
		Graph[begin-1].firstarc=p;
	}
}


bool TopologicalOrder(Vexnode * Graph,int vexnum,int arcnum,LinkStack & T,int *&ve,int &totaltime)
{
	Edgenode *p;
	int i=0,j=-1,k=0,count;
	InitStack(T);
	LinkStack S;		//建零入度顶点栈S
	InitStack(S);
	for(i=0;i<vexnum;i++) { if(Graph[i].indegree==0) Push(S,i,Graph);}
	count=0;
	for(i=0;i<vexnum;i++) ve[i]=0;
	while(!StackEmpty(S))
	{
		Pop(S,j); 
		Push(T,j,Graph);
		++count;
		for(p=Graph[j].firstarc;p;p=p->next)
		{
			k=p->adjvex;		
			if(--Graph[k].indegree==0) Push(S,k,Graph);		//若入度减为0，则入栈
			if(ve[j]+p->time>ve[k]) ve[k]=ve[j]+p->time;
			totaltime=ve[k];
		}
	}//while
	if(count<vexnum) return 0;		//该有向网有回路
	else return 1;
}

bool CriticalPath(Vexnode *Graph,int vexnum,int arcnum,LinkStack & T)
{
	int i=0,j=-1,k=-1,duttem=0;
	int ee,el,totaltime=0;
	char tag;
	Edgenode *p;
	int *ve=new int [vexnum];	//用来表示活动最早发生时间
	int *vl=new int [vexnum];	//用来表示在不推迟整个工程的前提下，活动允许最迟发生的时间
	if(!TopologicalOrder(Graph,vexnum,arcnum,T,ve,totaltime)) return 0;
	for(i=0;i<vexnum;i++) {vl[i]=totaltime;}
	while(!StackEmpty(T))
		for(Pop(T,j),p=Graph[j].firstarc; p; p=p->next)
		{
			k=p->adjvex;
			duttem=p->time;
			if(vl[k]-duttem<vl[j]) vl[j]=vl[k]-duttem;
		}
	cout<<endl;
	cout<<"| 起点 | 终点 |活动需要时间|最早开始时间|最迟完成时间| 差值 |关键活动|\n";
	for(j=0;j<vexnum;++j)
		for(p=Graph[j].firstarc; p; p=p->next)
		{
			k=p->adjvex;
			duttem=p->time;
			ee=ve[j];
			el=vl[k]-duttem;
			tag=(ee==el)?'*':' ';
			cout<<"|";	cout.width(5);	cout<<j+1;
			cout<<"|";	cout.width(6);	cout<<k+1;
			cout<<"|";	cout.width(11);	cout<<duttem;
			cout<<"|";	cout.width(12);	cout<<ee;
			cout<<"|";	cout.width(11);	cout<<el;
			cout<<"|";	cout.width(6);	cout<<el-ee;
			cout<<"|";	cout.width(7);	cout<<tag;
			cout<<"|"<<endl;
		}
	cout<<"共需时间:"<<totaltime<<endl;
	return 1;
}


void seekkeyroot()
{
	bool status;
	int vexnum,arcnum,totaltime=0; 
	LinkStack T;
	cout<<"请输入这个工程的化成图形的节点数:";
	cin>>vexnum;
	cout<<"请输入这个工程的活动个数:";
	cin>>arcnum;
	Vexnode *Graph=new Vexnode [vexnum];
	CreateGraph(Graph,vexnum,arcnum);
	status=CriticalPath(Graph,vexnum,arcnum,T);
	if(!status) cout<<"有回路,不能计算出关键路径!"<<endl;
}

void main()
{
	char c;
	seekkeyroot();
	c=getchar();
	return;
}