Thread: adjacency list

I am a small issue here...
I have my file as
//Mock Data
parse_line("456 222 0.981");
parse_line("789 999 0.982");
parse_line("123 111 0.983");
parse_line("456 333 0.984");
and I am reading it into a adjacency List.
the tings I am able to parse the first and the second column but not the third one.
it gives me result as

123 -> 111
456 -> 222 333
789 -> 999
when i want something like


123 -> 111 0.984
456 -> 222 0.981 333 0.984
789 -> 999 0.982

the functions i wrote are::

Code:

// Process the first column (Add it to main list)
struct mainList* process_first_col( int value )
{
#if MY_DEBUG
  printf(" hey first value: %i\n", value);
#endif
  
  // Search and add to the main list
  return SortedInsertInMainList(value);
}

// Process the second column
// Add these to adjacency list of the current *node* pointer
void process_second_col( struct mainList* node, int value )
{
  struct adjList *cur, *prev;
  struct adjList **ptr = &node->pAdjListHead;
  
  if((*ptr) == NULL)
    {
      (*ptr) = (struct adjList *)malloc(sizeof(struct adjList));
      (*ptr)->nodeNum = value;
      (*ptr)->pNext = NULL;
      return;
    }
  
  cur = *ptr;
  while(cur != NULL)
    {
      prev = cur;
      cur = cur->pNext;
    }
  
  prev->pNext = (struct adjList *)malloc(sizeof(struct adjList));
  prev->pNext->nodeNum = value;
  prev->pNext->pNext = NULL;
  
#if MY_DEBUG
  printf("second value: %i\n", value);
#endif
}

void process_third_col( struct adjList *node, float value1 )
{
  struct adjList *cur, *prev;
  struct adjList **ptr = &node;
  
  if((*ptr) == NULL)
    {
      (*ptr) = (struct adjList *)malloc(sizeof(struct adjList));
      (*ptr)->prob = value1;
      
      (*ptr)->pNext = NULL;
      return;
    }
  
  cur = *ptr;
  while(cur != NULL)
    {
      prev = cur;
      cur = cur->pNext;
    }
  
  prev->pNext = (struct adjList *)malloc(sizeof(struct adjList));
  prev->pNext->prob = value1;
  
  prev->pNext->pNext = NULL;
  
#if MY_DEBUG
  printf("third value: %f\n", value1);
#endif
}

what am i doing wrong here?

thanks

I don't see enough of an algorithm to do adjacency, whatever that means.
I think you need to show us your parse_line() function.

iMalc, you're not helpful. Casting or not casting return value of malloc is only problematic if one omits the appropriate prototype. Casting the return value shuts up a persnickety compiler such as Microsoft's C++ when the source code is in a .cpp file. Nothing wrong with that. Either way it has no effect on the OP's problem.

hey there is the parse function

Code:

void parse_line(char* line)
{
	int j = 0;
	int count = 0;
	int mainnode = 0;
	char value[5]; //Assume the number of the node < 9999
	struct mailList *node = NULL;

	while(*line != '\0')
	{
		// Differentiating only with TAB character only
		if(*line != 9) //9 is for tab
		{
			value[j] = *line;
			j++;
		}
		else
		{
			value[j] = '\0';
			if(count == 0)
			{
				mainnode = atoi((const char*)value);
				node = process_first_col( mainnode );
				count++;
				j = 0;
				line++;
				continue;
			}
			if(count == 1)
			{
				process_second_col( node, atoi((const char*)value) );
				count++;
				j = 0;
				line++;
			continue;
			}
			if(count == 2)
			{
				process_third_col(node, atof((const char*)value) );
				count++;
				j = 0;
				line++;
				break;
			}
		}
		line++;
	}
}

I this I am doing something wrong while parsing the third column

Can't you simply use sscanf() ???

i don't think that makes much different because I have latter written parsing codes for all three columns. First column act as main list and other two ad as the adjacency list.

but something went wrong.

So the reason your parse function doesn't work right is because it always expects a tab character after a number to signal the end of that number. But your last number is followed by a null character, causing your loop to terminate before it can get into the "if (count == 2)" section. By the way, using the magic number 9 is icky, use '\t' instead.

Or, better yet, as Bayint Naung suggested, use sscanf.

You are basically reinventing the wheel, which means that you're rewriting code that's already proven to work well. Your parse_line function is overly complicated and lacks some necessary error checking. If you use sscanf, it might look like this:

Code:

int parse_line2(char *line)
{
    int     val1, val2;
    float   val3;

    if (sscanf(line, "%d\t%d\t%f", &val1, &val2, &val3) != 3) {
        // we didn't convert all 3 pieces of data, print an error and return -1 to tell the caller we had a problem
        printf("Error parsing line '%s'\n", line);
        return -1;
    }

    // process all 3 columns and return 0 for success

    return 0;
}

thanks all.
let me try that.

hey !
I figured out it wont work for me become I have different functions that make adjacency list.
But
when i parse the lines...
it goes till the end of the line while(*line != '\0')

and then (count ==2 ) should work .
or there is something wrong again.

