/* 圖的關鍵路徑問題的算法*/


#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 100
#define TRUE 1
#define FALSE 0

typedef struct EdgeNode EdgeNode;
typedef struct EdgeNode * PEdgeNode;
typedef struct EdgeNode * EdgeList;
typedef float AdjType;

struct EdgeNode {
    int endvex;			/* 相鄰頂點字段 */
    AdjType weight;
    PEdgeNode nextedge;	/* 鏈字段 */
};						/* 邊表中的結點 */

typedef struct {
    /*VexType vertex;*/		/* 頂點信息 */
    EdgeList edgelist;		/* 邊表頭指針 */
} VexNode;				/* 頂點表中的結點 */

typedef struct {
    int n;				/* 圖的頂點個數 */
    VexNode vexs[MAXVEX];
} GraphList;


typedef struct {
    /*VexType vexs[MAXVEX];*/	/* 頂點信息 */	
    int vexsno[MAXVEX];		/* 頂點在頂點表中的下標值 */
} Topo;


/* 求出圖中所有頂點的入度 */
/* 方法是搜索整個鄰接表 */
void findInDegree(GraphList* g, int *inDegree) {
    int i; 
    PEdgeNode p;        

    for (i = 0; i < g->n; i++)
        inDegree[i] = 0;

    for (i = 0; i < g->n; i++) {
        p = g->vexs[i].edgelist;
        while(p) {
            inDegree[p->endvex]++; 
            p = p->nextedge; 
        }
    }
}

void makeNewAOV(EdgeList p, int* indegree, int* top) {
    int k;

    while (p) {                       /* 刪除以該頂點為起點的邊 */
        k = p->endvex; 
        indegree[k]--;
        if (indegree[k] == 0) {         /* 將新的入度為零的邊入棧 */
            indegree[k] = *top;
            *top = k; 
        }
        p = p->nextedge;
    }
}

/* 拓撲排序算法*/
int topoSort(GraphList * paov, Topo * ptopo) {
    EdgeList p;
    int i, j, nodeno = 0, top = -1;
    int indegree[MAXVEX];

    findInDegree(paov, indegree);    /* 求出圖中所有頂點的入度 */
    for (i = 0; i < paov->n; i++)
        if (indegree[i] == 0) {        /* 將入度為零的頂點入棧 */ 
            indegree[i] = top; top = i;
        }

    while (top != -1) {                /* 棧不為空 */
        j = top;
        top = indegree[top];               /* 取出當前棧頂元素 */
        /*ptopo->vexs[nodeno]=paov->vexs[j].vertex;*/ /* 將該元素輸出到拓撲序列中 */
        ptopo->vexsno[nodeno++] = j;
        p = paov->vexs[j].edgelist;    /* 取該元素邊表中的第一個邊結點 */
        /*刪除該結點,構造新的AOV網*/
        /*對indegree數組進行修改*/
        makeNewAOV(p, indegree, &top);
    }

    if (nodeno < paov->n) {       /* AOV網中存在回路 */
        printf("The aov network has a cycle\n");
        return FALSE;
    }
    
    return TRUE;
}

void insert(GraphList* p,int a,int b,float weight){
    EdgeList pp;
    PEdgeNode temp;
    temp = (PEdgeNode)malloc(sizeof(EdgeNode));
    temp->endvex = b;
    temp->nextedge = NULL;
    temp->weight = weight;
    pp = p->vexs[a].edgelist;
    if (pp == NULL)
        p->vexs[a].edgelist = temp;
    else {
        while (pp->nextedge != NULL)
            pp = pp->nextedge;
        pp->nextedge = temp;
    }
}
	
/* 鄰接表的構造*/
GraphList* makeList(){
    GraphList* p;
    int i;
    p = (GraphList*)malloc(sizeof(GraphList));
    p->n = 9;
    for (i = 0; i < p->n; i++)
        p->vexs[i].edgelist = NULL;
    insert(p,0,1,6);
    insert(p,0,2,4);
    insert(p,0,3,5);
    insert(p,1,4,1);
    insert(p,2,4,1);
    insert(p,3,5,2);
    insert(p,4,6,9);
    insert(p,4,7,7);
    insert(p,5,7,4);
    insert(p,6,8,2);
    insert(p,7,8,4);
    return p;
}

int CriticalPath(GraphList * paoe);

/* 主程序*/
int main(){
    GraphList* p;
    /*int i;*/
    p = makeList();
    /*if(topoSort(p,&topo)==TRUE)
        for(i=0;i<p->n;i++)
            printf("%d ",topo.vexsno[i]);*/
    if (CriticalPath(p) == FALSE)
        printf("There is no critical path!\n");
    return 0;
}


/*******************************************/
#define MAXEDGE 100 

/* 計算數組ee*/
void countee(GraphList* paoe,Topo* ptopo, AdjType* ee) {
    int i, j, k;
    EdgeList p;

    for (i = 0; i < paoe->n; i++) ee[i] = 0;
    for (k = 0; k < paoe->n; k++) {       /* 求事件vj可能的最早發生時間ee(j) */
        i = ptopo->vexsno[k];
        p = paoe->vexs[i].edgelist;
        while (p != NULL) {
            j = p->endvex;
            if (ee[i] + p->weight > ee[j])
                ee[j] = ee[i] + p->weight;
            p = p->nextedge;
        }
    }
}


/* 計算數組le*/
void countle(GraphList * paoe,Topo* ptopo, AdjType* ee, AdjType* le) {
    int i, j, k;
    EdgeList p;
    for (i = 0; i < paoe->n; i++)         /* 求事件vi允許的最遲發生時間le(i) */
        le[i] = ee[paoe->n - 1];
    for (k = paoe->n - 2; k >= 0; k--) {
        i = ptopo->vexsno[k];
        p = paoe->vexs[i].edgelist;
        while (p != NULL) {
            j = p->endvex;
            if( le[j] - p->weight < le[i] )
                le[i] = le[j] - p->weight;
            p = p->nextedge;
        }
    }
}

/* 計算數組e,l并輸出結果*/
void counte_l(GraphList * paoe,Topo* ptopo, AdjType* ee,
                AdjType* le, AdjType* e, AdjType* l) {
    int i, j, k = 0;
    EdgeList p;
    /* 求活動ak的最早開始時間e(k)及最晚開始時間l(k) */
    for (i = 0; i < paoe->n; i++) {
        p = paoe->vexs[i].edgelist;
        while (p != NULL) {
            j = p->endvex;
            e[k] = ee[i];
            l[k] = le[j] - p->weight;
            if (e[k] == l[k])
                printf("<v%2d, v%2d>, ", i, j);
            k++;
            p = p->nextedge;
        }
    }
}

/* 關鍵路徑算法*/
int CriticalPath(GraphList * paoe) {
    AdjType ee[MAXVEX], le[MAXVEX], l[MAXEDGE], e[MAXEDGE];
    Topo topo;
    if (topoSort(paoe, &topo) == FALSE)               /* 求AOE網的一個拓撲序列 */
        return FALSE;
    countee(paoe, &topo, ee); /*計算數組ee*/
    countle(paoe, &topo, ee, le);/*計算數組le*/
    counte_l(paoe, &topo, ee, le, e, l);/*計算數組e,l并輸出結果*/
    printf("\n");
    return TRUE;
}