Thread: adjacency list

It might help to read up on BFS first. Wikipedia has a good article here: Breadth-first search - Wikipedia, the free encyclopedia and Google has a few decent links: bfs with adjacency list - Google Search.

The algorithm is roughly this:

Code:

find your start node
put it in a FIFO queue of "to be searched" nodes
while (queue is not empty)
    dequeue the node
    if it's the node we're searching for
        stop, report it and exit
    else
        mark that node as visited
        enqueue all of it's unvisited neighbors (adjacent nodes)

I suggest not putting your search code inside the "find start node" loop:

Code:

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

if (!ptr) {
    // couldn't find start node, bail out
}

// BFS code goes here

You will most likely need to add a small data structure or two for the BFS and need to modify your adjacency list to track if a node has been visited. Take a crack at that and see what you come up with.

hello!
I tried something like this and it worked but i guess it is not an appropriate way to go

Code:

void SearchAndPrintList(int value, int value2)
{
  
  int i;
  //int array = malloc(20)
  struct mainList *ptr = *pHead;
  struct adjList *ptr2 =  NULL;
  for (i = 0 ; i < MAX; i++){
    if (array[i]== value)
      return;
    else if(array[i]==-1)
      break;
  }
   while(ptr != NULL)
   {
      if(value == ptr->nodeNum)
	{
	  printf("%d ,", ptr->nodeNum);
	  array[i]= ptr->nodeNum;
	  if (ptr->nodeNum == value2)
	    {
	      exit(0);
	    }
	  ptr2 = ptr->pAdjListHead;
	  while(ptr2 != NULL)
	    {
	      //   ptr2->pNext = (struct adjList *)malloc(sizeof(struct adjList));
	      //    printf("%d \n", ptr2->nodeNum);
	     
	      SearchAndPrintList(ptr2->nodeNum, value2);
 ptr2 = ptr2->pNext;
	    }
	  //	  printf("\n");
	  //	  return;
	  	}
      ptr = ptr->pNext;
    }
   // printf("NODE NOT FOUND!\n");
  }

and now I was trying using queue data structure and following the BFS algo but i failed miserably...have no clue whats going wrong

Code:

void BFS(int start)
{
  struct Q *queue = NULL;
  struct mainList *ptr = *pHead;
  struct adjList *ptr2 = NULL;
  
  while(ptr != NULL)
    {
      if(start == ptr->nodeNum)
	Visited = T;   /// i dont know how shouldI should keep track of the visited nodes 
      queue = Insert_Queue(start, queue);
      {
	
	printf("ADJ List for: %d -> ", ptr->nodeNum);
	ptr2 = ptr->pAdjListHead;
      }
      while(ptr2 != NULL && queue != NULL)
	
	{
	  queue = Delete_Queue(&start, queue);	
	  printf("%d ", ptr2->nodeNum);
	  ptr2 = ptr2->pNext;
	  queue = Insert_Queue(ptr, queue)
	    
	    }
      printf("\n");
      
    }
  ptr = ptr->pNext;
}

So for starters, you will need to have a visited flag in your struct adjList structure. You should initialize it to false/0 when you create the node. Then, you may want a few helper functions, like find_node(int val) that looks for the node in an adjacency list whose value is val, and returns a pointer to the node if found, or NULL otherwise, and something like Insert_Unvisited_Children that inserts all unvisited children from a specified node into the queue. Your Q structure also needs to hold pointers to actual adjList structs from mainList.

It would really help if I had enough code to compile and test this, and play with modifying it, or at the very least your type definitions for your mainList, adjList and Q structs, and your queue functions.

hey!
I am doing something like this
I made a structure and queues : to insert ans delete

Code:

struct Q
{
  int info;
  struct Q *next;
};

Code:

struct Q * Insert_Queue(int vertex_no, struct Q *first)
{
struct Q *new1, *current;
new1 =(struct Q *) malloc(sizeof(struct Q));
new1->info = vertex_no;
new1->next = NULL;
if (!first)
return (new1);
for (current = first; current->next; current = current->next);
current->next = new1;
return (first);
}

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

and my BFS code

Code:

