10 Replies - 8865 Views - Last Post: 15 May 2011 - 06:24 AM Rate Topic: ***** 1 Votes

#1 passer_by  Icon User is offline

  • D.I.C Head

Reputation: 5
  • View blog
  • Posts: 234
  • Joined: 06-March 11

Sparse matrix using linked lists & template

Posted 13 May 2011 - 08:25 PM

Hi guys,

I need to write a program that can store values in a Sparse matrix .
Of course ,using an array is not a good idea since we allocate to much unneeded memory.

My task involves implementing a sparse matrix using linked list and Templates.
My line of thinking is as follows : each node would hold
T* value;   // for the template (could be double/int .....) 
Node* col;  // inner class
Node* row;  // inner class Node
Node* next; // not sure about this one 



What do you think about it ? I think it would be a problem when I'd want to print the entire
matrix ,wouldn't it ?

Thanks,Ron

Is This A Good Question/Topic? 0
  • +

Replies To: Sparse matrix using linked lists & template

#2 Salem_c  Icon User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 1629
  • View blog
  • Posts: 3,092
  • Joined: 30-May 10

Re: Sparse matrix using linked lists & template

Posted 13 May 2011 - 11:07 PM

> Node* next; // not sure about this one
I think you need to spend more time thinking about this line, before doing anything else.

Do you want a single list of { row, column, value, next } or a list of rows { row, columns, next } pointing to a list of columns { column, value, next }

First, you should find out how 'sparse' the values are.
- Are they truly random, or is there a bias towards say a horizontal, vertical or diagonal distribution?
- Also, how many values are there? More than 1 value in each row/col?
The more you know about the problem, the better your design decisions are going to be.

But regardless of whichever internal data structure you choose, the external interface will remain constant.
Eg
m.read( row, col ) reads row,col element of the matrix, or returns zero.
m.write( row, col, value ) writes a value (replace existing value, or allocate a new node).
m.erase( row, col ) erases a value, freeing a node; further read() calls will now return zero.
Plus a few other methods to get/set say the matrix size.

You could also provide a print method if you wanted, though in reality, it's just a couple of loops calling read().
Was This Post Helpful? 3
  • +
  • -

#3 passer_by  Icon User is offline

  • D.I.C Head

Reputation: 5
  • View blog
  • Posts: 234
  • Joined: 06-March 11

Re: Sparse matrix using linked lists & template

Posted 14 May 2011 - 11:13 AM

View PostSalem_c, on 13 May 2011 - 11:07 PM, said:

> Node* next; // not sure about this one
I think you need to spend more time thinking about this line, before doing anything else.

Do you want a single list of { row, column, value, next } or a list of rows { row, columns, next } pointing to a list of columns { column, value, next }

First, you should find out how 'sparse' the values are.
- Are they truly random, or is there a bias towards say a horizontal, vertical or diagonal distribution?
- Also, how many values are there? More than 1 value in each row/col?
The more you know about the problem, the better your design decisions are going to be.

But regardless of whichever internal data structure you choose, the external interface will remain constant.
Eg
m.read( row, col ) reads row,col element of the matrix, or returns zero.
m.write( row, col, value ) writes a value (replace existing value, or allocate a new node).
m.erase( row, col ) erases a value, freeing a node; further read() calls will now return zero.
Plus a few other methods to get/set say the matrix size.

You could also provide a print method if you wanted, though in reality, it's just a couple of loops calling read().


Hi,thanks for the response.
I need to write a program that would support the following types :
int ,char, bool ,double . 

The main goal of the task is to ADD (+) two matrices and compare == two matrices .
At the moment I think about doing a LinkedList Class with an inner class - Node ,like this :


template <class T>
class LinkedList {

private:

