Graphs in Ruby Pt. 1 — Representation
I’ve been brushing up on my CS fundamentals recently. Specifically, I’ve been thinking a lot about graphs. And one thing that’s always bothered me is the relative lack of resources for learning about them in Ruby. As a result, while I work through various graph-related problems in ruby, I’ve decided to document the process on this blog, in the hopes that it might be helpful to others.
In this first part of my series on graphs in Ruby, I’ll just be introducing a couple of methods of representing graphs, implemented in Ruby. These implementations are the building blocks that we’ll need to start working on solving problems in Part 2. Let’s jump right in.
Representation #1: The Adjacency Matrix
What is an adjacency matrix? Well, let’s say we have a graph with N vertices. The idea behind an Adjacency Matrix is that we store an NxN matrix, where each element (i,j) is 0 when there is no edge between vertex i and vertex j, and 1 when there is such an edge. This is probably the simplest way to represent a graph in code. I want to talk a little bit about the pros and cons of this representation, but first I'll introduce what I came up with for an implementation in Ruby.
I began by deciding on a basic interface for my graph. I wanted to be able to do the following operations:
add_edge- Add an edge to the graphremove_edge- Remove an edge from the graphedge?(i, j)- Check if there is an edge connecting two vertices,iandjto_s- Pretty-print the graph's contentselement(i, j)- Get the element at(i, j)row(i)- Get theith row
I also wanted to support undirected and directed implementations, and check for OutOfBounds errors.
Let’s look at some RSpec tests I created to ensure the implementation works properly. First, for creation:
Basically the above ensures that we can create a blank MatrixGraph with all vertices initialized to zero.
Now for the tests about adding and removing edges:
This is the basic functionality I hoped to get out of my initial adjacency matrix implementation. Here’s the code I ended up with:
As you can see the class itself is extremely simple. It creates a graph with a supplied number of vertices, it allows you to add and remove edges. It allows you to check if edges exist and get specific elements and rows, and it prints the current graph.
Note that I’ve employed the Strategy Pattern to separate the difference in logic between undirected and directed graphs:
As you can see this class encapsulates the idea that when we add or remove an edge, we must also add or remove its corresponding edge. For example, if you do graph.add_edge(1, 2), then in an undirected graph, you must also do graph.add_edge(2, 1), since having the first one implies that the second must also be included.
Here’s the corresponding class for directed graphs, where this extra step is not necessary:
I have also used the with_bounds_check method to ensure that we raise an error when any of our methods are called with invalid vertex indices. Its implementation looks like this:
So that’s our implementation. It’s really very straightforward, but this is all you need to represent a graph in Ruby.
Visualizing our graphs
It can be a bit tough to visualize a graph based purely on code, so I also wrote a small ruby script using Shoes to print a geometric representation of a graph on a computer screen.
Let’s look at an example of how we can view one representation of a graph created with my MatrixGraph class.
This one-liner is enough to create a simple image:
Not too interesting. But this is our graph as it stands. It is just a collection of nine vertices without any edges between them. Now let’s try adding an edge:
There we go, now we can see that an edge has been added betwen the first two vertices. By the way, here’s the output of graph.to_s (array-based implementation):
As you can see, the elements at (0, 1) and (1, 0) are set to 1, representing the edge shown above.
Let’s add a few more edges:
And here’s the resulting graph:
Pros and cons of the Adjacency Matrix
The MatrixGraph approach has some benefits. For one thing, checking the inclusion of an edge is dead simple and runs in O(1) time, since all you need to do is get elements[i][j]. Additionally, when we have dense graphs (where a given element has edges to a significant portion of all other elements), this is more efficient than other representations. The operation of adding new edges is also a constant-time, simple operation.
Unfortunately, there are also some cons to the Adjacency Matrix approach. Namely, when dealing with sparse graphs (like the ones shown above), we’re wasting a lot of memory by storing zeros for every possible edge location, when there are only a handful of ones. And if you wanted to go through the graph and find all of the edges, that operation would be O(N^2), which is particularly unfortunate when we have a sparse graph where most of this traversal is useless.
There is one other major way to represent graphs, which we’ll look at now. It’s called an Adjacency List.
Graph Representation #2: Adjacency List
The basic idea behind the Adjacency List is that, instead of having an NxN array of arrays, we have an array of linked lists. This way, when we have a sparse graph, the total amount of memory being used can be lower than with adjacency matrices (O(N) instead of O(N^2)).
In order to look at how to represent this structure in Ruby, we first need an implementation of a Linked List. So I went ahead and began by creating a class to accomplish that.
First of all, here are the specs governing this ListNode class:
Basically we need to be able to add and remove elements, print the elements in a list, and check if a given element is contained in the list.
Here’s the actual implementation for this:
I believe this implementation is pretty straightforward, so now let’s introduce the Adjacency List representation of a graph that uses the above class. The external interface is pretty much the same (though slightly slimmed-down) as the one for the Adjacency Matrix so I won’t show the test cases, but here’s the class itself:
Once again we end up with a tiny, compact class that looks very similar to the previous one. The main difference is that we’re using an array of linked lists under the hood. This isn’t overly clear when looking at the code, but it can make a difference in our runtime and space complexities.
Adjacency List Pros and Cons
Let’s think again about how switching to Linked Lists changes our class’s behavior. The biggest pro is the fact that now when we have a sparse graph (such as a friendship graph, road network etc), we can save a lot of memory by only storing a value in the list if an edge exists, and assuming it doesn’t exist otherwise. This can make a huge speed difference when we start actually using these graphs to run algorithms. With the Adjacency Matrix, we had no choice but to always store O(N^2) elements. Now with the Adjacency List we can often store O(N) elements, which can make the difference between an algorithm being slow or fast.
Having said that, there are also some drawbacks to this approach. For one thing, adding a new edge requires traversal of the linked list for the given vertex, and is therefore O(N) instead of O(1) as it was before. Checking inclusion of a given edge is also no longer possible in constant-time, since again we must traverse a linked list and search for the given vertex.
Despite these drawbacks, adjacency lists are superior to adjacency matrices in the majority of applications. So in the upcoming posts in this series, I will typically use my adjacency list representation by default, unless there’s a specific reason not to. And that about sums up the ruby graph implementations that I’ll be using as I continue to explore graphs and CS concepts in ruby. Here is a link to all of the source code for this post, and thanks for reading!
