Bitmap Matrix and Undirected Graphs in Ruby

2023-03-19 @ 12:12

I’ve been working my way through Engineering a Compiler. I really enjoy the book, but one part has you build an interference graph for doing register allocation via graph coloring. An interference graph is an undirected graph, and one way you can represent an undirected graph is with a bitmap matrix.

A bitmap matrix is just a matrix but the values in the matrix can only be 1 or 0. If every node in your graph maps to an index, you can use the bitmap matrix to represent edges in the graph.

I made a bitmap matrix implementation that I like, but I think the code is too trivial to put in a Gem. Here is the code I used:

class BitMatrix
  def initialize size
    @size = size
    size = (size + 7) & -8 # round up to the nearest multiple of 8
    @row_bytes = size / 8
    @buffer = "\0".b * (@row_bytes * size)
  end

  def initialize_copy other
    @buffer = @buffer.dup
  end

  def set x, y
    raise IndexError if y >= @size || x >= @size

    x, y = [y, x].sort

    row = x * @row_bytes
    column_byte = y / 8
    column_bit = 1 << (y % 8)

    @buffer.setbyte(row + column_byte, @buffer.getbyte(row + column_byte) | column_bit)
  end

  def set? x, y
    raise IndexError if y >= @size || x >= @size

    x, y = [y, x].sort

    row = x * @row_bytes
    column_byte = y / 8
    column_bit = 1 << (y % 8)

    (@buffer.getbyte(row + column_byte) & column_bit) != 0
  end

  def each_pair
    return enum_for(:each_pair) unless block_given?

    @buffer.bytes.each_with_index do |byte, i|
      row = i / @row_bytes
      column = i % @row_bytes
      8.times do |j|
        if (1 << j) & byte != 0
          yield [row, (column * 8) + j]
        end
      end
    end
  end

  def to_dot
    "graph g {\n" + each_pair.map { |x, y| "#{x} -- #{y};" }.join("\n") + "\n}"
  end
end

I like this implementation because all bits are packed in to a binary string. Copying the matrix is trivial because we just have to dup the string. Memory usage is much smaller than if every node in the graph were to store an actual reference to other nodes.

Anyway, this was fun to write and I hope someone finds it useful!

« go back