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.
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:
https://gist.github.com/f435103a553c28f0939bcf291551d70b
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.
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:
https://gist.github.com/c65cccd51263a06400077454f686a5b8
This 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:
https://gist.github.com/2fa60e2945137bf4bd6d7316b47cb0fb
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:
https://gist.github.com/cd980b4852658ab68f674126c53d492e
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!