#include <stdio.h>
#include <stdlib.h>
#define MAX 20
#define INFINIT 65535
typedef struct _ArcCell{
int adj; // Weight or flag about connection
int *info; // Other information
}ArcCell;
typedef char VertexType;
typedef enum{
DG,
DN,
UDG,
UDN
}GraphKind;
typedef struct _MGraph{
VertexType vexs[MAX];
ArcCell arcs[MAX][MAX];
int vexnum;
int arcnum;
GraphKind kind;
}MGraph;
int visited[MAX];
int ve[MAX];
int vl[MAX];
int e[MAX];
int l[MAX];
int LocateVex(MGraph *G, VertexType v)
{
int i=0;
while(i<G->vexnum && G->vexs[i] != v){
i++;
}
if(i<G->vexnum){
return i;
}else{
return -1;
}
}
int CreateUDN(MGraph *G)
{
int i,j,k;
char v1,v2;
int cost;
scanf(" %d %d", &G->vexnum, &G->arcnum);
for(i=0; i<G->vexnum; i++){
scanf(" %c", &G->vexs[i] );
}
for(i=0; i<G->vexnum; i++){
for(j=0; j<G->vexnum; j++){
G->arcs[i][j].adj = INFINIT;
}
}
for(k=0; k<G->arcnum; k++){
scanf(" %c %c %d", &v1, &v2, &cost);
i=LocateVex(G, v1);
j=LocateVex(G, v2);
G->arcs[i][j].adj = cost;
}
return 1;
}
int FirstAdjvex(MGraph *G, int v)
{
int i=0;
while(i<G->vexnum && G->arcs[v][i].adj == INFINIT){
i++;
}
if(i<G->vexnum){
return i;
}else{
return -1;
}
}
int NextAdjvex(MGraph *G, int v, int w)
{
int i=w+1;
while(i<G->vexnum && G->arcs[v][i].adj == INFINIT){
i++;
}
if(i<G->vexnum){
return i;
}else{
return -1;
}
}
void FindInDegree(MGraph *G, int *indegree)
{
int i;
int j;
for(i=0; i<G->vexnum; i++){
indegree[i]=0;
for(j=0; j<G->vexnum; j++){
if(G->arcs[j][i].adj != INFINIT){
indegree[i]++;
}
}
}
}
int TopologicalSort(MGraph *G, int *stackT, int *topT)
{
int indegree[MAX];
int stack[MAX];
int top = -1;
int w;
int i;
int count;
FindInDegree(G, indegree);
for(i=0; i<G->vexnum; i++){
if(!indegree[i]){
stack[++top] = i;
}
ve[i] = 0;
}
count = 0;
while(top>=0){
w = stack[top--];
stackT[++(*topT)] = w;
//printf(" %c->", G->vexs[w]);
++count;
for(i=0; i<G->vexnum; i++){
if(G->arcs[w][i].adj != INFINIT){
indegree[i]--;
if(indegree[i] == 0){
stack[++top] = i;
}
if(ve[w] + G->arcs[w][i].adj > ve[i]){
ve[i] = ve[w] + G->arcs[w][i].adj;
}
}
}
}
if(count < G->vexnum){
return 0;
}else{
return 1;
}
}
int CriticalPath(MGraph *G)
{
int i;
int j;
int stackT[MAX];
int topT = -1;
int tag;
int ee, el;
if(!TopologicalSort(G, stackT, &topT) ){
return 0;
}
for(i=0; i<G->vexnum; i++){
vl[i] = ve[G->vexnum-1];
}
while(topT>=0){
j = stackT[topT--];
for(i=0; i<G->vexnum; i++){
if(G->arcs[i][j].adj != INFINIT){
if( vl[j] - G->arcs[i][j].adj < vl[i] ){
vl[i] = vl[j] - G->arcs[i][j].adj;
}
}
}
}
for(j=0; j<G->vexnum; j++){
for(i=0; i<G->vexnum; i++){
if(G->arcs[j][i].adj != INFINIT){
ee = ve[j];
el = vl[i] - G->arcs[j][i].adj;
tag = (ee == el)? '*':' ';
printf("%c->%c len=%d ee=%d el=%d %c\n",
G->vexs[j], G->vexs[i],
G->arcs[j][i].adj, ee, el, tag);
}
}
}
}
void main()
{
MGraph G;
printf("log.anycle.com\n\n");
printf("Create graph:\n");
CreateUDN(&G);
printf("\n");
printf("Find critical path:\n");
CriticalPath(&G);
printf("\n");
}