	class Node
	{
	public:
		int row;			
		int col;			
		T value;	 		
		Node *next;   	
		Node *prev;   	
...
...
}


However,I'm not sure how to implement the next/prev nodes.I will have to use a design that would
be comfortable for the + operation and == operation . After some thinking , I don't know if
next/prev would be a wise decision .Am I wrong ?

thanks ,Ron

This post has been edited by passer_by: 14 May 2011 - 11:19 AM

Was This Post Helpful? 0
  • +
  • -

#4 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Sparse matrix using linked lists & template

Posted 14 May 2011 - 11:52 AM

If you're going to have a list of nodes, each node needs at least a Node* next -- otherwise how will it be a list?

You might consider implementing the matrix as a sorted list by writing the insert function to insert each node at the appropriate position based on its row/column.

Or you might consider something other than a simple list of nodes, for example an array of lists: an array for every row, in which each array element consists of (or points to) a list of nodes representing the occupied elements in that row.

The details of the structure of the matrix can make it easier to implement the matrix operations, so you should keep both aspects in mind as you design your implementation.
Was This Post Helpful? 1
  • +
  • -

#5 Salem_c  Icon User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 1629
  • View blog
  • Posts: 3,092
  • Joined: 30-May 10

Re: Sparse matrix using linked lists & template

Posted 14 May 2011 - 12:47 PM

http://en.wikipedia....iki/Linked_list
Get a pencil and paper, and draw some boxes and arrows to represent the nodes and links.

You can have as many links as you like, if you can manage the complexity of the code which results.

Starting with a simple single linked list of { row, column, value, next } might not be the most efficient, unless your matrix is really sparse, but it will be the easiest to implement to the point of having something which works.

If you have good class methods which completely hide the implementation detail, you can then tinker with the internal data structure (say lists of lists) whilst keeping the interface constant (and the users of your class oblivious to the internal detail).
Was This Post Helpful? 1
  • +
  • -

#6 passer_by  Icon User is offline

