Implementing an Undirected Graph in Ruby

Data Structures & Algorithms

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.

class Node

  attr_reader :value

  def initialize(value)
    @value = value
    @adjacent_nodes = []
  end

  def add_edge(adjacent_node)
    @adjacent_nodes << adjacent_node
  end

end

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.

class Graph

  def initialize
    @nodes = {}
  end

  def add_node(node)
    @nodes[node.value] = node
  end

  def add_edge(node1, node2)
    @nodes[node1].add_edge(@nodes[node2])
    @nodes[node2].add_edge(@nodes[node1])
  end

end

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 node1 to 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

Graph Traversal - Wikipedia