Programming Help
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
 
 
User Name:
Password:
Remember me
Go Back   ASP Free ForumsOtherProgramming Help

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Rate Thread Display Modes
 
Unread ASP Free Forums Sponsor:
  #1  
Old July 20th, 2008, 12:03 PM
strakerc strakerc is offline
Registered User
ASP Free Newbie (0 - 499 posts)
 
Join Date: Jun 2008
Location: Pittsburgh, PA
Posts: 7 strakerc User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 3 h 16 m 3 sec
Reputation Power: 0
Send a message via AIM to strakerc
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

Reply With Quote
  #2  
Old July 20th, 2008, 09:18 PM
strakerc strakerc is offline
Registered User
ASP Free Newbie (0 - 499 posts)
 
Join Date: Jun 2008
Location: Pittsburgh, PA
Posts: 7 strakerc User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 3 h 16 m 3 sec
Reputation Power: 0
Send a message via AIM to strakerc
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);
}

Reply With Quote
  #3  
Old July 21st, 2008, 09:51 AM
Shadow Wizard's Avatar
Shadow Wizard Shadow Wizard is offline
Moderator From Beyond
ASP Free God 45th Plane (27000 - 27499 posts)
 
Join Date: Sep 2004
Location: Israel
Posts: 27,250 Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)  Folding Points: 354839 Folding Title: Super Ultimate Folder - Level 1Folding Points: 354839 Folding Title: Super Ultimate Folder - Level 1Folding Points: 354839 Folding Title: Super Ultimate Folder - Level 1Folding Points: 354839 Folding Title: Super Ultimate Folder - Level 1Folding Points: 354839 Folding Title: Super Ultimate Folder - Level 1Folding Points: 354839 Folding Title: Super Ultimate Folder - Level 1
Time spent in forums: 3 Months 1 Week 6 Days 10 h 43 m 15 sec
Reputation Power: 1778
debug the code.
try with different values and see what's the pattern.
also, do you free the allocated memory?

Reply With Quote
  #4  
Old July 21st, 2008, 10:30 AM
strakerc strakerc is offline
Registered User
ASP Free Newbie (0 - 499 posts)
 
Join Date: Jun 2008
Location: Pittsburgh, PA
Posts: 7 strakerc User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 3 h 16 m 3 sec
Reputation Power: 0
Send a message via AIM to strakerc
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

Reply With Quote
  #5  
Old July 21st, 2008, 10:43 AM
Shadow Wizard's Avatar
Shadow Wizard Shadow Wizard is offline
Moderator From Beyond
ASP Free God 45th Plane (27000 - 27499 posts)
 
Join Date: Sep 2004
Location: Israel
Posts: 27,250 Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)Shadow Wizard User rank is General 12nd Grade (Above 100000 Reputation Level)  Folding Points: 354839 Folding Title: Super Ultimate Folder - Level 1Folding Points: 354839 Folding Title: Super Ultimate Folder - Level 1Folding Points: 354839 Folding Title: Super Ultimate Folder - Level 1Folding Points: 354839 Folding Title: Super Ultimate Folder - Level 1Folding Points: 354839 Folding Title: Super Ultimate Folder - Level 1Folding Points: 354839 Folding Title: Super Ultimate Folder - Level 1
Time spent in forums: 3 Months 1 Week 6 Days 10 h 43 m 15 sec
Reputation Power: 1778
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.

Reply With Quote
  #6  
Old July 21st, 2008, 10:49 AM
strakerc strakerc is offline
Registered User
ASP Free Newbie (0 - 499 posts)
 
Join Date: Jun 2008
Location: Pittsburgh, PA
Posts: 7 strakerc User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 3 h 16 m 3 sec
Reputation Power: 0
Send a message via AIM to strakerc
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....

Reply With Quote
Reply

Viewing: ASP Free ForumsOtherProgramming Help > C - Initializing a Sparse Matrix


Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump


Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 





© 2003-2008 by Developer Shed. All rights reserved. DS Cluster 2 hosted by Hostway
Stay green...Green IT