### Thread: Compressed Sparse Row implementation, got stuck

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
27
Rep Power
0

#### Compressed Sparse Row implementation, got stuck

The idea is to have 3 arrays to represent a matrix.
V has the values of the non-zero values.
C has the column of each value with the same index from V.
R has the index(in V) of the first element in each row.

Example:
0 1 0
0 2 0
0 0 3
V = 1,2,3
C = 1,1,2
R = 0,1,2,3

so I can find the element in the position (0,1) looking at R and figuring the row 0 has only the element 0 from V, then looking at C check if there is an element in the column 1.

So far, I wrote the code to read the values, and store in an array with the coordinates and the value, but I can't find out how to get the row index array from the input.

Code:
```struct coord{
int row;
int col;
int val;
};
typedef struct coord coord;

int main(){
int * R,*C,*V;
int n,i,j,nrow;
coord * temp;
scanf("%d", &n);
temp = malloc(n * sizeof(coord));
V = malloc(n * sizeof(int));
C = malloc(n * sizeof(int));
if(!temp || !V || !C){
return 0;
}

for(i=0;i<n;i++){
scanf("%d %d %d", &temp[i].row, &temp[i].col, &temp[i].val);
}

qsort (temp,n,sizeof(coord),compar); **compar sorts the values row-wise.
nrow = temp[n-1].row + 1;
R = malloc((nrow + 1)*sizeof(int));

if(!R) return 0;

for(i=0;i<n;i++){
V[i] = temp[i].val;
C[i] = temp[i].col;
}```
This is what I've got so far, but I can't figure out how to get the values for R, specially because I want to have the empty rows to have the same value of the next row for easier access later.
2. No Profile Picture
Contributing User
Devshed Loyal (3000 - 3499 posts)

Join Date
May 2004
Posts
3,417
Rep Power
890
This is what I've got so far, but I can't figure out how to get the values for R, specially because I want to have the empty rows to have the same value of the next row for easier access later.
We probably can't either. Not without guessing what the rules are. The reason you are having troubles with this is probably due to your inability to describe the problem adequately enough.

Is R supposed to contain the set of all values in the matrix?
Last edited by jwdonahue; May 10th, 2013 at 04:27 PM. Reason: grammar
3. The usual way to store a sparse rank n matrix would be

The constant value.
non-constant values (need not be zero)
Length n vector of indexes for each non-constant value.

For 2 D array with m non-constant values I expect these variables:

datatype ConstantValue;
datatype array[m];
int col[m], row[m];

Your vcr (V, C, and R) have different lengths. I can't tell if you're trying to use a secondary compression scheme.