void BFS(int value)
{
  struct Q *queue = NULL;
  int i;
  int visited[i];  //store the visited nodes
  for (i = 0; i < 10;i++){   // time being I say I have 10 nodes
    visited[i]= F; // F says it is false, no node is visited yet.
 }
  
  struct mainList *ptr = *pHead;  // the head pointer to the mainList
  struct adjList *ptr2 = NULL;  
  
  
  if(value == ptr->nodeNum) // we start our search with the user input and define start node as value
    {
      ptr2 = ptr->pAdjListHead; // ptr takes the pointer to the adajcency list
      while(ptr2 != NULL) // while there are adajcecnt nodes
	{
	  printf("%d ", ptr2->nodeNum); // get the adjacent nodes
	  ptr2 = ptr2->pNext; //ptr now points to the pointer of the next node
	  Insert_Queue(ptr2->pNext->nodeNum, queue); // we put all the adajcent nodes in the queue
	  
	}
      while(queue != NULL) // while queue is not empty
	{
	  queue = Delete_Queue(&value, queue);// take the first node out of the queue
	  if(value != visited[i]); // if the first value is not in the visited array , put it there and
	  Insert_Queue(value,queue) // insert its adajcent nodes in queue again
	    }
	  printf("\n");
	  
	}
  ptr = ptr->pNext; // Move on to the next pointer
    }
  printf("NODE NOT FOUND!\n");
}

that doesnt do anything at the moment.

Your queue structure should contain pointers to adjList nodes, not the integer value of the node. Your Insert and Delete functions seem fine, and should more or less work when you change your queue structure. Your BFS code wont even compile due to some syntax errors. As I mentioned before, you have to add a visited flag to the adjList node itself. You can't track it in some array.

It would still be really helpful if I could see your data structures for mainList and adjList.

Sure! I tried using Flag thingi but I did it well from wahtever I read n all

the strucutres that I am using for main list and adjacecny list are


// Adjacency List Structure

Code:

struct adjList {
	// Adjacent Node
	int nodeNum;
        //probability 
       float prob;
	// Next Node pointer
	struct adjList* pNext;
};

// Main List Structure
struct mainList
{
	int nodeNum;
         float prob;
	// Adjacency List Pointer
	struct adjList* pAdjListHead
	// Next Node pointer
	struct mainList *pNext;
};

I have sort of stuck now

Ok, so you need to add an int called visited to the definition of struct mainList. Make sure it's initialized to false when you create the node. Then, here is a shell of what you need for your bfs (I left some stuff for you to implement). Note that this is totally untested, but should get you going in the right direction:

Code:

struct mainList *find_node(struct mainList *list, int value)
{
    // loop through list looking for a node with nodeNum equal to value
    // if you find it, return a pointer to that node, otherwise return NULL
}

struct Q *insert_unvisited_children(struct Q *queue, struct mainList *search, struct mainList *nodes)
{
    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(nodes, adj_node->nodeNum);
        // if main_node has not been visited, insert it in queue
    }

    return queue;
}

void BFS(struct mainList *nodes, int start, int goal)
{
    struct mainList *start, *search;
    struct Q *queue;

    // returns a pointer to the mainList node with nodeNum start
    start = find_node(nodes, start);
    if (!start) {
        // bail out
    }

    queue = Insert_Queue(queue, start);
    while (queue) {
        // extract next node to search
        queue = Delete_Queue(&search, queue);

        if (search->nodeNum == goal) {
            // we found our node, act accordingly
        }
        else {
            // set visited to true for search
            insert_unvisited_children(queue, search, nodes);
        }
    }
}

Hello anduril462 .Thanks a lot till now. I tried the above template to implement in my code but something is really messing up things.

Firstly I have initialized a member in mainList called int visited. But i write int visited = F, my code goes all the way full with error saying that pNext is not a member of mainList.

Other Issue is that in BFS it doesn't like to get two variables with the same name start that I changed accordingly .
Also, it doesnt like the first value of the Delete_queue. I tried changing it too...but still deosnt work.
coz it needs a pointer to int valu and not struct i guess. I tried changing it to
queue = Delete_Queue(&search->nodeNum, queue);
and the overall error i get is Segmentation error. The code I was trying is

Code:

