Thread: Compacting a sparse matrix

  1. #1
    Registered User
    Join Date
    Apr 2018
    Posts
    16

    Compacting a sparse matrix

    So i'm dealing with sparse matrix and i have to compact in into a single array, for this assignment i created a struct called Point that has a line, column and value and i created an array of Points.
    So, i dont have a 2d array, just a normal array of Points with their position on the matrix (line and column) and value.
    Lets imagine my matrix its like this (the -1s dont not count as values of the matrix):

    Code:
     -1   5   6  -1  -1
     -1  -1  -1   7  -1 
      8   9  -1  -1   4
    I have to start with the line with the most elements and put those elements in the array ( thats already has a size pre defined), so, since the line with the most elements is the 3rd, it would look like this:

    Code:
    8  9  -1  -1   4
    Then comes the 2nd line, but, as you can see, i can't keep the relative positions of the elements unless i move the line 1 spot to the front, it would look like this:

    Code:
    8  9  5  6  4  -1
    In this case, the offset for the 2nd line is 1 because i had to move it 1 spot. For the final line, the one with the least elements, i have to move it 2 spots to the side, so the offset would be 2 and the final result would be:

    Code:
    8  9  5  6  4  7
    This is my goal, first i created an array with the lines sorted by number of elements, but im really struggling with putting the elements in the array and keeping their relative positions. Remember, i dont have a 2d array, a just a normal array which each element is Point with a line, column and value.
    Normally i dont ask thngs like these but im really having a hard time and getting really frustrated. Does anyone have an idea, not even code, just for a algorhytm to solve this?

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,607
    Where do relative positions come into this?

    Given this
    Code:
    -1   5   6  -1  -1
    -1  -1  -1   7  -1 
     8   9  -1  -1   4
    Your Points looks like
    2,0,8
    2,1,9
    2,4,4
    0,1,5
    0,2,6
    1,3,7
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 01-06-2016, 01:15 AM
  2. transpose sparse matrix
    By ITSONNET in forum C Programming
    Replies: 3
    Last Post: 12-22-2012, 06:56 PM
  3. adjacency matrix and sparse matrix
    By dpp in forum C Programming
    Replies: 3
    Last Post: 07-11-2010, 10:26 AM
  4. Sparse Matrix
    By brb9412 in forum C Programming
    Replies: 3
    Last Post: 01-02-2009, 01:12 PM
  5. Sparse matrix
    By milenkom in forum C++ Programming
    Replies: 4
    Last Post: 01-02-2008, 04:17 PM

Tags for this Thread