# Adjacency List: Path counter nonfunctional

I'm implementing a queue for an adjacency matrix, in a program that finds the shortest path between two nodes. But my path counter isn't being incremented and I can't see why. Any help would be greatly appreciated.

Here's the file adj.data which the program draws from:

1 2 2 3 3 4 2 5 5 6 6 3 6 7 4 8 5 8 8 1

Here's the code.

//------------------------Preprocessor Instructions. ------------------------------------ #include <stdio.h> #include <stdlib.h> #include <strings.h> #define MAX 128 //Max number of nodes in the graph. #define BUFFER 120 //Buffer length. //------------------------Global Stuff. ------------------------------------------------- int adjacency[MAX][MAX]={0}; int visited[MAX]={0}; int queue[MAX]; int head=-1; int tail=-1; int hops; //------------------------Function Defintions. ------------------------------------------ int path(int src, int dest); void QueuePush(int num); int QueuePop(); int IsEmpty(); //------------------------Main. --------------------------------------------------------- /* Main writes the file data to the adjacency matrix, and parses command line args. */ int main(int argc, char **argv) { FILE *fp; //File pointer. char buffer[BUFFER]; //Temporary storage int src; //Location a int dest; //Location b int retval; int tempa=0; int tempb=0; //Temporary variables for reading from file to array. int i=0; int j=0; //Loop counters. //Command Line Argument Parsing: Assigns inputs to variables. if (argc != 3){ printf("Usage: %s #a #b. \n",argv[0]); //Usage: *program* *# #* return(1); } if (1 != sscanf(argv[1],"%d", &src)){ //Parses first integer. printf("Usage: %s #a #b. \n",argv[0]); return(1); } if (1 != sscanf(argv[2], "%d", &dest)){ //Parses second integer. printf("Usage: %s #a #b. \n",argv[0]); return(1); } printf(" Source: %d \n Destination: %d \n", src, dest); //File reading. fp=fopen("adj.data","r"); if(NULL==fp){ printf("Error opening file. \n"); exit(0); } //Save file to array. while(NULL != fgets(buffer, BUFFER, fp)){ sscanf(buffer, "%d %d", &tempa, &tempb); adjacency[tempa][tempb]=1; //Assign 1 to locations (Making the adjacency matrix) } fclose(fp); //Printing list for convenience. for(i=0;i<MAX;i++){ for(j=0;j<MAX;j++){ if(1==adjacency[i][j]){ printf(" %d --> %d \n", i, j); //Prints the graph as list. } } } retval=path(src, dest); if(0==retval){ printf("There is no path from %d to %d. \n", src, dest); } else{ printf("%d is %d hops away from %d. \n", src, hops, dest); } printf("Path returned %d \n", retval); } //------------------------Path function. ------------------------------------------------ /* The path function is where the work is done for the Shortest Path algorithm. Puts a source node onto the queue, and then adds the nodes directly connected. Checks to see if any of the nodes on the queue are the destination node, and if they are it returns the number of hops. Otherwise it keeps adding and checking until it either finds a path or reaches the end of the queue. */ int path(int src, int dest) { int node; int i; QueuePush(src); //Pushes source node onto queue. //While the queue isn't empty, while(0==IsEmpty) { node=QueuePop(); //Pop the head of the queue hops=QueuePop(); //Pop the next number, which will be the hops value. //If popped value is equal to target, we're done! if(node==dest){ return 1; } //If the node has been visited before, do nothing. if(visited[node]==1){} else { //Otherwise, search for connected nodes and add them to queue. hops=hops+1; for(i=0;i<MAX;i++){ if(adjacency[node][i]==1){ //If one exists, push onto queue. QueuePush(i); visited[node]=1; } } } } return 0; } //------------------------Push function for Queue. -------------------------------------- void QueuePush(int num) { //If queue is empty, if(-1==head && -1==tail){ head=0; tail=0; queue[tail]=num; //Add a node. tail++; //Incremement the tail(Queue no longer empty) queue[tail]=hops; //Place number of hops right after the node. } //If tail is about to hit the end, else if((tail==(MAX) || (tail==(MAX-1)) && (head != 0 || head != 1))){ tail=0; //Bring the tail to the front. (Circular Queue) queue[tail]=num; //Place node in last queue spot tail++; queue[tail]=num; //Place number of hops right after the added node. } //Otherwise, else{ tail++; queue[tail]=num; tail++; queue[tail]=hops; } } //------------------------Pop function for Queue. --------------------------------------- int QueuePop() { int node; //Will be the first thing on the queue. node=queue[head]; //If the head and tail are equal, the queue is empty. if(head==tail){ head=-1; tail=-1; } //If the queue is at the end, loop it around. (Circular Queue) else { if(head==MAX){ head=0; } else{ head++; } } return(node); //Returns the next node. } //------------------------Function to check if the queue is empty. ---------------------- int IsEmpty() { //If queue is empty, if(-1==head){ return 1; } //Otherwise, else { return 0; } }

Thanks in advance.

## Answers

The following line will never be true because IsEmpty is a pointer to a function and is never 0.

while(0==IsEmpty)

What you wanted to say is

while(0==IsEmpty() )

which *calls* the function and checks the return value.

This is not related to your problem but I recommend you to use STL queue instead of writing your own queue function. By this you can save yourself from doing many errors.

I think your assumption of having queue full is also wrong. The circular queue will be full when **tail-head == MAX** or **head-tail == 1**.