void BFS(struct mainList *nodes, int start1, int goal)
{
  struct mainList *start;
 struct mainList *search;
    struct Q *queue;

    // returns a pointer to the mainList node with nodeNum start
    start1 = find_node(nodes, start1);
struct mainList *find_node(struct mainList *list, int value)
{
  // loop through list looking for a node with nodeNum equal to value
  // if you find it, return a pointer to that node, otherwise return NULL
  //list = *pHead;
  while(list != NULL)
    {
      if(value == list->nodeNum)
	{
	  list= list->pNext;
	}
      else 
return 0;
    }

}

    /*  if (!start) {
        // bail out
    }
    */

    queue = Insert_Queue( start1, queue);
    while (queue) {
        // extract next node to search
        queue = Delete_Queue(&search->nodeNum, queue);

        if (search->nodeNum == goal) {
	  printf("we found out Goal\n");
	  printf("%d", goal);
	  return ;
            // we found our node, act accordingly
        }
        else {
            // set visited to true for search
	  search->visited = T;
            insert_unvisited_children(queue, search, nodes);
struct Q *insert_unvisited_children(struct Q *queue, struct mainList *search, struct mainList *nodes)
{
  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(nodes, adj_node->nodeNum);
    // if main_node has not been visited, insert it in queue
    if(main_node->visited = F )
      queue = Insert_Queue(main_node->nodeNum, queue); 
 }
 return queue;
}
        }
    }
}

the coloured codes in the BFS code are obviously written separately. I wrote in BFS just fro posting it to the forum .
Please have a look. I am stuck at the very last step now.

Code:

start1 = find_node(nodes, start1);

This is not correct. start1 is an in, but find_node returns a pointer to a struct mainList. You want start = find_node(). I know I screwed up a bit int the example, but you have to think through the algorithm and figure out what makes sense in terms of where you need an int and where you need a pointer.

Your find_node is broken. If list is the node we're looking for, you set list to list->pNext, and if it's not the node we're looking for, you return 0. It needs to look like this:

Code:

while (list) {
    if this is the node we're looking for {
        return list
    }
    list = list->pNext
}
return NULL

Your insert and delete queue functions need to take pointers to mainList nodes, not just ints. It's a queue of nodes.

Code:

insert_unvisited_children(queue, search, nodes);

I forgort this in my example, but you need to assign this to queue, like so:

Code:

queue = insert_unvisited_children(queue, search, nodes);

otherwise there will be problems when you try to do this with an empty queue (e.g. first time through the loop).

Code:

if(main_node->visited == F )

You need a second = to make this a comparison, not an assignment.

hello!
My program compiles but i get an error like
per(1711) malloc: *** error for object 0x100300670: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
Abort trap

I dont how to tackle this...
My last function of BFS looks like

Code:

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
      search1 = Delete_Queue(search, queue);
queue = Delete_Queue(search, queue);
      while(search1 != NULL)
	{
	  if ( goal == search1->nodeNum) {
	    // we found our node, act accordingly
	    printf("We found the goall\n");
	 
	  }
	  else 
	    {
	      // set visited to true for search
	      search->visited == T;
	      queue = insert_unvisited_children(queue, search);
	    }
	}
    }
   
}

Any clue why this might be happening. Thanks

thanks i did that n found that I have an error in my delete function.
when i free one of the values.
but why so, i dont understand........can some1 comment?

Code:

struct Q * Delete_Queue(struct mainList *vertex_no, struct Q *first)
{
  struct Q *previous;
  if (!first)
    return (NULL);
  vertex_no = first->info;
  previous = first;
  first = first->next;
  free(previous);  // It is here ...some issue
  return (first);
}

Ya I checked....
I wanted to know if my code line
if ( goal == search1->nodeNum)

is incorrect...coz m getting error when i try to run my program
thanks

Originally Posted by satty

Ya I checked....
I wanted to know if my code line
if ( goal == search1->nodeNum)

is incorrect...coz m getting error when i try to run my program
thanks

There is nothing grammatically or syntactically wrong with that comparison. Whether it provides the desired functionality, I can't say, but I imagine it's fine, since you are looking for the goal node.

You need to be more specific. "I'm getting an error" doesn't help us. I don't know if you are referring to the same error you mentioned in post #25 (freeing memory you never malloc'ed), or if you are talking about some other error. I don't even know if it's a compiler/linker error, runtime error (e.g. segfault), or some logic error (program runs, but gives bad output).