Bitmap Matrix and Undirected Graphs in Ruby
2023-03-19 @ 12:12I’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!