  • D.I.C Head

Reputation: 5
  • View blog
  • Posts: 234
  • Joined: 06-March 11

Re: Sparse matrix using linked lists & template

Posted 14 May 2011 - 05:45 PM

View PostSalem_c, on 14 May 2011 - 12:47 PM, said:

http://en.wikipedia....iki/Linked_list
Get a pencil and paper, and draw some boxes and arrows to represent the nodes and links.

You can have as many links as you like, if you can manage the complexity of the code which results.

Starting with a simple single linked list of { row, column, value, next } might not be the most efficient, unless your matrix is really sparse, but it will be the easiest to implement to the point of having something which works.

If you have good class methods which completely hide the implementation detail, you can then tinker with the internal data structure (say lists of lists) whilst keeping the interface constant (and the users of your class oblivious to the internal detail).


Okay , after some thinking , how about this one :
each node would hold *rightNode,*downNode (in addition to the other three fields of
value / row number / column number) ,i.e , a list of rows . The upper left node is the head ,and
the *downNode represents the start of another new row . Again,not sure (:
10x man
Was This Post Helpful? 0
  • +
  • -

#7 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Sparse matrix using linked lists & template

Posted 14 May 2011 - 07:21 PM

It's not hard to think of a scenario that would present a problem for that approach. Suppose you have a 3x2 matrix with entries in (0,1), (1,0) and (2,1). Which is the "upper left node" that will be head? And how will (1,0) be linked in?

Probably the easiest list to implement would be a sorted linked list in which the nodes are ordered first by row and then by column within each row, but that might not be so inefficient when it comes to performing arithmetic operations on the matrix. A list-of-lists (or array-of-lists) approach isn't quite as economical in terms of space, but maybe preferable in terms of facilitating arithmetic.

Did you read the Wikipedia article?
Was This Post Helpful? 1
  • +
  • -

#8 passer_by  Icon User is offline

  • D.I.C Head

Reputation: 5
  • View blog
  • Posts: 234
  • Joined: 06-March 11

Re: Sparse matrix using linked lists & template

Posted 14 May 2011 - 09:35 PM

View Postr.stiltskin, on 14 May 2011 - 07:21 PM, said:

It's not hard to think of a scenario that would present a problem for that approach. Suppose you have a 3x2 matrix with entries in (0,1), (1,0) and (2,1). Which is the "upper left node" that will be head? And how will (1,0) be linked in?

Probably the easiest list to implement would be a sorted linked list in which the nodes are ordered first by row and then by column within each row, but that might not be so inefficient when it comes to performing arithmetic operations on the matrix. A list-of-lists (or array-of-lists) approach isn't quite as economical in terms of space, but maybe preferable in terms of facilitating arithmetic.

Did you read the Wikipedia article?

I've read the article,however,the problem in solving the problem using arrays is that
I don't know how many cells I'd have.The input is like this :
value value2 value3 value4 value5 .......

"value" might be an actual value or a "-" , where "-" signifies a blank entry .
if I have the following :
1 - - - 2 - - 3

it means:
(0,0) = 1 ,(0,1)=0 ,(0,2)=0 ,(0,3)=0, (0,4)=2, (0,5)=0 ,(0,6)=0 ,(0,7)=3


and I'm only allowed to use the <string> <sstream> <iostream> headers .
So I cannot allocate in advance a large array .

This post has been edited by passer_by: 14 May 2011 - 09:38 PM

Was This Post Helpful? 0
  • +
  • -

#9 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Sparse matrix using linked lists & template

Posted 14 May 2011 - 10:17 PM

Fine. That's where list is useful. Your example describes only a single row. That row can be represented by a simple singly-linked list consisting of 3 nodes, with a node consisting of row, col, value and next.

Will the input tell you how many rows? If so, you can allocate an array of Node* where each Node* points to the beginning of a row's list. If not, you can make a list of Row objects, each Row consisting of a Node* (for the list of Nodes in that row) and a Row* pointer to the next Row. You can create a Row for every row in the matrix, or for only the occupied rows -- whichever you prefer.

I suppose that if you instantiate only the occupied rows, the Row object should also identify the row number (although you can also just use the first Node in the Row to find out the row number).
Was This Post Helpful? 1
  • +
  • -

#10 passer_by  Icon User is offline

  • D.I.C Head

Reputation: 5
  • View blog
  • Posts: 234
  • Joined: 06-March 11

Re: Sparse matrix using linked lists & template

Posted 14 May 2011 - 10:51 PM

View Postr.stiltskin, on 14 May 2011 - 10:17 PM, said:

Fine. That's where list is useful. Your example describes only a single row. That row can be represented by a simple singly-linked list consisting of 3 nodes, with a node consisting of row, col, value and next.

Will the input tell you how many rows? If so, you can allocate an array of Node* where each Node* points to the beginning of a row's list. If not, you can make a list of Row objects, each Row consisting of a Node* (for the list of Nodes in that row) and a Row* pointer to the next Row. You can create a Row for every row in the matrix, or for only the occupied rows -- whichever you prefer.

I suppose that if you instantiate only the occupied rows, the Row object should also identify the row number (although you can also just use the first Node in the Row to find out the row number).

A complete input would look like this:
1 - - 
- 2 - 

which means :
1 0 0 
0 2 0 

So,after each "\n" (i.e : the user has pressed ENTER) I would have another line .
From the first line I will be able know how many columns I will have , however not how many rows.
I would know how many rows would be ,after the user has pressed ENTER on a blank line:

1 - - 
- 2 - 
// nothing is written here , now I'm the user and I pressed ENTER

and now I know that he has 3 columns and 2 rows .

If I choose the other option you said ,meaning "list of Row objects" , do you think it would be easier to
manipulate calculations (+ operator) and equal (== operator) between two matrices ?

thanks a lot for the help ,BTW

This post has been edited by passer_by: 14 May 2011 - 10:52 PM

Was This Post Helpful? 0
  • +
  • -

#11 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Sparse matrix using linked lists & template

Posted 15 May 2011 - 06:24 AM

View Postpasser_by, on 15 May 2011 - 12:51 AM, said:

If I choose the other option you said ,meaning "list of Row objects" , do you think it would be easier to
manipulate calculations (+ operator) and equal (== operator) between two matrices ?

If those are the only operations to be implemented it probably makes no difference. It should be easy enough to implement + and == (and scalar multiplication) with a single sorted list representing the entire matrix. A list of rows would be helpful if you were going to implement things like vector multiplication, matrix multiplication or convolution.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1