# Bitmap Matrix and Undirected Graphs in Ruby

Mar 19, 2023 @ 12:12 pmI’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!