Thread: adjacency list

Hey andruli,
It was a segmentation error that i fixed but I think my find node function is not working . I was using the pseudo code u helped with.
This function finds the node that has value passes as the start value.
it should return a pointer to that node but it stops at
while(ptr != NULL)
in the function

Code:

struct mainList *find_node( int value)
{
	struct mainList *ptr = *pHead;
	while(ptr != NULL)
		
    {
		if(value == ptr->nodeNum)
		{
			printf("The found node is %d", ptr->nodeNum);
			ptr = ptr->pNext;}
		 }
	
	return ptr;
}
}

And m not following why is not working?
thanks

Your { } are all screwy. Keep your code well formatted to make sure your braces line up properly and your lines are correctly indented so you can be certain of what code belongs to which block. Post your code here with proper formatting so it's easier for us to read. Then, look at the instructions inside the if statement. You use the if statement to check if you found the node, but then what do you do?

Code:

struct mainList *find_node( int value)
{
  struct mainList *ptr = *pHead;
  
  while(ptr != NULL)
    {
      if(value == ptr->nodeNum)
	{
	   printf("The starting node is : %d \n", ptr->nodeNum);  
	}
      ptr = ptr->pNext;
    }
  return ptr;
}

it worked again... the program compiles perfectly and runs too .
But it doesnt give the desired output.

the main BFS function also seems fine now

Code:

void BFS( int start1, int goal)
{
  struct mainList *start, *search;
  struct mainList *search1;
  struct adjList *pt;
  struct Q *queue;
  // returns a pointer to the mainList node with nodeNum start
  start = find_node( start1);
  // put the the found node in a queue
  queue = Insert_Queue( start, queue);
  //while queue is not empty
  while (queue) 
    {
      // Extract the first node to search
      queue = Delete_Queue(search, queue);
      //while the there is something poped out
      while (queue != NULL)
	{
	  pt = search1->pAdjListHead;
	  // look for the adjacent nodes of the extracted node
	  while (pt != NULL)
	    {
	      // if the any of the adjacent nodes is equal to the goal, stop the search
	      if(goal == pt->nodeNum)
		{
		  printf("We Found the goal");
		
		}
 
	      else 
		{
		  // else say the node is visited 
		  search->nodeNum = T;
		  // inderted the adjacent nodes to the queue again and repeat it
		  queue = Insert_Queue(search1->pNext, queue);
		}
	    }
	  pt = pt->pNext;
	}
    }
}

can u please comment on the logic ..m using here.

thanks

Look at my comments in post #24! We went over this already. What should your find function do when it finds the desired node? That is, what should be inside the if (value == ptr->nodeNum)?

My find function should give the adjacent nodes for the start nodes.
like

Code:

struct mainList *find_node( int value)
{
  struct mainList *ptr = *pHead;
  struct adjList *ptr2 = NULL;
  while(ptr != NULL)
    {
      if(value == ptr->nodeNum)
	{
	  ptr2 = ptr->pAdjListHead;
	  while(ptr2 != NULL)
	    {
	      ptr2 = ptr2->pNext;
	    }
	  printf("\n");
	  
	}
      ptr = ptr->pNext;
    }
  return ptr2; //  I guess m returning wrong pointer
}

I was unable to pass to the pointer to the adjacent nodes to Insert queue. So , I tried finding the adjacent nodes in BFS like above post.

Why should your find function give the adjacent nodes for the start node? This should throw hideous compiler warnings because you have a function that returns a mainList *, but you're trying to return an adjList *. Not to mention, you find the correct start node, then set ptr2 to the list of adjacent nodes and iterate until the end. Then you return ptr2, which has to be NULL otherwise the while (ptr2 != NULL) loop would be infinite. So this function always returns NULL.

Your find function should simply search a list of mainList nodes and return a pointer to the node if it's found, or NULL otherwise. Nothing more, nothing less.

You were so close with your BFS function in post #25. All you needed to do was drop the first call to Delete_Queue, fix the parameters to the second call to Delete_Queue and ditch the while (search1 != NULL) loop.

hey! This is the recent improvement i made.

