# Thread: Detecting symmetry in sparse matrix

1. ## 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. 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. 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.

4. 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

5. 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. 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

7. Wow I'm blind; I swapped where 0 and 1 should be.

8. 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

Popular pages Recent additions