Thread: Initializing a Sparse Matrix

Hi all, so I'm trying to initialize 2 arrays of nodes as defined like:

Code:

struct Node
{  
    long rowIndex;
    long columnIndex;
    double value;
    struct Node* rowPtr;
    struct Node* colPtr;
};
typedef struct Node Node;

struct Matrix
{
    long dimension;
    Node** rowList;
    Node** columnList;
};

and I keep running into bus errors. This is what I have, and I cannot think of where my logic is wrong (gdb says I have invalid memory access):

Code:

void initializeMatrix(Matrix** M, long* dimension, FILE* in) {
        (*M)->rowList = malloc(*dimension*sizeof(Node));
	(*M)->columnList = malloc(*dimension*sizeof(Node));
	int i;
	for (i=0; i<*dimension; i++) {
		(*M)->rowList[i] = NULL;
		(*M)->columnList[i] = NULL;
	}
}

Maybe here:

Code:

(*M)->rowList = malloc(*dimension*sizeof(Node));
(*M)->columnList = malloc(*dimension*sizeof(Node));

rowList and columnList are a pointer to pointer to Node. Shouldn't you have:

Code:

......sizeof(*Node)

instead?

Do you mean node*? Yea I think you're right. Additionally I think I needed to malloc for the Matrix. I am getting the same bus error for invalid memory access all over the place...

Here is my main that calls 2 functions, initialize and insert:

Code:

int main(int argc, char* argv[])
{
    FILE* in;
	long dimension, row_index, column_index;
	in = fopen(argv[1], "r");
	fscanf(in, "%ld", &dimension);
    double value;
    Matrix* M = malloc(sizeof(Matrix));
  
    initializeMatrix(&M, &dimension,in);

    while (fscanf(in, "%ld  %ld  %lf", &row_index, &column_index, &value) == 3)
    {
		insertNode(&M, row_index, column_index, value);
    }

And the reformed initialize and insert functions are:

Code:

void initializeMatrix(Matrix** M, long* dimension, FILE* in) {
	(*M)->rowList = malloc(*dimension*sizeof(Node*));
	(*M)->columnList = malloc(*dimension*sizeof(Node*));
	int i;
	for (i=0; i<*dimension; i++) {
		(*M)->rowList[i] = NULL;
		(*M)->columnList[i] = NULL;
	} 
}
void insertNode(Matrix** M, long row_index, long column_index, double value) {
	Node* ptr; /*= malloc(sizeof(Node)); */
	ptr->value = value; /* initialize all properties of node */
	ptr->rowIndex = row_index;
	ptr->columnIndex = column_index;
	if ((*M)->rowList[row_index] == NULL) { /* index is empty */
		ptr->rowPtr = NULL;
		(*M)->rowList[row_index] = ptr;
	}
	else { /* ((*M)->rowList[row_index] != NULL) { index is not empty */
		ptr->rowPtr = NULL;
		int counter = 0;
		for (counter; (*M)->columnList[counter] != NULL; counter++) {}
		((*M)->columnList[counter])->colPtr = ptr;
	}
	if ((*M)->columnList[column_index] == NULL) { 
		ptr->colPtr = NULL;
		(*M)->columnList[column_index] = ptr;
	}
	else { /* ((*M)->columnList[column_index] != NULL) { */
		ptr->colPtr = NULL;
		int counter = 0;
		for (counter; (*M)->rowList[counter] != NULL; counter++) {}
		((*M)->rowList[counter])->rowPtr = ptr;
	}
}

I am now getting the bus error in insertnode...do you know why? Thanks for your help!

I have completely rewritten my insert function, which has removed all bus errors. I now however cannot tell if either my print function is wrong, or the insert function isnt completely right as printing prints 15.000000 twice and that's it....

Code:

#include "matrix.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void initializeMatrix(Matrix** M, long* dimension, FILE* in) {
	(*M)->rowList = (Node**)malloc(*dimension*sizeof(Node*));
	(*M)->columnList = (Node**)malloc(*dimension*sizeof(Node*));
	int i;
	for (i=0; i<*dimension; i++) {
		(*M)->rowList[i] = NULL;
		(*M)->columnList[i] = NULL;
	} 
}
void insertNode(Matrix** M, long row_index, long column_index, double value) {
	Node* ptr = (Node*)malloc(sizeof(Node)); 
	ptr->value = value; /* initialize all properties of node */
	ptr->rowIndex = row_index;
	ptr->columnIndex = column_index;
	if ((*M)->rowList[row_index] == NULL) { /* index is empty */
		ptr->rowPtr = NULL;
		(*M)->rowList[row_index] = ptr;
	}
	if ((*M)->columnList[column_index] == NULL) { 
		ptr->colPtr = NULL;
		(*M)->columnList[column_index] = ptr;
	}
	if ((*M)->rowList[row_index]->columnIndex > column_index) { /* insert node to front */
		ptr->colPtr = (*M)->rowList[row_index];
		(*M)->rowList[row_index] = ptr;
	}
	if ((*M)->columnList[column_index]->rowIndex > row_index) { 
		ptr->rowPtr = (*M)->rowList[row_index];
		(*M)->columnList[column_index] = ptr;
	}
	if ((*M)->rowList[row_index]->columnIndex < column_index) { /* insert node in order */
		Node* rowptr = (Node*)malloc(sizeof(Node));
		rowptr = (*M)->rowList[row_index];
		while (rowptr->colPtr != NULL && rowptr->columnIndex < column_index) {
			rowptr = rowptr->colPtr;
		}
		if (rowptr->colPtr == NULL) {
			rowptr->colPtr = ptr;
			free(rowptr);
		}
		else { /* node already exists */
			printf("Node already exists!");
			free(ptr);
			free(rowptr);
		}
	}
	if ((*M)->columnList[column_index]->rowIndex < row_index) {
		Node * colptr = (Node*)malloc(sizeof(Node));
		colptr = (*M)->columnList[column_index];
		while (colptr->rowPtr != NULL && colptr->rowIndex < row_index) {
			colptr = colptr->rowPtr;
		}
		if (colptr->rowPtr == NULL) {
			colptr->rowPtr = ptr;
			free(colptr);
		}
		else { /* Node already exists! */
			printf("Node already exists!");
			free(ptr);
			free(colptr);
		}
	}
}
void printSubMatrix(Matrix* M, long beginrow, long endrow, long begincol, long endcol) {
	long i = beginrow;
	Node* ptr = (Node*)malloc(sizeof(Node));
	ptr->columnIndex = begincol;
	for (i; i<endrow; i++) {
		printf("\n");
		if (M->rowList[i] != NULL) {
			ptr = M->rowList[i];
			while (ptr->columnIndex <= endcol) {
				printf("%lf ", ptr->value);
				ptr = ptr->colPtr;
			}
		}
	}
	free(ptr);
}