Problem when inserting in a Sparse Matrix

Question

I have to implement the CSR matrix data structure in C++ using 3 dynamic arrays (indexing starts at 0) and I've got stuck. So I have to implement 2 functions:

1) modify(int i, int j, TElem e) - modifies the value of (i,j) to e or adds if (if it does not exist) or deletes it if e is null.

2) element(int i, int j) const - returns the value found on (i,j)

I wanted to test my code in the next way:

Matrix m(10, 10);
    for (int j = 0; j < m.nrColumns(); j++) {
        m.modify(4, j, 3);
    }                                                             
    for (int i = 0; i < m.nrLines(); i++)
        for (int j = 0; j < m.nrColumns(); j++)
            if (i == 4)
                assert(m.element(i, j) == 3);
            else
                assert(m.element(i, j) == NULL_TELEM);

And I got a surprise to see that m.element(4,j) will be 0 for j in the range (0,8) and only 3 for j=9.

This is my implementation of element(int i, int j) :

    int currCol;
    for (int pos = this->lines[i]; pos < this->lines[i+1]; pos++) {
        currCol = this->columns[pos];
        if (currCol == j)
            return this->values[pos];
        else if (currCol > j)
            break;
    }
    return NULL_TELEM;

The constructor looks like this:

Matrix::Matrix(int nrLines, int nrCols) {
    if (nrLines <= 0 || nrCols <= 0)
        throw exception();
    this->nr_lines = nrLines;
    this->nr_columns = nrCols;
    this->values = new TElem[1000];
    this->values_capacity = 1;
    this->values_size = 0; 
    this->lines = new int[nrLines + 1];
    this->columns = new TElem[1000];
    this->columns_capacity = 1;
    this->columns_size = 0; 
    for (int i = 0; i <= nrLines; i++)
        this->lines[i] = NULL_TELEM;
}

This is the "modify" method:

TElem Matrix::modify(int i, int j, TElem e) {
    if (i < 0 || j < 0 || i >= this->nr_lines || j >= nr_columns)
        throw exception();
    int pos = this->lines[i];
    int currCol = 0;
    for (; pos < this->lines[i + 1]; i++) {
        currCol = this->columns[pos];
        if (currCol >= j)
            break;
    }
    if (currCol != j) {
        if (!(e == 0)) 
            add(pos, i, j, e);
    }
    else if (e == 0)
        remove(pos, i);
    else
        this->values[pos] = e;
    return NULL_TELEM;
}

And this is the inserting method:

void Matrix::add(int index, int line, int column, TElem value)
{
    this->columns_size++;
    this->values_size++;
    for (int i = this->columns_size; i >= index + 1; i--) {
        this->columns[i] = this->columns[i - 1];
        this->values[i] = this->values[i - 1];
    }
    this->columns[index] = column;
    this->values[index] = value;
    for (int i = line + 1; i <= this->nr_lines; i++)
        this->lines[i]++;
}

Can somebody help me, please? I can't figure out why this happens and I really need to finish this implementation these days. It's pretty weird that is sees those positions having the value 0.

So having the next test that starts in the next way, I get a memory acces violation:

Matrix m(200, 300);
    for (int i = m.nrLines() / 2; i < m.nrLines(); i++) {
        for (int j = 0; j <= m.nrColumns() / 2; j++)
        {
            int v1 = j;
            int v2 = m.nrColumns() - v1 - 1;
            if (i % 2 == 0 && v1 % 2 == 0)
                m.modify(i, v1, i * v1);
            else
                if (v1 % 3 == 0)
                    m.modify(i, v1, i + v1);
            if (i % 2 == 0 && v2 % 2 == 0)
                m.modify(i, v2, i * v2);
            else
                if (v2 % 3 == 0)
                    m.modify(i, v2, i + v2);
        }

The error is thrown in the method "modify" at currCol = this->column[pos];

And if I look into the debugger it looks like:i=168, lines[i]=-842150451, lines[i+1]=10180,pos=-842150451.

Does anybody have any ideas why it looks this way?

M Oehm · Accepted Answer · 2020-03-21 10:31:38Z

1

Your code has two small errors.

When you try to find the insertion position in modify, you loop over the non-empty elements in the row:

int currCol = 0;

for (; pos < this->lines[i + 1]; i++) {
    currCol = this->columns[pos];
    if (currCol >= j)
        break;
}

Here, you must update pos++ in each iteration instead of i++.

The second error occurs when you insert an element into column 0. The currCol will be zero, but your condition for adding a new element is

if (currCol != j) {
    if (!(e == 0)) 
        add(pos, i, j, e);
}

But j is zero, too, so nothing will be inserted. You can fix this by starting with a non-existing column:

int currCol = -1;

answered Mar 21, 2020 at 10:31

M Oehm

29.2k3 gold badges36 silver badges44 bronze badges

Sign up to request clarification or add additional context in comments.

12 Comments

Andrei Gabor Over a year ago

Thank you very much! Now it works perfectly on that test. Now I have another test and I get a memory acces violation error... I don't know why that happens. I'll edit the post right now and post it.

M Oehm Over a year ago

I'm glad it works now, but please don't edit the question after the fact. SO is supposed to be a repository of questions and answer, not a discussion. By editing the question my anser now refers to only a part of the question. I think you should open a new question if you face another problem.

M Oehm Over a year ago

On another note, you can also try to find out what's going on by printing the contents of your arrays after each step. The matrix is only 10x10 and you can see what's going on. (The weird indices look as if you had swapped in some gerbage from beyond the valid array limits.)

M Oehm Over a year ago

Well, reduce the test. It's quite likely that the same error will occur on a smaller matrix. Don't stick too close to the course script. You have to try out things!

Andrei Gabor Over a year ago

It works perfectly on 20x30, but it should behave the same way on 200x300. There is no difference. And I get that memory acces violation. Also I've changed the size of vectors to [1000] but that isn't the problem.

|

Collectives™ on Stack Overflow

Problem when inserting in a Sparse Matrix

1 Answer 1

12 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

12 Comments

Your Answer

Sign up or log in

Post as a guest

Related