Programming Help

Web Development



What's Here?

  • Members: 105,761
  • Replies: 404,434
  • Topics: 61,340
  • Snippets: 2,214
  • Tutorials: 597
  • Total Online: 1,752
  • Members: 74
  • Guests: 1,678

Who's Online?

Welcome to Dream.In.Code
Getting C++ Help is Easy!

Join 105,761 C++ Programmers for FREE! Ask your question and get quick answers from experts. There are 1,752 online right now! We've got more than 500 tutorials and 2,000 snippets. Join and find out why Dream.In.Code is the #1 programming help community on the internet! Registration is fast and FREE... Join Now!



Initializing a Sparse Matrix

 
 Reply to this topicStart new topic

Initializing a Sparse Matrix
strakerc
post 20 Jul, 2008 - 10:04 AM
Post #1


New D.I.C Head

*
Joined: 31 May, 2008
Posts: 23


My Contributions
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;
    }
}
User is offlineProfile CardPM

Go to the top of the page


skaoth
post 20 Jul, 2008 - 10:37 AM
Post #2


D.I.C Regular

Group Icon
Joined: 7 Nov, 2007
Posts: 316



Thanked 5 times

Dream Kudos: 100
My Contributions
I'd have to see how you are invoking this function because I don't know if Matrix** M that your passing into initializeMatrix() has already been allocated with malloc().
If it hasn't then you'll either need to allocate memory for your matrix variable before or inside of the function

CODE


// Ex 1:
// This doesn't work
Matrix *m = NULL;

long size = 10;
// This will cause a seg fault
initializeMatrix(&m, &size, NULL);


// Ex 2:
// This does not cause a seg fault
Matrix * m = (Matrix*) malloc(sizeof(Matrix));
long size = 10;
initializeMatrix(&m, &size, NULL);
User is online!Profile CardPM

Go to the top of the page

strakerc
post 20 Jul, 2008 - 11:02 AM
Post #3


New D.I.C Head

*
Joined: 31 May, 2008
Posts: 23


My Contributions
Ah, of course! I was calling initializematrix in my main class without mallocing first -- and I wasn't even looking for problems there. Thanks!

However, now after finally fixing this problem I am running into the same error at other areas of my code. I have an insertnode function, which is called by:
CODE

    FILE* in;
    long dimension, row_index, column_index;
    in = fopen(argv[1], "r");
    double value;
    Matrix* M = malloc(sizeof(Matrix));
    while (fscanf(in, "%ld  %ld  %lf", &row_index, &column_index, &value) == 3) {
         insertNode(&M, row_index, column_index, value);
    }

after being initialized of course.

My insertnode function takes into account multiple cases (empty row or column) but is still causing a bus error from invalid memory access:
CODE

void insertNode(Matrix** M, long row_index, long column_index, double value) {
    Node* ptr;
    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] != 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;
        int counter = 0;
        for (counter; (*M)->rowList[counter] != NULL; counter++) {}
        ((*M)->rowList[counter])->rowPtr = ptr;
    }
}


This post has been edited by strakerc: 20 Jul, 2008 - 11:03 AM
User is offlineProfile CardPM

Go to the top of the page

skaoth
post 20 Jul, 2008 - 11:29 AM
Post #4


D.I.C Regular

Group Icon
Joined: 7 Nov, 2007
Posts: 316



Thanked 5 times

Dream Kudos: 100
My Contributions
You are still going to need to call initializeMatrix() after you malloc your matrix variable. Your insert function is banking on the fact that rowList and columnList have been allocated properly otherwise it will fail.
Secondly, you need to malloc the node pointer you are trying to insert

CODE

void insertNode(Matrix** M, long row_index, long column_index, double value){

/// NOTE -- ptr is not allocated before trying to access it !!!!
Node* ptr;
    ptr->value = value; /* initialize all properties of node */
    ptr->rowIndex = row_index;
    ptr->columnIndex = column_index;

....
}


