Task 10

/* * @author Tenzin Dakpa * @mat no. 5751 * @task 3,4 * @Assignment 9 * @date 4 may 2009 *---------------------------------------------------------------------*------------The reason behind the solution-----------------------------* a critical node C in a connected graph between S and T implies that * in any valid path between S and T , c must be present. * moreover, if C is removed any and all path between S and T is broken. * Therefore to detect such a critical node , one can find the shortest * path between S and T, then check one by one each node for criticality * by hiding the node and checking that the connection remains unbroken. * If the connection is broken, then we have found a critical node. * -----------The DFS cost(time)----------------------------------------* Cost of getting the path using the Adjacency list E(a single DFS call) + * Cost of checking if each node in path is critical[there can be (V-2) * nodes on the path as the starting and the end node is not usefull. The * cost is obtained by multiplying this number with cost of doing DFS (V+E)on * the start node.]=(V-2)(V+E) * Total Worst case cost O =(V-2)(V+E) + E * ---------------------------------------------------------------------* -----------The BFS cost(time)----------------------------------------* Cost of getting the path using adjacency matrix (V+E) + * Cost of checking if each node in path is critical[ (V-2)times (V+E)]= * (V-2)(V+E) * Total Worst case cost O=(V-1)(V+E) * ---------------------------------------------------------------------* */ #include <stdio.h> #include <malloc.h> #define N 9 typedef enum {white, gray, black} Color; typedef enum {FALSE, TRUE} bool; typedef struct vertex { char name; Color clr; struct vertex* pred; // index of previous vertex in the traversal bool critical; // bool hidden; // usefull in hidding the node struct vertex* adjacent[N];//adjacent vertex as per DFS int time;/*While used as time Counter in DFS, it is reused as the dist counter in BFS*/ } Vertex; Vertex* V[N]; // array of all vertexes typedef struct queue/* a simple queue.with head and tail */ { int data;// just the index of the vertex in the global array of vertex. struct queue *next; }Q; Q* bfsQueue=NULL; Q* tail=NULL;

int time = 0; // a global variable to account /* adjacency matrix */ int Adj[N][N] = { /*S B C D E F G H {0, 1, 1, 0, 0, 0, 0, 0, {1, 0, 0, 1, 1, 0, 0, 0, {1, 0, 0, 0, 1, 0, 0, 0, {0, 1, 0, 0, 0, 1, 0, 0, {0, 1, 1, 0, 0, 1, 0, 0, {0, 0, 0, 1, 1, 0, 1, 1, {0, 0, 0, 0, 0, 1, 0, 1, {0, 0, 0, 0, 0, 1, 1, 0, {0, 0, 0, 0, 0, 0, 1, 1, };

T 0}, 0}, 0}, 0}, 0}, 0}, 1}, 1}, 0},

// // // // // // // // //

*/ S B C D E F G H T

/*---common function---*/ void initMemory(void);// populate the vertex array with vertex void init(void); // set the color and predecessor to starting conditions void setName(void); // set the label of vertex bool isUnreliableConnected(Vertex* u, Vertex* v,int Al);/*the third parameter chooses which graph algorithm is used. BSF==0, DFS ==1*/ /*---BFS---*/ void enque(int data); // fifo queue : enque function int deque(void); // fifo queue : deque function void BFS(int u); // BFS algorithm.using the adjacency matrix. /*---DFS---*/ void setAdjList(void);//converting the adjacency matrix into adjacent list for DFS void DFS(Vertex* u); //DFS Algorithm //A function to test if two vertex are reliably connected using DFS int main() /*----------------main-------------------------*/ { /*---set the initial states---*/ initMemory(); init(); setName(); /*---hide a node to verfy Algorithm runs in expected way---*/ //V[6]->hidden=TRUE; /*---using the function for BFS ---*/ if(isUnreliableConnected(V[0],V[8],0)==TRUE) { printf("\n(BFS)*is Unreliable*(BFS)\n\n"); } else printf("\n(BFS)*|* Reliable *|*(BFS)\n\n"); /*-------for DFS: set the Adj list-------*/ setAdjList(); /*----------reset all state --------*/ init(); if(isUnreliableConnected(V[0],V[8],1)==TRUE) { printf("\n(DFS)***is Unreliable***(DFS)\n\n"); }

