#1
  1. No Profile Picture
    Registered User
    ASP Explorer (0 - 99 posts)

    Join Date
    Jun 2008
    Location
    Pittsburgh, PA
    Posts
    7
    Rep Power
    0

    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, row-index, column-index 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
  2. #2
  3. No Profile Picture
    Registered User
    ASP Explorer (0 - 99 posts)

    Join Date
    Jun 2008
    Location
    Pittsburgh, PA
    Posts
    7
    Rep Power
    0
    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);
    }
  4. #3
  5. Moderator From Beyond
    ASP Mastermind (5000+ posts)

    Join Date
    Sep 2004
    Location
    Israel
    Posts
    31,135
    Rep Power
    2924
    debug the code.
    try with different values and see what's the pattern.
    also, do you free the allocated memory?
  6. #4
  7. No Profile Picture
    Registered User
    ASP Explorer (0 - 99 posts)

    Join Date
    Jun 2008
    Location
    Pittsburgh, PA
    Posts
    7
    Rep Power
    0
    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
  8. #5
  9. Moderator From Beyond
    ASP Mastermind (5000+ posts)

    Join Date
    Sep 2004
    Location
    Israel
    Posts
    31,135
    Rep Power
    2924
    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.
  10. #6
  11. No Profile Picture
    Registered User
    ASP Explorer (0 - 99 posts)

    Join Date
    Jun 2008
    Location
    Pittsburgh, PA
    Posts
    7
    Rep Power
    0
    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....

Similar Threads

  1. Use visual studion or web matrix
    By Narasim.kulkarn in forum .NET Development
    Replies: 2
    Last Post: January 2nd, 2007, 04:27 PM
  2. Web Matrix with Dreamweaver 8 pages
    By wizuk in forum .NET Development
    Replies: 3
    Last Post: October 28th, 2006, 06:08 AM
  3. Web Matrix SQL Connection Error
    By ragepro7 in forum .NET Development
    Replies: 1
    Last Post: September 20th, 2004, 04:32 PM
  4. Replies: 15
    Last Post: August 28th, 2004, 09:11 AM
  5. Sql Server Rerporting Services
    By ameet_vasu in forum Microsoft SQL Server
    Replies: 0
    Last Post: June 3rd, 2004, 07:08 AM

IMN logo majestic logo threadwatch logo seochat tools logo