July 20th, 2008, 12:03 PM

C  Initializing a Sparse Matrix and Adding Nodes
Hi all, so I'm trying to create a sparse matrix...ie a matrix where only space is allocated for cells (nodes) with values. There are two parts to this program. First part of the assignment is to build a structure to store a sparse matrix A. I must take the name of the file as a command line argument. Entries of the sparse matrix are given in the file in the following format. First line of the file is an integer that is the dimension of the matrix. You may assume that the matrix is square. That is, the row and column dimensions are the same. Each of the subsequent lines contain two integers, rowindex, columnindex and value of the matirx entry(double). An example of a text file will look like this:
10
0 1 23
0 6 34
2 3 56.6
2 8 89.0
3 1 15
5 2 17.34
6 7 13.32
8 5 10.12
8 8 10
8 9 20
9 9 10.34
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 = (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;
}
}
Called by this in main:
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);
}
}
Last edited by strakerc; July 20th, 2008 at 07:54 PM.
Reason: New problem
July 20th, 2008, 09:18 PM

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);
}
July 21st, 2008, 09:51 AM

debug the code.
try with different values and see what's the pattern.
also, do you free the allocated memory?
July 21st, 2008, 10:30 AM

The code runs, etc. Therefore gdb isn't helpful...I came to the forums having done all the debugging I can and being stuck. None of the values have 15, so the printing makes no sense. I inserted print statements in add and it is adding correctly I believe. Therefore I feel as if I am not navigating through the matrix properly in print, but I don't see how that could be
July 21st, 2008, 10:43 AM

well, the print looks fine. the insert got some suspicious parts I would check
very good if it's really working by careful debug and adding lots of printf commands
inside the insert method.
July 21st, 2008, 10:49 AM

I've been able to isolate the line in print causing trouble:
ptr = ptr>colPtr;
This probably then means the insert wasn't done as properly as I had thought....