Lastly, I'm not sure what you are trying to do, but the logic for the insert seems wierd. First you check if
(*M)->rowList[row_index] == NULL and (*M)->rowList[row_index] == NULL. If this is true (which it will be on the first insert)
you assign it the ptr variable. This is fine.

However, then you check for (*M)->rowList[row_index] != NULL and (*M)->columnList[column_index] != NULL. Since you just assigned
rowList and columnList, these checks will also be true, and you will re-assign the value.

If this is your intent then there is nothing wrong. Though it almost seems like you want to do some thing like this
CODE

if ((*M)->rowList[row_index] == NULL) { /* index is empty */
        ptr->rowPtr = NULL;
        (*M)->rowList[row_index] = ptr;
}
else
{
        ptr->rowPtr = NULL;
        int counter = 0;
        
        // WARNING Will Robinson... WARNING
        // Don't forget that you could over run your buffer her if your not careful
        // Your initialize function determined how many elements there were in there.
        // So don't go over that size.
        for (counter; (*M)->columnList[counter] != NULL; counter++) {}
        ((*M)->columnList[counter])->colPtr = ptr;
}
User is online!Profile CardPM

Go to the top of the page

strakerc
post 20 Jul, 2008 - 11:50 AM
Post #5


New D.I.C Head

*
Joined: 31 May, 2008
Posts: 23


My Contributions
Well yes, I call initializematrix before insertnode. And as for the logic with the 4 if statements I understand how the overwrite that would cause which I am NOT trying to do and have fixed that. Lastly, I malloced ptr, but I did not think I needed too; I am still getting the same error in insertnode...

Here is my reformed code, that is still getting a bus error, I think with the for loops in insert node:
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);
    }
    long beginrow = 2, endrow=5, begincol=1, endcol=3;
    printSubMatrix(M, beginrow, endrow, begincol, endcol);
    return EXIT_SUCCESS;
}

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;
    }
}

skaoth, thank you for all of your help so far; these bus errors have been giving me problems for days.

This post has been edited by strakerc: 20 Jul, 2008 - 03:16 PM
User is offlineProfile CardPM

Go to the top of the page

skaoth
post 20 Jul, 2008 - 04:05 PM
Post #6


D.I.C Regular

Group Icon
Joined: 7 Nov, 2007
Posts: 316



Thanked 5 times

Dream Kudos: 100
My Contributions
Before I continue helping you can you describe what it is your trying to do? There is something odd about the logic of the insertNode() function. I'm not following how your trying to insert nodes into the matrix.
User is online!Profile CardPM

Go to the top of the page

strakerc
post 20 Jul, 2008 - 04:20 PM
Post #7


New D.I.C Head

*
Joined: 31 May, 2008
Posts: 23


My Contributions
QUOTE(skaoth @ 20 Jul, 2008 - 04:05 PM) *

Before I continue helping you can you describe what it is your trying to do? There is something odd about the logic of the insertNode() function. I'm not following how your trying to insert nodes into the matrix.

No problem:
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

It is hard to describe in writing, so I have a attached a picture.

This post has been edited by strakerc: 20 Jul, 2008 - 04:28 PM


Attached thumbnail(s)
Attached Image

Attached File(s)
Attached File  SkillLab4.zip ( 5.77k ) Number of downloads: 2
User is offlineProfile CardPM

Go to the top of the page

strakerc
post 20 Jul, 2008 - 07:19 PM
Post #8


New D.I.C Head

*
Joined: 31 May, 2008
Posts: 23


My Contributions
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);
}
User is offlineProfile CardPM

Go to the top of the page

Reply to this topicStart new topic
Time is now: 8/21/08 01:26PM
Invision Power Board v2.1.7 © 2008  IPS, Inc.
Licensed to: MediaGroup1

Live C++ Help!

C++ Tutorials

Reference Sheets

C++ Snippets

Bye Bye Ads

Free DIC T-Shirt

T-Shirt Example

Related Sites

Monthly Drawing

Thumb Drive

Partners

Top Contributors

Top 10 Kudos This Month