Actually, it should work for you if you put your calls to process_first_col, process_second_col and process_third_col where I had the comment "process all 3 columns and return 0 for success". Those functions will be called in the same order as in your own parse function, and, since there is nothing else going on in your parse function, you should be fine. It will be much cleaner, less error prone and you will have less code to write and maintain (and I think you're realizing that writing even a simple parsing function is a pain).

If, however, you still insist on using your own function, here is why it is broken:
Your code only processes the number it just extracted when it finds a tab character. This happens when you hit the else block of if (*line != 9). But your input lines are (presumably) something like this: "123\t456\t.987". Notice there is no tab character after the .987. There is only the null that tells you it's the end of the string. You successfully put the .987 into value, but you never get a tab character to let yourself into the chunk of code that calls process_third_col. Your while loop instead finds that *line is null and exits the loop.

If you don't feel like figuring that out and refuse to use sscanf, you could at least look into using strtok. It should split up the line for you just like you're doing it, but without the problem you're having of skipping the last token (number).

As a side note, both your function and strtok will modify the original string you passed in to parse_line. This may be undesirable if you need it later for anything. This is another reason why I strongly suggest using sscanf.

hey thanks, I used sscanf...it was easy n convinent.

I could make the adajceny list...
but got another error in my print function i guess.
I gives me two values now like

123 -> 111 0.000000 0 0.983000
456 -> 222 0.000000 0 0.981000 333 0.000000 0 0.984000
789 -> 999 0.000000 0 0.982000
when i should be

123 -> 111 0.983000
456 -> 222 0.981000 333 0.984000
789 -> 999 0.982000

i have no clue why it is printing column 2 and column 3 values twice and that too with Zeros .

My function is

Code:

void printMainList()
{
	struct mainList *ptr = *pHead;    // main list
	struct adjList *ptr2 = NULL;        // adjacency list
	printf("List: \n");
	
	while(ptr != NULL)
	  {
	    printf("%d -> ", ptr->nodeNum);
	    ptr2 = ptr->pAdjListHead;    // pAdjListHead is a pointer to the adjacency list in mainlist 
	    while(ptr2 != NULL)
	      {
		printf(" %d %f\t", ptr2->nodeNum, ptr2->prob );
		
		ptr2 = ptr2->pNext;
		
	      }
	    printf("\n");
	    ptr = ptr->pNext;
	  }
	printf("\n");
}

So the short answer is: You have two nodes in your adjacency list for each one node you're trying to track. I think it has to do with you creating (via malloc) separate nodes in process_second_col and process_third_col. That's why the first of your two has a nodeNum and no prob, and the second has a prob, but no nodeNum. Combine your process_second_col and process_third_col functions, and just pass it both nodeNum and prob.

Thanks a ton.
i got it and it worked perfectly nice.
This forum is awesome

only the last issue.

I have trying to print the adjacent nodes on a user input node value.

Code:

void SearchAndPrintList(int value)
{
  struct mainList *ptr = *pHead;
  struct adjList *ptr2 = NULL;
  
  // HERE IT IS LINEAR SEARCH. WE CAN HAVE BINARY SEARCH HERE.
  // IT WILL BE VERY FAST!
  while(ptr != NULL)
    {
      if(value == ptr->nodeNum)
	{
	  printf("ADJ List for: %d -> ", ptr->nodeNum);
	  ptr2 = ptr->pAdjListHead;
	  while(ptr2 != NULL)
	    {
	      printf("%d ", ptr2->nodeNum);
	      ptr2 = ptr2->pNext;
	    }
	  printf("\n");
	  return;
	}
      ptr = ptr->pNext;
    }
  printf("NODE NOT FOUND!\n");
}

And it gives the correct output.
Telling what nodes are adjacent to the asked node.
But I want to do something like Breadth First search here.
Eg if I have

Graph like

1 -> 2, 4
2 -> 1, 3
3-> 2, 4
4 -> 1,3,5
5->4

I want to if 1 and 5 are connect.
I able to retrieve the nodes for Node1 but I want to search for the adjacent nodes.
Then I should repeat the same for the adjacent nodes till , I find the desired node.

So i search for Node1, i get
1 -> 2, 4
then I want to search for 3 and 4


I think I need 1 more while loop there i tried some ways but no luck...
Please help, m stuck on the last part now.

i did something like this but it keeps on adding the node till segmentation fault.

Code:

void SearchAndPrintList(int value, int value2)
{
  struct mainList *ptr = *pHead;
  struct adjList *ptr2 = NULL;
  while(ptr != NULL)
     {
      if(value == ptr->nodeNum)
	{
	  printf("ADJ List for: %d -> ", ptr->nodeNum);
	  ptr2 = ptr->pAdjListHead;
	  while(ptr2 != NULL || ptr2 != value2)
	    {
	      ptr2->pNext = (struct adjList *)malloc(sizeof(struct adjList));
	      printf("%d ", ptr2->nodeNum);
	      SearchAndPrintList(ptr2->nodeNum, ptr2->pNext->nodeNum); 
	      
	    }
	  ptr2 = ptr2->pNext;
	  
	  printf("\n");
	  return ;
	}
      ptr = ptr->pNext;
     } 
  printf("NODE NOT FOUND!\n");
}