Graphs in Ruby Pt. 1.5 — Refactoring
Since my previous post on representing graphs in ruby, I’ve changed my mind about a few things. I went through and did some refactoring to achieve what I believe is a superior ruby implementation of the two graph types: Adjacency Matrix and Adjacency List. In this post I’d like to quickly go over how I changed the code, so that my later posts on this topic make sense.
The situation pre-refactor
Just as a reminder, here’s what the project’s directory structure looked like when I wrote my original post introducint the code:
As you can see, I used the concept of Edge Strategies
and Storage Strategies
and created factory classes to create these for a single Graph
base class that mostly just delegated to one of these strategies to achieve various behavior. I had versions of these that were tied to List
and Matrix
Graphs directly, and folders to store these.
Here’s the original Graph
class:
This is one way of achieving some level of decoupling, but through refactoring I came up with a different method that I think I like better.
The updated implementation
Here’s the new file structure I ended up with:
Clearly this is much simpler than the previous screenshot, which reflects the fact that the code has been simplified as well. Despite this, one thing that has not changed is the fact that we have one central Graph
class:
The class has grown somewhat, but its behavior requires less delegation and instead it contains most of the logic needed to represent a graph. There is still some polymorphism happening, but I’ve encapsulated it to the vertex_list_class
method, which controls what kind of list we're using for the vertexes in the base element array.
Doing this removes the need to do all of the stuff with factories and strategies that I was doing in my previous post. Now all we need to do is add an ArrayVertexList
class that fulfills the same interface as our ListNode
class, which allows us to use them interchangeably. This is now the only difference between an adjacency list-based graph and an adjaceny matrix-based graph.
Here’s what the ArrayVertexList
looks like:
This class keeps the relatively low-level HAS_VERTEX
and NO_VERTEX
in one place, which limits the changes necessary in other classes as a result of these constants' behavior changing.
So that’s the main change that I made. This allowed me to remove the concepts of Edge Strategy
and Storage Strategy
and generally delete a lot of code. One other small change is that I created a Components
namespace to store the above class and the ListNode
class.
I’ve also given the whole project a new namespace of Graphs
, which I think is a better overall description for the library, and I've switched from using require_relative
to adding the base directory to the LOAD_PATH
in graphs.rb
and using the normal require
.
I did also expand a Graph’s functionality a bit, by adding the following methods to its public interface:
The add_vertex
and remove_vertex
make constructing new graphs easier and more flexible. The incident_vertices
method should be useful for traversals, which is what I will discuss in part 2 of this series!