aoe.h

数据结构算法

#include<iostream.h>
#include"dlink.h"
#include"Graph.h"

class AOE{
public:
    AOE(){}
    ~AOE(){}

    void Initial();
	void keyin();
    void keyroute();
	void show();
	    
private:
	void visit(int i,int* route,int& j);
	void Calle();
	void Calee();
	Graph InDeg;
	Graph OutDeg;
	int* le;                   //事件的最早开始时间
	int* ee;                   //事件的最迟开始时间
};

void AOE::show(){
   cout<<endl;
   cout<<"After topsort( <- ):";
   dlink<int> Queue;
   Queue=OutDeg.topsort();   
   while(!Queue.isempty())
	   cout<<Queue.output()<<"  ";
   cout<<endl;
   cout<<"Aftet topsort( -> ):";
   Queue=InDeg.topsort();
   while(!Queue.isempty())
	   cout<<Queue.output()<<"  ";
   cout<<endl;
}

void AOE::Calee(){
	ee=new int[InDeg.NumV()];
	for(int i=0;i<InDeg.NumV();i++)
		ee[i]=0;
	dlink<int> Queue=InDeg.topsort();	
	while(!Queue.isempty()){
		i=Queue.output();
		Edge* temp=InDeg.list[i].FirstE;
		while(temp!=NULL){
		  if(ee[i]<(ee[temp->v2]+temp->weight))
			  ee[i]=ee[temp->v2]+temp->weight;
          temp=temp->next;
		}
	}
}

void AOE::Calle(){	
	le=new int[OutDeg.NumE()];
	
	dlink<int> Queue=OutDeg.topsort();
	int j=Queue.output();
	for(int i=0;i<OutDeg.NumV();i++)
		le[i]=ee[j];

	while(!Queue.isempty()){
		j=Queue.output();
		Edge* temp=OutDeg.list[j].FirstE;
		while(temp!=NULL){
			if(le[j]>(le[temp->v2]-temp->weight))
				le[j]=le[temp->v2]-temp->weight;
		    temp=temp->next;
		}		
	}
}


void AOE::keyroute(){
	Calee();
	Calle();
    cout<<"Early :";
	for(int x=0;x<OutDeg.NumV();x++)
		cout<<"v"<<x<<":"<<ee[x]<<"  ";
	cout<<endl;
	cout<<"Late  :";
	for(x=0;x<OutDeg.NumV();x++)
		cout<<"v"<<x<<":"<<le[x]<<"  ";
	cout<<endl;


	int* keys=new int[OutDeg.NumE()];
	int* route=new int[OutDeg.NumE()];
	const Max=65535;   

    for(int i=0;i<OutDeg.NumE();i++){
		keys[i]=le[i]-ee[i];
		route[i]=Max;
	}

    dlink<int> Queue=InDeg.topsort();
    
    i=Queue.output();
	int j=0;
    visit(i,route,j);
}
void AOE::visit(int i,int* route,int& j){
	route[j++]=i;
	if(OutDeg.list[i].degree==0){
		cout<<"route :";
		for(int t=0;t<j;t++){			
			cout<<route[t]<<"  ";
		}
		cout<<endl;
		j--;
		return;
	}
	Edge* temp=OutDeg.list[i].FirstE;
	while(temp!=NULL){
		if(ee[temp->v2]==le[temp->v2]){
			visit(temp->v2,route,j);						
		}	
		temp=temp->next;
	}
	j--;
	return;
}

void AOE::Initial(){
    int n=9;
	OutDeg.NumVert=n;
	OutDeg.NumEdge=0;
	OutDeg.list=new ListNode[n];
	for(int i=0;i<n;i++){
		(OutDeg.list)[i].degree=0;
		(OutDeg.list)[i].FirstE=NULL;
	}

	OutDeg.InsertEdge(0,1,6);	
	OutDeg.InsertEdge(0,2,4);
	OutDeg.InsertEdge(0,3,5);
	OutDeg.InsertEdge(1,4,1);	
	OutDeg.InsertEdge(2,4,1);
    OutDeg.InsertEdge(3,5,2);
	OutDeg.InsertEdge(4,6,9);
	OutDeg.InsertEdge(4,7,7);
	OutDeg.InsertEdge(5,7,4);
	OutDeg.InsertEdge(6,8,2);
	OutDeg.InsertEdge(7,8,4);
//---------------------------------------
    InDeg.NumVert=n;
	InDeg.NumEdge=0;
	InDeg.list=new ListNode[n];
	for(i=0;i<n;i++){
		(InDeg.list)[i].degree=0;
		(InDeg.list)[i].FirstE=NULL;
	}

	InDeg.InsertEdge(1,0,6);	
	InDeg.InsertEdge(2,0,4);
	InDeg.InsertEdge(3,0,5);
	InDeg.InsertEdge(4,1,1);	
	InDeg.InsertEdge(4,2,1);
    InDeg.InsertEdge(5,3,2);
	InDeg.InsertEdge(6,4,9);
	InDeg.InsertEdge(7,4,7);
	InDeg.InsertEdge(7,5,4);
	InDeg.InsertEdge(8,6,2);
	InDeg.InsertEdge(8,7,4);


}


void AOE::keyin(){
	int n,e;
	cout<<"Please key int how many nodes(0~n-1)  :";
    cin>>n;
	cout<<endl<<"Please key in how many edge  :";
	cin>>e;

    OutDeg.NumVert=n;
	OutDeg.NumEdge=0;
	OutDeg.list=new ListNode[n];
	for(int i=0;i<n;i++){
		(OutDeg.list)[i].degree=0;
		(OutDeg.list)[i].FirstE=NULL;
	}

    InDeg.NumVert=n;
	InDeg.NumEdge=0;
	InDeg.list=new ListNode[n];
	for(i=0;i<n;i++){
		(InDeg.list)[i].degree=0;
		(InDeg.list)[i].FirstE=NULL;
	}
    
    cout<<endl<<"v1->v2 weight w<key in as :v1 v2 w>"<<endl;   
	int v1,v2,w;
	for(i=1;i<e+1;i++){
	cout<<"No."<<i<<" : ";
	cin>>v1>>v2>>w;	
    
	OutDeg.InsertEdge(v1,v2,w);
	InDeg.InsertEdge(v2,v1,w);
	}
	cout<<endl<<"--------over-----------"<<endl;


}