else printf("\n(DFS)*|*|* Reliable *|*|*(DFS)\n\n"); } /*----------------end-of-main-------------------------*/ bool isUnreliableConnected(Vertex* u, Vertex* v, int Al) { bool answer=FALSE; int uint=0; while(V[uint]!=u)/*get the address of the starting Vertex */ { uint++; } if (Al==0)/* CALL THE APPROPRIATE GRAPH ALGORITHM*/ { BFS(uint);}//using BFS to set the path} else { DFS(u); } if(v->pred!=NULL) { /*keep the list of path nodes and remove one and check.*/ Vertex* path[N];/*saving nodes found on the path*/ int i=0; Vertex* j= v; while(j->pred!=u) {j=j->pred; path[i]=&(*j); printf("(%d, %c) -> ",i,path[i]->name); i++; } printf("\nNodes found on path %d \n",i); int k=0; for(k=0;kpred=NULL; j=path[k]; init(); j->hidden=TRUE; if (Al==0)/* CALL THE APPROPRIATE GRAPH ALGORITHM*/ { BFS(uint);} else {DFS(u); } j->hidden=FALSE; if(v->pred==NULL) { printf("One critical node found at %c \n",j->name); j->critical=TRUE; answer=TRUE; }else { printf("Not a critical node %c \n",j->name); } } } else printf(" doesnt exist s-t path\n"); return answer; } void BFS(int u){

V[u]->clr = gray; int j,i=0; enque(u); V[u]->time=time; int temp=-1; while(bfsQueue!=NULL){ temp=bfsQueue->data; for(j = 0; j < N; j++) { if(Adj[temp][j]==1){ if(V[j]->clr == white && V[j]->hidden==FALSE){ enque(j); V[j]->clr=gray; V[j]->pred = V[temp]; V[j]->time= V[temp]->time+1; } }

}

} V[temp]->clr=black; deque();

} void enque(int data){ if (tail!=NULL){ tail->next=(Q*)malloc(sizeof(Q)); tail=tail->next; tail->data=data; tail->next=NULL; } else{ bfsQueue=(Q*)malloc(sizeof(Q)); bfsQueue->data=data; bfsQueue->next=NULL; tail=bfsQueue; } } int deque() { if(bfsQueue!=NULL) {int temp= bfsQueue->data; Q* temp2= bfsQueue; if(bfsQueue==tail){ tail=NULL; } bfsQueue=bfsQueue->next; free(temp2); return temp; }else return -1; } void initMemory(void){ int i; for(i = 0; i < N; i++){ V[i]=(Vertex*)malloc(sizeof(Vertex));

V[i]->hidden=FALSE; V[i]->time=-1;

} } void init(void){ int i; for(i = 0; i < N; i++){ V[i]->clr = white; V[i]->pred = NULL; V[i]->time =-1; } }

void setAdjList(void)//converting the adjacency matrix into adjacent list for DFS { int j,i,k; for(i = 0; i < N; i++) { k=0; for(j = 0; j < N; j++) { if(Adj[i][j]==1){ V[i]->adjacent[k]=V[j]; k++; // printf("\n %d , %d , K %d",i , j,k); } }V[i]->adjacent[k]=NULL; } } void setName(void) { int i; char names [N+1]="SBCDEFGHT"; for(i = 0; i < N; i++){ V[i]->name=names[i]; } } void DFS(Vertex* u){ u->clr = gray; int j; Vertex* k=NULL; for(j = 0; j < N; j++) { k=u->adjacent[j]; if(k==NULL){ j=N; }else if(k->clr == white && k->hidden==FALSE) { k->pred = u; DFS(k); } } u->clr = black; return ; }

/* testing the fifo queue for bfs enque(V[0]); enque(V[1]); enque(V[2]); enque(V[0]); enque(V[1]); enque(V[8]); printf("\n s = %c",(deque())->name); printf("\n b = %c",(deque())->name); printf("\n c = %c",(deque())->name); printf("\n s = %c",(deque())->name); printf("\n b = %c",(deque())->name); printf("\n T = %c",(deque())->name); enque(V[0]); enque(V[1]); enque(V[2]); enque(V[0]); enque(V[1]); enque(V[8]); printf("\n s = %c",(deque())->name); printf("\n b = %c",(deque())->name); printf("\n c = %c",(deque())->name); printf("\n s = %c",(deque())->name); printf("\n b = %c",(deque())->name); printf("\n T = %c",(deque())->name);*/