Introduction to Graphs in Ruby

I thought it was about time that I tackle those tricky data structures: graphs.

I'm still learning about them myself, but I thought it'd be a good idea to go over the basic types of graphs so they'll be easier to recognize when you come across one.

What are graphs?

Graphs are a data structure typically made up of vertices or nodes and edges.

What are they good for?

Graphs are useful for connecting pieces of information into a network and showing how each piece is related to another. This is why they are typically used for real-life network problems like maps of phone lines or social network designs.

What aren't they good for?

Graphs are slow and take a long time to implement and thus aren't used generally for scaling. They also aren't made to run well with algorithms built across the vertices.

Types of Graphs

There are two main categories when it comes to graphs: are they directed or undirected?

Directed graphs are graphs structures that have edges which have directions and will point to a specific vertex.

Undirected graphs are graph structures that don't have any specified directions and simply connect vertices to each other vertices.

Cyclic vs Acyclic

It is also a very important distinction in graphs if they are cyclical or acyclic.

Cyclical graphs are graph structures that can eventually point back at their own vertex.

Acyclic graphs are graph structures that will never point back at their own vertex.

Weighted vs Unweighted

Graphs can also be distinguished by whether or not their edges are weighted. Weighted edges simply means they have an integer value attached to them. This would be typical of measuring distances on a map.

As you can imagine, unweighted edges are simply empty of any type of measuring value.

Put it altogether!

So when referring to graphs, we can now decide if they are either cyclic or acyclic and undirected or directed and weighted or unweighted. The most common combination of theses that you will find out in the wild are DAGs, directed acyclic graphs.

Basic Implementation

I've wrote the simplest implementation for a graph class in Ruby which can be used to build off many of the different types of graphs.

class GraphNode

  attr_accessor :value, :neighbors

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

  def add_edge(neighbor)
  @neighbors << neighbor
  end

end

class Graph

  attr_accessor :nodes

  def initialize
    @nodes = []
  end

  def add_node(value)
  @nodes << GraphNode.new(value)
  end

end

It isn't always easy to find resources in Ruby and I adored these articles about graphs in Ruby I came across:

• Graphs in Ruby
• Graph Data Structure in Ruby
• InterviewCake's Intro to the Graph Data Structure
• GeeksForGeeks Brief Overview of Graphs

Hopefully they'll be helpful for you as well. Next time I plan to go more in depth on each type of graph with code as well. Happy coding!

Comments

[Samuel Path]

Thanks Megan, that's very helpful! :)