#1
  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. #2
  3. No Profile Picture
    Contributing User
    Devshed Loyal (3000 - 3499 posts)

    Join Date
    May 2004
    Posts
    3,417
    Rep Power
    887
    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 05:27 PM. Reason: grammar
    I no longer wish to be associated with this site.
  4. #3
  5. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,961
    Rep Power
    481
    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.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo