topo.c~

This program use for topological sorting

/*This program calcuate the critical rote when you input the dat in a file */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include "stack.c"       /* include stack */

#define LETTER  'A'    /* The first letter */
#define Max 50         /* at most 50 vex */
#define BUFF 30
#define DAT_TFILE "topo3.dat"   /*输入数据文件"topo＊.dat"*/

typedef struct Arcnode{
       char adjvex;  
       struct Arcnode *nextarc;
}Arcnode;

typedef struct {
       char vex;           /*data's tag*/
       int time;           
       Arcnode *firstarc;
}Vertexnode;

typedef struct {
       Vertexnode vertex[Max];
       int vexnum;
}Adjlist;

void Creatadjlist(Adjlist *G){
     FILE *dat;
     dat = fopen(DAT_TFILE,"r");
     Arcnode *newarc;
     int i;
     int flag;
     char a[BUFF];
     char yn[BUFF];
     
     fscanf (dat,"%d",&G->vexnum);
     for(i=0;i<G->vexnum;i++){
        flag=1;
        fscanf(dat,"%s", a);
        G->vertex[i].vex=a[0];                
        fscanf(dat,"%d",&G->vertex[i].time);
        fscanf(dat,"%s",yn);
        G->vertex[i].firstarc = (Arcnode *)malloc(sizeof(Arcnode));   /*Because firstarc has nextarc in it so it has to allocate memory*/        
        if (strcmp(yn,"no")==0)
        G->vertex[i].firstarc = NULL;

        else{             /*else 1*/
        fscanf(dat,"%s",a);
        G->vertex[i].firstarc->adjvex = a[0];
        G->vertex[i].firstarc->nextarc=NULL; 

        while(flag){
        fscanf(dat,"%s",yn);      
        if (strcmp(yn,"no")==0)             
             flag=0;             
        else{ 
              fscanf(dat,"%s",a); 
              newarc = (Arcnode *)malloc(sizeof(Arcnode));
              newarc->adjvex=a[0];
              newarc->nextarc = G->vertex[i].firstarc->nextarc;
              G->vertex[i].firstarc->nextarc= newarc;                      
            }
         }     /*while 1*/
        }     /*else 1*/   
     }   /*for*/ 
    fclose(dat);   
}

void Findid(Adjlist G, int indegree[Max]){      /* find every vex'indegree */
    int i;
    int k;
    Arcnode *arc;
    for(i=0; i<G.vexnum; i++)
       indegree[i]=0;
    for(i=0; i<G.vexnum; i++){
           arc = G.vertex[i].firstarc;
           while (arc != NULL){
             k=arc->adjvex-LETTER;       /*A-65=0*/
             indegree[k]++;        
             arc = arc->nextarc;
           }    
       }
}

void Toposort(Adjlist G,seqstack *T,int ve[Max]){
     int i;
     int m;
     int count;
     char vex[Max];
     int k;
     Arcnode *arc;
     int indegree[Max];
     seqstack S;
     Initstack(&S);
     Initstack(T);
     Findid( G, indegree);
     for(i=0; i<G.vexnum; i++){
       if(!indegree[i])
         Push(&S,G.vertex[i].vex);
       ve[i]=0;                      /* init start time */
     }
     count=0;

     while(S.top != -1){    
     Pop(&S,&vex[count]);
     m = vex[count]-LETTER; 
     Push(T,vex[count]);
     count++;
     arc = G.vertex[m].firstarc;
     
            while( arc != NULL){ 
                 k = arc->adjvex-LETTER;       
                 indegree[k]--;        
                 if(!indegree[k])
                 Push(&S,arc->adjvex); 
                 if(ve[m]+G.vertex[m].time > ve[k])
                 ve[k] = ve[m]+G.vertex[m].time;        
                 arc = arc->nextarc;
            } 
      }   
}

void Criticalpath(Adjlist G){
     seqstack T;
     char tag;
     int ei,li;
     int i;
     int m;
     int k;
     char x;
     int ve[Max];
     int vl[Max];
     Arcnode *arc;
     Toposort(G,&T,ve);
     for(i=0; i<G.vexnum; i++){
      vl[i]=ve[i];
     } 

   while(T.top != -1){
     Pop(&T,&x);
     m = x-LETTER;               
     arc = G.vertex[m].firstarc;
        while( arc != NULL){ 
         k = arc->adjvex-LETTER;           
         if(vl[k]-G.vertex[m].time < vl[m])
         vl[m] = vl[k]-G.vertex[m].time;        
         arc = arc->nextarc;
        }      
     } 

   for(i=0; i< G.vexnum; i++)    /*求ei,li 和关键活动*/
     {
        arc = G.vertex[i].firstarc;
        while( arc != NULL){ 
          k = arc->adjvex-LETTER;
          ei=ve[i];li=vl[k]-G.vertex[i].time;
          tag= (ei==li)?'*':' ';
          printf ("%c,%c,%d,%d %c\n",G.vertex[i].vex,G.vertex[k].vex,ei,li,tag);
          arc = arc->nextarc;
        }
     }
}

int main(){
    Adjlist G;
    int i;
    char vex[Max];
    int indegree[Max];
    Creatadjlist(&G);
    Criticalpath(G);
}