Java Sparse Matrix creation

Question

I'm currently creating a sparse matrix program that uses a SparseMatrixNode:

 public SparseMatrixNode(int row, int col, int value, SparseMatrixNode down, SparseMatrixNode across)
  {
      this.row = row;
      this.col = col;
      this.value = value;
      this.down = down;
      this.across = across;
  }

My program creates the template sparse matrix like so:

  public SparseMatrix()
  {
    noofrows=noofcols=0;    
    // create the top-left entry point cell
    root=new SparseMatrixNode(0, 0, 0, new SparseMatrixNode(0, 0, 0, null, null), new SparseMatrixNode(0, 0, 0, null, null));
  }     


  public void Create(int noofrows, int noofcols)
  {
      this.noofrows=noofrows;
      this.noofcols=noofcols;
      root=new SparseMatrixNode(0, 0, 0, new SparseMatrixNode(noofrows+1, 0, 0, null, null), new SparseMatrixNode(0, noofcols+1, 0, null, null));
  }

And this is my SetValue function which takes three integer values supplied to either replace a current value or create a new node and insert it into the Sparse Matrix.

 public void SetValue(int row, int col, int value)
  {     
      if (value == 0)
      {
          return;
      }
      else
      {
          SparseMatrixNode checkNode = FindNode(row, col);
          if (checkNode.value != 0)
          {
              checkNode.setValue(value);
          }
          //SparseMatrixNode dummyRow = root.FindRow(row);
          if (root.down.row == 5)
          {
              root.down = new SparseMatrixNode(row, 0, 0, null, new SparseMatrixNode(row, col, value, null, null));
              root.across = new SparseMatrixNode(0, col, 0, new SparseMatrixNode(row, col, value, null, null), null);
          }          
      }

However when I test my code based on a 4x4 grid and calling SetValue(1, 2, 5), it simply outputs a grid of 0's. I've been trying to step through my code and find out why it doesn't input the new node however i've been stuck for hours and was wondering if anyone could shine some light on the situation?

So my question is: why does my SetValue function not create a new node and link it to the "dummy" across and down properties (row 0 column 0)?

Answer 1

It is hard to say what is wrong if you don't show the Find method and the code responsible for printing.

However, your approach seems a bit convoluted to me. I find it easier to use a Map of Positions to values (this is the so called Dictionary of Keys representation). It is worth noting that there may be more efficient storage formats for Sparse matrices, depending on what operation you want to perform. A few canonical examples are listed here.

Below is a working example for the Dictionary of Keys approach.

import java.util.*;

class Position {
    private Integer row, col;

    public Position(int row, int col)
    {
        this.row = row;
        this.col = col;
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Position))
            return false;
        Position other = (Position)o;
        return row == other.row && col == other.col;
    }

    @Override
    public int hashCode() {
        return 31 * row.hashCode() + col.hashCode();
    }

    @Override
    public String toString() {
        return String.format("(%d, %d)", row, col);
    }

}

public class SparseMatrix {

    private Map<Position, Integer> nnzs = new HashMap<>();
    private int maxRows, maxCols;

    public SparseMatrix(int maxRows, int maxCols) {
        this.maxRows = maxRows;
        this.maxCols = maxCols;
    }

    public void SetValue(int row, int col, int value) {     
        if (row > maxRows || col > maxCols)
            throw new RuntimeException("Position out of bounds");
        nnzs.put(new Position(row, col), value);
    }

    public static void main(String[] args) {
        SparseMatrix sp = new SparseMatrix(10, 10);
        sp.SetValue(1, 2, 5);
        System.out.println(sp.nnzs);
        sp.SetValue(1, 2, 7);
        sp.SetValue(1, 10, 8);
        System.out.println(sp.nnzs);
    }
}

Output:

javac SparseMatrix.java && java SparseMatrix
{(1, 2)=5}
{(1, 2)=7, (1, 10)=8}