A Bit Matrix in C#

The other day I was testing very large graphs. I needed a data structure to store information about which nodes in the graph are connected to each other. For example if a graph had four nodes and node 0 was connected to nodes 1 and 3 I could use a 4 by 4 matrix of booleans where the entries in the first row are false (node 0 is not connected to itself), true (node 0 is connected to node 1), false, and true. See image below. But using booleans uses a lot of space. If a boolean is 32 bits then the matrix for a very large graph could be too large to fit in memory. So I wanted a matrix of bits which would allow me to store 32 true or false values at a time. In the old days with C++ I’d have had to write a lot of bit manipulation code with shifting and masks. I’ve done this before and it’s not fun. But C# has a BitArray class that stores an array of booleans as bits which made creating a BitMatrix class very easy. Calling the class looks like:

BitMatrix matrix = new BitMatrix(4); // create a 4×4 matrix
matrix.SetValue(0, 1, true); // [0,1] = true
. . .
bool b = matrix.GetValue(0, 1); // fetch value at [0, 1]
Console.WriteLine(b.ToString()); // display as 0s and 1s
. . .

Here’s my BitMatrix class:

class BitMatrix
{
  public BitArray[] data; // an array of arrays
  public int dim; // dimension

  public BitMatrix(int n)
  {
    this.data = new BitArray[n];
    for (int i = 0; i < data.Length; ++i)
    {
      this.data[i] = new BitArray(n);
    }
    this.dim = n;
  }
  public bool GetValue(int row, int col)
  {
    return data[row][col];
  }
  public void SetValue(int row, int col, bool value)
  {
    data[row][col] = value;
  }
  public override string ToString()
  {
    string s = “”;
    for (int i = 0; i < data.Length; ++i)
    {
      for (int j = 0; j < data[i].Length; ++j)
      {
        if (data[i][j] == true) s += “1 “; else s += “0 “;
      }
        s += Environment.NewLine;
      }
      return s;
  }

} // class BitMatrix

Advertisements
This entry was posted in Software Test Automation. Bookmark the permalink.