#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#define INFINITY 88
#define MAX_VERTEX_NUM 20
#define MAX_ARC_NUM MAX_VERTEX_NUM*2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OVERFLOW -1
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int InfoType;
typedef char VertexType;
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;
int ve[ MAX_VERTEX_NUM];
int vl[ MAX_VERTEX_NUM];
}ALGraph;
typedef int SElemType;
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
} SqStack;
Status InitStack(SqStack &S)
{
int stack_init_size=STACK_INIT_SIZE;
S.base=(SElemType * )malloc(stack_init_size* sizeof(SElemType));
if(!S.base) exit (OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status Push(SqStack &S,SElemType e)
{
int stackincrement=STACKINCREMENT;
if(S.top-S.base >= S.stacksize)
{
S.base=(SElemType*)realloc(S.base,(S.stacksize+stackincrement)*sizeof(SElemType));
if(!S.base) exit (OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,SElemType &e)
{
if (S.top==S.base)return ERROR;
e=*--S.top;
return OK;
}
Status StackEmpty(SqStack S)
{
if (S.top==S.base)return (TRUE);
else return (FALSE);
}
Status CreateDN(ALGraph &G)
{
int i,j,k,w,IncInfo;
char v1,v2,V;
ArcNode *p;
int LocateVex(ALGraph,char);
printf("input the number for vexnum and arcnum");
scanf("%d,%d",&G.vexnum,&G.arcnum);
IncInfo=0;IncInfo=IncInfo;
V=getchar(); //skip the enter ,same as next...
printf("input %d char for vexs \n",G.vexnum);
for(i=0;i<G.vexnum;++i)
{
G.vertices[i].data=getchar();
V=getchar();
}
for(i=0;i<G.vexnum;++i)
G.vertices[i].firstarc=NULL;
printf("input %d arc(char,char,weight) \n",G.arcnum);
for(k=0;k<G.arcnum;++k)
{
printf("%d: ",k);
scanf("%c,%c,%d",&v1,&v2,&w);
V=getchar(); V=V;
i=LocateVex(G,v1); j=LocateVex(G,v2);
if(i!=100&&j!=100)
{
p=new ArcNode;
p->adjvex=j;
p->info=new InfoType;
*(p->info)=w;
p->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
}
}
return OK;
}
int LocateVex(ALGraph G,char v)
{
int i,p;
p=100;
for(i=0;i<G.vexnum;++i)
if(v==G.vertices[i].data)p=i;
return p;
}
Status DispGraph(ALGraph G)
{
int i;
ArcNode *p;
for(i=0;i<G.vexnum;++i)
{
printf("%3d%c",i,G.vertices[i].data);
p=G.vertices[i].firstarc;
while(p)
{
printf("--->%d%3d",p->adjvex,*(p->info));
p=p->nextarc;
}
printf("\n");
}
return OK;
}
Status TopologicalOrder(ALGraph &G,SqStack &T)
{
int indegree[ MAX_VERTEX_NUM];
int i,j,k,count;
ArcNode *p;
SqStack S;
InitStack(S); InitStack(T);
count=0;
for(i=0;i<G.vexnum;++i)
indegree[i]=0;
for(i=0;i<G.vexnum;++i)
{
p=G.vertices[i].firstarc;
while(p)
{
++indegree[p->adjvex];
p=p->nextarc;
}
}
for(i=0;i<G.vexnum;++i) G.ve[i]=0;
for(i=0;i<G.vexnum;++i)
if(!indegree[i])Push(S,i);
while(!StackEmpty(S))
{
Pop(S,j);
Push(T,j);
++count;
for(p=G.vertices[j].firstarc; p; p=p->nextarc)
{
k=p->adjvex;
if(--indegree[k]==0) Push(S,k);
if(G.ve[j] +*(p->info) > G.ve[k])
G.ve[k] = G.ve[j]+*(p->info);
}
// for(j=0;j<G.vexnum;++j)printf("%d--%d\n",j,indegree[j]);
}
if(count<G.vexnum)return ERROR;
else return OK;
}
Status CriticalPath(ALGraph G)
{
int i,j,k,dut,ee,el;
ArcNode *p;
SqStack T;
char tag;
if(! TopologicalOrder(G,T))return ERROR;
for(i=0;i<G.vexnum;++i)
G.vl[i]=G.ve[G.vexnum-1];
while(!StackEmpty(T))
for(Pop(T,j),p=G.vertices[j].firstarc; p; p=p->nextarc)
{
k=p->adjvex;dut=*(p->info);
if(G.vl[k]-dut<G.vl[j])G.vl[j]=G.vl[k]-dut;
}
for(j=0;j<G.vexnum;++j)
for(p=G.vertices[j].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
dut=*(p->info);
ee=G.ve[j];el=G.vl[k]-dut;
tag=(ee==el)?'*':'@';
printf("%c %d-->%d dut:%d ee:%d el:%d\n",tag,j,k,dut,ee,el);
}
return OK;
}
void main()
{
ALGraph G;
CreateDN(G);
//DispGraph(G);
if(! CriticalPath(G))printf("The graph G exist cycle !");
}