When i compile I get the following errors:
A.c: In function 'Insert_Queue':
A.c: warning: assignment makes integer from pointer without a cast
A.c: In function 'Delete_Queue':
A.c: warning: assignment makes pointer from integer without a cast

n when i run i get the segmentation error.
When i use gdb to debug i get
Program received signal EXC_BAD_ACCESS, Could not access memory.
Reason: KERN_INVALID_ADDRESS at address: 0x0000000000000000
0x0000000100001bb8 in BFS (start1=5, goal=8) at Adj_mod7.c:284
284 if (goal == queue->info ) {

I tried correcting the warnings but still can get it running fine.
i am posting the main functions for the BFS thing

Code:

struct mainList *find_node( int value)
{
  struct mainList *ptr = *pHead;
  struct adjList *ptr2 = NULL;
  while(ptr != NULL)
    {
      if(value == ptr->nodeNum)
	{
	  ptr2 = ptr->pAdjListHead;
	  while(ptr2 != NULL)
	    {
	      ptr2 = ptr2->pNext;
	    }
	  printf("\n");
	}
      ptr = ptr->pNext;
    }
  return ptr; 
}

struct Q *Insert_Queue(struct mainList *vertex_no, struct Q *first)
{
  struct Q *new1, *current;
  new1 =(struct Q *) malloc(sizeof(struct Q));
  new1->info = vertex_no;   // this a warning , i know of I also tried pointing it to vertex->nodeNum
  new1->next = NULL;
  if (!first)
    return (new1);
  for (current = first; current->next; current = current->next);
  current->next = new1;
  return (first);
}

struct Q *Delete_Queue(struct mainList *vertex_no, struct Q *first)
{
  struct Q *previous;
  previous =(struct Q *) malloc(sizeof(struct Q));
  if (!first)
    return (NULL);
  vertex_no= first->info;
  previous = first;
  first = first->next;
  free(previous);
  return (first);
}	

struct Q *insert_unvisited_children(struct Q *queue, struct mainList *search)
{
  struct adjList *adj_node;
  struct mainList *main_node;
  for (adj_node = search->pAdjListHead; adj_node; adj_node = adj_node->pNext)
    {
      // find the mainList node for this adjList node
      main_node = find_node( adj_node->nodeNum);
      // if main_node has not been visited, insert it in queue
      if(main_node->visited == F )
	queue = Insert_Queue(main_node->pNext, queue); 
    }
  return queue;
}

void BFS( int start1, int goal)
{
  struct mainList *start, *search, *search1;
  struct Q *queue;
  // returns a pointer to the mainList node with nodeNum start
  start = find_node( start1);
  queue = Insert_Queue( start, queue);
  while (queue) 
    {
      // extract next node to search
      queue = Delete_Queue(search, queue);
      //  search1 = Delete_Queue(search, queue);
      if (goal == queue->info ) {
	// we found our node, act accordingly
	printf("We found the goall\n");
      }
      else 
	{
	  // set visited to true for search
	  queue = insert_unvisited_children(queue, search);
	  search->visited = T;
	}
    }
}

The info field of a struct Q is of type int but vertex_no is a struct mainList *. You can't just assign these two to eachother. Also, I still don't think your find_node function works. From my post #16:

Code:

for (ptr = pHead; ptr; ptr = ptr->next) {
    if (ptr->value == value) {
        break;
    }
}

return ptr;  // if we found the node, this will point to it, otherwise it will be null

Thanks for all the help till now.
I am almost through the code. (no warnings/ no errors)

But i got stops at
if (goal == queue->info )
while my my delete and insert queue function fine too....
it gives me segmentation fault.Seems like I am doing something wrong memeory allocation but dont know where.

I can't say for sure without the newest version of all your code. My suspicion, however, is that queue is null, so queue->info gives a segmentation fault. Since you know it crashes on that line, look in the debugger and see what value is in queue.

@satty: I just read your message. Please post your pastebin link and any other comments/questions here as I rarely check my messages unless I'm expecting one. Besides, others can look at your code and give more advice as well. Maybe I've been missing something, since we seem to be running around still with no solution.

Hello!
Thanks a lot andruli .I sorted it out n it worked.
thanks again