Depth First Search DFS

/*
 * File:   DFS.c
 * Author: SUVO
 * suvayan92@gmail.com
 * Created on 08 June, 2013, 03:34 PM
 */

#include <stdio.h>
#include <stdlib.h>
#define SIZE 100
#define debugMode 0 //for debugging purpose, set to 1 if want to start in debug mode

typedef enum{
    FALSE, TRUE
}boolean;

//////***********Implementation of Stack *****************///
//this stack can be used in DFS traversal of the graph.
typedef struct {
    char item[SIZE];
    int top;
}Stack;

void push(Stack *sp, char val){
    if (sp->top == SIZE-1){
        printf("\n:( Unable to process more than 100 elements\n Stack Overflow\nterminating process");
        return;
    }
    sp->item[++sp->top] = val;
}
char pop(Stack *sp){
    if (sp->top == -1){
        printf("Stack Underflow\n terminating the process\n");
        exit(0);
    }
    return sp->item[sp->top--];
}

/////****************END OF STACK IMPLEMENTATION***************************//
////*****************IMPLEMEMTATION OF QUEUE FOR BFS TRAVERSAL*****************/
typedef struct {
    char item[SIZE];
    int rear, front;
}Queue;

void queueInsert(Queue *qp, char val){
    if ((qp->rear+1)%SIZE==qp->rear){
        printf(":( Unusual situation, Queue overflow\nTerminating the process\n");
        exit(0);
    }
    qp->rear=(qp->rear+1)%SIZE;//moving the rear to the next location circularly.  
     //now place the value at the rear
    qp->item[qp->rear] = val;
}

char queueRetrieve(Queue *qp){
    if (qp->rear==qp->front){
        printf(":( Unusual situation\nQueue Underflow\nTerminating process\n");
        exit(0);
    }
    //move the front to the next location circularly
    qp->front = (qp->front+1)%SIZE;
    return qp->item[qp->front];
}

typedef struct GraphNode{
    char nodeVal;
    int STATUS;//used for BFS, DFS traversal
    //STATUS=0, node is un-touched, initial state.
    //STATUS=1, node is inserted into the STACK (BFS)/QUEUE (DFS)
    //STATUS=2, node has been processed;
    struct GraphNode *next;  
}GraphNode;

typedef struct AdjList{
     GraphNode *adjListHead;
     int nodeCount;
     int edgeCount;
}AdjList;

////**********************END OF QUEUE IMPEMENTATION ********************////


//function prototype declarations

void allocateAdjList(AdjList *);
void insertAtHead(GraphNode **, char);
void insertNeighbor(AdjList *, char , char);
void inputNodes(AdjList *);
void displayGraph(AdjList*);
char * getNeibors(AdjList*, char, int);
void initializeNodeStatus(AdjList *);
void DFS(AdjList *, char);
void BFS(AdjList *, char);


void initializeNodeStatus(AdjList *ptrAdjList){
    //initializes each nodes status field to 0
    int i;          
    for(i=0;i<ptrAdjList->nodeCount;i++){  
        (ptrAdjList->adjListHead+i)->STATUS=0;
       
    }
             
}


GraphNode* setNodeStatus(AdjList * ptrAdjList, char nodeChar, int STATUS){
    int i=0;
    for(i=0;i<ptrAdjList->nodeCount;i++){
        if((ptrAdjList->adjListHead+i)->nodeVal==nodeChar){
            (ptrAdjList->adjListHead+i)->STATUS=STATUS;
            break;
        }
    }
    return (ptrAdjList->adjListHead+i)->next;//return the neighbor list
}
int getNodeStatus(AdjList *ptrAdjList, char nodeChar){
    int i=0;
    for(i=0;i<ptrAdjList->nodeCount;i++){
        if((ptrAdjList->adjListHead+i)->nodeVal==nodeChar){          
            break;
        }
    }
    return (ptrAdjList->adjListHead+i)->STATUS;
}

