Last time we met we discussed the concept of Graphs in CS. In a very general way we talked about what a Graph is, the differences between Directed and Undirected Graphs, and some of the more common categories of Graphs you might encounter in the wild. If you haven’t read that article, or need to brush up before moving on, you can check it out here.
Today I’m going to have a look at implementing a very basic Undirected Graph in Ruby. We will save the traversals and other algorithms for next time. For now our focus will be solely on implementing a Graph class.
There are several ways to do this, including using an adjacency list or an adjacency matrix. I’ve decided to use an adjacency list implementation. Mostly because it makes the most sense to me, and is probably the simplest way to implement a Graph data structure.
So, what is an adjacency list? It’s simply a list of nodes that are adjacent to a given node. Take the simple undirected, cyclic Graph shown below.
In this graph, each node would have an adjacency list associated with it. Each of those adjacency lists would have two Nodes in it.
- Node a → adjacent to [ b, c]
- Node b → adjacent to [a, c]
- Node c → adjacent to [a, b]
That’s all there is to it, we just need to keep track of the list of Nodes that are connected to a given Node. Let’s implement a Node class that does this.
There you have it, our Node class using an adjacency list. It looks a lot like the Nodes we have used in the past for Linked Lists and Trees. The main differences being that it is instantiated with an empty list representing the adjacent Nodes, and it has a function,
add_edge, that allow us to connect two Nodes.
Next step is to implement a Graph class that uses our new Node class. There are several ways to do this as well. We could keep track of the Nodes in the Graph using a List, or better yet a Set to ensure unique Nodes. However, I have elected to use a hash. Mainly because this allows us to keep a list of Nodes that will have keys based on their value. This allows us to quickly find a Node in the Graph. Check it out below.
A few things to note. First the
add_node method uses the value of the node to create the key in the
@nodes hash and sets it equal to the
node passed to it. This method could obviously benefit from some checks to see if a Node value already exists in the
@nodes hash. For simplicity and demonstration purposes I have left that out.
Another thing to note is the
add_edge method. Since we are implementing an Undirected Graph, we need to add two edges. One from
node2 and vice-versa.
That’s really all there is to it. Next time comes the fun part. How do we traverse a Graph efficiently? Much like Tree traversals we can do this in a Depth-first way or in a Breadth-first way. Throw in weighted edges and you have an even more complex problem. Check out some of the reading below until next time when we implement some of these traversals.
Adjacency list - Wikipedia
An adjacency list representation for a graph associates each vertex in the graph with the collection of its neighboring…