I am trying to do an efficient sparse matrix multiplication. Right now I am reading the data into memory and this is how my data structure looks like:
typedef struct node{
int x;
int y;
int value;
struct node* row;
struct node* col;
}node;
typedef struct matrix{
int height;
int width;
node** rowList;
node** colList;
}matrix;
My current code for the insertion is:
void insert(matrix** M, int row_index, int col_index, int value)
{
node* currNode=(node*)malloc(sizeof(node));
currNode->x=row_index;
currNode->y=col_index;
currNode->value=value;
if ((*M)->rowList[row_index] == NULL) { /* index is empty */
currNode->row = NULL;
(*M)->rowList[row_index] = currNode;
}
else if ((*M)->rowList[row_index]->y > col_index) { /* insert node to front */
//printf("%d, %d\n", (*M)->rowList[row_index]->y, col_index);
currNode->col = (*M)->rowList[row_index];
(*M)->rowList[row_index] = currNode;
}
else if ((*M)->rowList[row_index]->y < col_index) { /* insert node to front */
node* rowptr = (node*)malloc(sizeof(node));
rowptr = (*M)->rowList[row_index];
while(rowptr->col!=NULL&&rowptr->col->y < col_index)
rowptr=rowptr->col;
currNode->col=rowptr->col;
rowptr->col=currNode;
//printf("-----------------%d\n", rowptr->y);
}
if ((*M)->colList[col_index] == NULL) {
currNode->col = NULL;
(*M)->colList[col_index] = currNode;
}
else
if ((*M)->colList[col_index]->x > row_index) {
//printf("%d, %d\n", (*M)->colList[col_index]->x, row_index);
currNode->row = (*M)->colList[col_index];
(*M)->colList[col_index] = currNode;
}
}
In case of you ask, this is my print function:
void print_matrix(matrix *M){
for(int i=0;i<M->height;i++){
while(M->rowList[i]!=NULL){
printf("i=%d, j=%d, v=%d\n",M->rowList[i]->x, M->rowList[i]->y,
M->rowList[i]->value);
M->rowList[i]=M->rowList[i]->col;
}
}
}
For this input:
5,5
0,0,1
0,1,2
0,3,3
0,4,4
where (5,5) matrix dimensions and (0,0,1) = i,j,value, I get this:
i=0, j=0, v=1
i=0, j=1, v=2
i=0, j=3, v=3
i=0, j=4, v=4
i=0, j=4, v=4
For this input:
5,5
0,0,1
0,1,2
0,3,3
0,4,4
0,2,5
I get this:
i=0, j=0, v=1
i=0, j=1, v=2
i=0, j=2, v=5
i=0, j=2, v=5
I think the problem is here:
else if ((*M)->rowList[row_index]->y < col_index) {
node* rowptr = (node*)malloc(sizeof(node));
rowptr = (*M)->rowList[row_index];
while(rowptr->col!=NULL&&rowptr->col->y < col_index)
rowptr=rowptr->col;
currNode->col=rowptr->col;
rowptr->col=currNode;
}
[ ... ]
Somehow I remove one of the values when I add a new element that is smaller.
The question is : how can I get this code to load my sparse matrix values into memory using the data structure provided correctly?
Thank you ^^
Here:
if ((*M)->colList[col_index] == NULL) {
currNode->col = NULL;
(*M)->colList[col_index] = currNode;
}
where you write currNode->col
, you should have written currNode->row
. After making this change the output is correct for the second input file.
While looking at the code I noticed other odd things; for example, the print_matrix function also destroys the matrix ->col pointer chains. Also, in these two lines
node* rowptr = (node*)malloc(sizeof(node));
rowptr = (*M)->rowList[row_index];
you're allocating memory and then immediately overwriting the pointer to it.