void BFS(AdjList *ptrAdjList, char startNodeVal){
    int i, found;
    Queue queue;
    char pCh;
    GraphNode *neighborList;
    //initialize the stack;
    queue.rear = SIZE-1;
    queue.front = SIZE-1;
    //initialize graph
    initializeNodeStatus(ptrAdjList);
    //check if start node exists
    found = FALSE;
    for(i=0;i<ptrAdjList->nodeCount;i++){
        if ((ptrAdjList->adjListHead+i)->nodeVal==startNodeVal){
           found = TRUE;
           break;
        }
    }
    if (!found){
        printf(" :( Start Node: %c not found\n", startNodeVal);
        return;
    }
    //if start node found push it into the stack
    queueInsert(&queue, (ptrAdjList->adjListHead+i)->nodeVal);
    //set the status of the start node to 1;
    (ptrAdjList->adjListHead+i)->STATUS=1;
    printf("BFS LIST: ");
    while(queue.rear!=queue.front){
        pCh = queueRetrieve(&queue);
        printf("%4c",pCh);
        neighborList = setNodeStatus(ptrAdjList,pCh,2);
        for(;neighborList!='\0';neighborList=neighborList->next){
            if (getNodeStatus(ptrAdjList,neighborList->nodeVal)==0){
                queueInsert(&queue, neighborList->nodeVal);
                setNodeStatus(ptrAdjList,neighborList->nodeVal,1);
            }
        }
    }
 
    printf("\n");
 
 
}


void DFS(AdjList *ptrAdjList, char startNodeVal){
    int i, found;
    Stack stack;
    char pCh;
    GraphNode *neighborList;
    //initialize the stack;
    stack.top = -1;
    //initialize graph
    initializeNodeStatus(ptrAdjList);
    //check if start node exists
    found = FALSE;
    for(i=0;i<ptrAdjList->nodeCount;i++){
        if ((ptrAdjList->adjListHead+i)->nodeVal==startNodeVal){
           found = TRUE;
           break;
        }
    }
    if (!found){
        printf(" :( Start Node: %c not found\n", startNodeVal);
        return;
    }
    //if start node found push it into the stack
    push(&stack, (ptrAdjList->adjListHead+i)->nodeVal);
    //set the status of the start node to 1;
    (ptrAdjList->adjListHead+i)->STATUS=1;
    printf("DFS LIST: ");
    while(stack.top!=-1){
        pCh = pop(&stack);
        printf("%4c",pCh);
        neighborList = setNodeStatus(ptrAdjList,pCh,2);
        for(;neighborList!='\0';neighborList=neighborList->next){
            if (getNodeStatus(ptrAdjList,neighborList->nodeVal)==0){
                push(&stack, neighborList->nodeVal);
                setNodeStatus(ptrAdjList,neighborList->nodeVal,1);
            }
        }
    }
 
    printf("\n");
 
 
}

void allocateAdjList(AdjList *ptrAdjList){
    //allocate the array of head pointers for holding
    //the list of neighbor for each node.
    //if the function returns 0 then memory allocation failed
    //otherwise on success it returns the size of memory allocated (a +ve value)
    int i=0;
    ptrAdjList->adjListHead = (GraphNode *)malloc(sizeof(GraphNode) * ptrAdjList->nodeCount);
    if (ptrAdjList->adjListHead=='\0'){
        printf(":( Unable to allocate memory\nterminating the programe\n");
        exit(0);
    }
    //initialize head of each list
    for(i=0;i<ptrAdjList->nodeCount;i++){      
        ptrAdjList->adjListHead[i].next = '\0';
    }      
}

void insertAtHead(GraphNode **hp, char nodeValue){
    //inserts a node at the head of the linked list
    //hp is the pointer to the head (actually its the next pointer of the AdjList node array.)
    GraphNode *p;
    //create a new node.
    p = (GraphNode*)malloc(sizeof(GraphNode));  
    if (p == '\0'){
        printf("Unable to allocate memory for node\nterminating application\n");
        exit(0);
    }
    p->nodeVal = nodeValue;
    p->next = *hp;
    *hp = p;
}


void insertNeighbor(AdjList *ptrAdjList, char targetNode, char neighborNode){  
    //inserts the neighborNode as the neighbor of the targetNode;
    int i=0;

 
   if (debugMode)
     printf("@Debug %c-%c\n",targetNode,neighborNode);
 
 
   for(i=0;i<ptrAdjList->nodeCount;i++){
       if ((ptrAdjList->adjListHead+i)->nodeVal==targetNode){
           insertAtHead( &((ptrAdjList->adjListHead[i]).next),neighborNode);
       
       }
       else if ((ptrAdjList->adjListHead+i)->nodeVal==neighborNode){
           insertAtHead( &((ptrAdjList->adjListHead[i]).next),targetNode);        
       }
   }
}

void inputNodes(AdjList *ptrAdjList){
    int i=0;
    if (ptrAdjList->nodeCount==0)
        return;
    for(i=0;i<ptrAdjList->nodeCount;i++){
        printf("Next Node [characters allowed only(a,b,c,1,2,3 ....)]: ");
        scanf(" %c",&((ptrAdjList->adjListHead+i)->nodeVal));
    }
}

void inputEdges(AdjList *ptrAdjList){
    int i=0, ec,nc;
    char firstNode, secondNode;
    if (ptrAdjList->nodeCount==0)
        return;
    nc = ptrAdjList->nodeCount;
 
    do{
        printf("How Many edges: ");
        scanf(" %d",&ec);
        if (ec>((nc*(nc-1))/2))
        printf(" Invalid Number of edges...\ntry input again \n");
    }while(ec>(nc*(nc-1))/2);
 
    ptrAdjList->edgeCount=ec;
 
    for(i=0;i<ptrAdjList->edgeCount;i++){
        printf("Enter edge in the format a-b (if a,b forms an edge): ");      
        scanf(" %c%*c%c",&firstNode,&secondNode); //skipping the minus sign
     
     
        //insert the neighbour into the adjList
        insertNeighbor(ptrAdjList,firstNode, secondNode);
    }
 
}

void displayGraph(AdjList *ptrAdjList){
    int i,k=0,t;
    char nodeVal;
    GraphNode *p;
    boolean alreadyDisplayed;
    char displayed[ptrAdjList->edgeCount][ptrAdjList->edgeCount];
 
    printf("\n\tV={");
    for(i=0;i<ptrAdjList->nodeCount;i++){
        printf("%4c,",(ptrAdjList->adjListHead+i)->nodeVal);
    }
    printf("\b }\n\tE={");
    for(i=0;i<ptrAdjList->nodeCount;i++){
        nodeVal = (ptrAdjList->adjListHead+i)->nodeVal;
        if(debugMode){
            printf("@Debug: %c\n",nodeVal);
        }
        for(p=(ptrAdjList->adjListHead+i)->next;p!='\0';p=p->next){
            alreadyDisplayed= FALSE;
            for(t=0;t<k;t++){
                if ((displayed[t][0]==nodeVal && displayed[t][1]==p->nodeVal)||
                        (displayed[t][0]==p->nodeVal && displayed[t][1]==nodeVal)){
                    alreadyDisplayed=TRUE;
                    break;
                }
            }
            if(!alreadyDisplayed){
                printf("%c-%c,",nodeVal,p->nodeVal);
                displayed[k][0] = nodeVal;
                displayed[k++][1] = p->nodeVal;
            }
        }
     
    }
    printf("\b }\n\n");
}

int main(int argc, char** argv) {
    AdjList adjList;
    int choice;char startNode;
    printf("Enter total Number of Nodes: ");
    scanf(" %d",&adjList.nodeCount);
 
 
    allocateAdjList(&adjList);
    inputNodes(&adjList);
    inputEdges(&adjList);
 
    do{
        printf("1. BFS\n");
        printf("2. DFS\n");
        printf("3. Display\n");
        printf("4. Both DFS & BFS\n");
        printf("5. Exit\n");
        printf("Please enter your choice: ");
        scanf(" %d", &choice);
        switch(choice){
            case 1:printf("Enter Start Node: ");
                   scanf(" %c",&startNode);
                   BFS(&adjList,startNode);
                   break;
            case 2:printf("Enter Start Node: ");
                   scanf(" %c",&startNode);
                   DFS(&adjList,startNode);
                   break;
         
            case 3:displayGraph(&adjList);
                        break;
            case 4:printf("Enter Start Node: ");
                   scanf(" %c",&startNode);
                   DFS(&adjList,startNode);
                   BFS(&adjList,startNode);
                   break;
            case 5:exit(0);
            default: printf("Invalid Choice\n");                                
        }
     
 
    }while(1);
 
    return (EXIT_SUCCESS);
}