Tutorialspoint.dev

Sparse Matrix and its representations | Set 2 (Using List of Lists and Dictionary of keys)

Prerequisite : Sparse Matrix and its representations Set 1 (Using Arrays and Linked Lists)

In this post other two methods of sparse matrix representation are discussed.

  1. List of Lists
  2. Dictionary

List of Lists (LIL)

One of the possible representation of sparse matrix is List of Lists (LIL). Where one list is used to represent the rows and each row contains the list of triples: Column index, Value(non – zero element) and address field, for non – zero elements. For the best performance both lists should be stored in order of ascending keys.

Sparse-Matrix-List-of-Lists

// C program for Sparse Matrix Representation
// using List Of Lists
#include<stdio.h>
#include<stdlib.h>
#define R 4
#define C 5
  
// Node to represent row - list
struct row_list
{
    int row_number;
    struct row_list *link_down;
    struct value_list *link_right;
};
  
// Node to represent triples
struct value_list
{
    int column_index;
    int value;
    struct value_list *next;
};
  
// Fuction to create node for non - zero elements
void create_value_node(int data, int j, struct row_list **z)
{
    struct value_list *temp, *d;
  
    // Create new node dynamically
    temp = (struct value_list*)malloc(sizeof(struct value_list));
    temp->column_index = j+1;
    temp->value = data;
    temp->next = NULL;
  
    // Connect with row list
    if ((*z)->link_right==NULL)
        (*z)->link_right = temp;
    else
    {
        // d points to data list node
        d = (*z)->link_right;
        while(d->next != NULL)
            d = d->next;
        d->next = temp;
    }
}
  
// Function to create row list
void create_row_list(struct row_list **start, int row,
                    int column, int Sparse_Matrix[R][C])
{
    // For every row, node is created
    for (int i = 0; i < row; i++)
    {
        struct row_list *z, *r;
  
        // Create new node dynamically
        z = (struct row_list*)malloc(sizeof(struct row_list));
        z->row_number = i+1;
        z->link_down = NULL;
        z->link_right = NULL;
        if (i==0)
            *start = z;
        else
        {
            r = *start;
            while (r->link_down != NULL)
                r = r->link_down;
            r->link_down = z;
        }
  
        // Firstiy node for row is created,
        // and then travering is done in that row
        for (int j = 0; j < 5; j++)
        {
            if (Sparse_Matrix[i][j] != 0)
            {
                create_value_node(Sparse_Matrix[i][j], j, &z);
            }
        }
    }
}
  
//Function display data of LIL
void print_LIL(struct row_list *start)
{
    struct row_list *r;
    struct value_list *z;
    r = start;
  
    // Traversing row list
    while (r != NULL)
    {
        if (r->link_right != NULL)
        {
            printf("row=%d ", r->row_number);
            z = r->link_right;
  
            // Traversing data list
            while (z != NULL)
            {
                printf("column=%d value=%d ",
                     z->column_index, z->value);
                z = z->next;
            }
        }
        r = r->link_down;
    }
}
  
//Driver of the program
int main()
{
    // Assume 4x5 sparse matrix
    int Sparse_Matrix[R][C] =
    {
        {0 , 0 , 3 , 0 , 4 },
        {0 , 0 , 5 , 7 , 0 },
        {0 , 0 , 0 , 0 , 0 },
        {0 , 2 , 6 , 0 , 0 }
    };
  
    // Start with the empty List of lists
    struct row_list* start = NULL;
  
    //Function creating List of Lists
    create_row_list(&start, R, C, Sparse_Matrix);
  
    // Display data of List of lists
    print_LIL(start);
    return 0;
}

Output:

row = 1 
column = 3 value = 3 
column = 5 value = 4 
row = 2 
column = 3 value = 5 
column = 4 value = 7 
row = 4 
column = 2 value = 2 
column = 3 value = 6 

 

Dictionary of Keys

An alternative representation of sparse matrix is Dictionary. For the key field of the dictionary, pair of row and column index is used that maps with the non – zero element of the matrix. This method saves space but sequential access of items is costly.
In C++, dictionary is defined as map class of STL(Standard Template Library). To know more about map click the link below:
Basics of map



// C++ program for Sparse Matrix Representation
// using Dictionary
#include<bits/stdc++.h>
using namespace std;
#define R 4
#define C 5
  
// Driver of the program
int main()
{
    // Assume 4x5 sparse matrix
    int Sparse_Matrix[R][C] =
    {
        {0 , 0 , 3 , 0 , 4 },
        {0 , 0 , 5 , 7 , 0 },
        {0 , 0 , 0 , 0 , 0 },
        {0 , 2 , 6 , 0 , 0 }
    };
  
    /* Declaration of map where first field(pair of
       row and column) represent key and second
       field represent value */
    map< pair<int,int>, int > new_matrix;
  
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            if (Sparse_Matrix[i][j] != 0)
                new_matrix[make_pair(i+1,j+1)] =
                                Sparse_Matrix[i][j] ;
  
    int c = 0;
  
    // Iteration over map
    for (auto i = new_matrix.begin(); i != new_matrix.end(); i++ )
    {
        if (c != i->first.first)
        {
            cout << "row = " << i->first.first << endl ;
            c = i->first.first;
        }
        cout << "column = " << i->first.second <<" ";
        cout << "value = " << i->second << endl;
    }
  
    return 0;
}

Output:

row = 1
column = 3 value = 3
column = 5 value = 4
row = 2
column = 3 value = 5
column = 4 value = 7
row = 4
column = 2 value = 2
column = 3 value = 6

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter