Thread: Detecting symmetry in sparse matrix

  1. #1
    Registered User
    Join Date
    Jul 2008
    Location
    Pittsburgh, PA
    Posts
    12

    Detecting symmetry in sparse matrix

    So I need to detect symmetry between 2 arrays of linked lists. One array represents rows in a sparse matrix (a table where empty values do not exist and thus do not waste space) and the other represents columns. I need to detect to see if the matrix is symmetrical, and I don't know how to navigate through the matrix properly to test this. If someone could please describe the proper loops and checks to make it would be great. Thanks!

  2. #2
    Registered User
    Join Date
    Jul 2008
    Posts
    58
    Its a little hard to understand what exactly you mean, but this is what I got from it:

    You have 2 arrays, one array has information inputted in a horizontal fashion, the other in a vertical fashion... like the two ascii grids below

    |1 2 3 4|
    |5 6 7 8|
    |9 10 11 12|
    |13 14 15 16|

    and

    |1 5 9 13|
    |2 6 10 14|
    |3 7 11 15|
    |4 8 12 16|

    To cross referance these grids the loops would look like this(Just one way of doing it)

    Code:
    int x=4, y=4, d, dd;
    for(d=0;d<y;d++)
    {
      for(dd=0;dd<x;dd++)
      {
        if(ColumnGrid[x][y]!=RowGrid[y][x])
          then quit because they do not match
      }
    }
    if(didn't quit cause' they didn't match)
      then the grids do match!
    the important part of that code is the if statement checking if columngrid and rowgrid are not equal, it does this by inverting the x and y pairs in the array structure, so while one grid is read left-right/up-down the other is read up-down/left-right
    Which is what I think you want... unless I'm mistaken

  3. #3
    Registered User
    Join Date
    Jul 2008
    Location
    Pittsburgh, PA
    Posts
    12
    That's close, but the data structure isn't a normal 2D array and cannot be accessed like array[][]. It is two separate arrays of linked lists...I uploaded a picture to help explain what I mean. The way to access spaces in the matrix is to create a pointer node to the head of the list (array[x]) and then make ptr = ptr->next until you have the node you want.
    Last edited by strakerc; 07-23-2008 at 09:53 AM.

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    If each row consists of a linked list with n elements [where n may be different from one row to another], would a dynamically allocated array plus a count not be a better format to hold your data - it would save about half the data-size if you are storing 32-bit values.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Jul 2008
    Location
    Pittsburgh, PA
    Posts
    12
    I'm in school, and this was the assignment; so I cannot change the data structure. Here is my code which may also help make more sense of things. I think it is close to being right, but some non-symmetric matricies come up as symmetric:
    Code:
    int isSymmetric(Matrix* array) {
    	long i = 0;
    	long j = 0;
    	for(i; i<array->dimension; i++) { 
    		Node* rowptr = array->rowList[i];
    		for(j; j<array->dimension; j++) {
    			Node* colptr = array->columnList[j];
    			while (colptr != NULL && rowptr != NULL) {
    				if (colptr->rowIndex != rowptr->columnIndex || colptr->columnIndex != rowptr->rowIndex) {
    					return 1;
    				}
    				colptr = colptr->rowPtr;
    				rowptr = rowptr->colPtr;
    			}
    		}
    	}
    	return 0;
    }

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    So, let me guess: your false positives find non-symetric cases where there is only a column or row that is longer in one matrix than the other?

    Or in other words, if rowptr == NULL but colptr != NULL or the other way around?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    Registered User
    Join Date
    Jul 2008
    Location
    Pittsburgh, PA
    Posts
    12
    Wow I'm blind; I swapped where 0 and 1 should be.

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    May I suggest also:

    Code:
    	long i = 0;
    	long j = 0;
    	for(i = 0; i<array->dimension; i++) { 
    		Node* rowptr = array->rowList[i];
    		for(j=0; j<array->dimension; j++) {
    The first one is to make it clear that i = 0, even if it's been set previously - the compiler will sort out that it only needs setting once - if that's not the case, you need a better compiler. The second one is absolutely needed - as you are not going into the loop if j is over the limit of array->dimension, which may be the case when you get to the next outer loop iteration.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C - access violation
    By uber in forum C Programming
    Replies: 2
    Last Post: 07-08-2009, 01:30 PM
  2. Sparse Matrix
    By brb9412 in forum C Programming
    Replies: 3
    Last Post: 01-02-2009, 01:12 PM
  3. Matrix Help
    By HelpmeMark in forum C++ Programming
    Replies: 27
    Last Post: 03-06-2008, 05:57 PM
  4. What is a matrix's purpose in OpenGL
    By jimboob in forum Game Programming
    Replies: 5
    Last Post: 11-14-2004, 12:19 AM