Graph implementation in Ruby

graph.rb

class Graph
  def initialize
    @nodes = []
  end

  def add_node(name)
    fail 'Node already exists!' if find_node(name)
    nodes << Node.new(name)
    nodes.last
  end

  def find_node(name)
    nodes.find { |node| node.name == name }
  end

  def connect_nodes(node1, node2)
    node1.connect(node2)
    node2.connect(node1)
  end

  def connected_depth?(start_node, end_node)
    nodes.each { |node| node.traversed = false }
    depth_first_search(start_node)
    end_node.traversed?
  end

  def connected_breadth?(start_node, end_node)
    nodes.each { |node| node.traversed = false }
    breadth_first_search(start_node)
    end_node.traversed?
  end

  def find_shortest_path(start_node, end_node)
    nodes.each { |node| node.reset }
    set_shortest_paths(start_node)
    path = collect_path(end_node)
    path.first == start_node ? path : []
  end

  def print
    nodes.each { |node| puts node.print }
  end

  private

  def set_shortest_paths(start_node)
    start_node.distance = 0
    untraversed = [start_node]

    until untraversed.empty?
      current = untraversed.shift
      current.traversed = true
      current.connections.each do |connected|
        distance_from_start = current.distance + 1
        if distance_from_start < connected.distance
          connected.distance = distance_from_start
          connected.parent = current
        end
        untraversed << connected unless connected.traversed?
      end
    end
  end

  def collect_path(end_node)
    node = end_node
    path = []
    while node
      path << node
      node = node.parent
    end
    path.reverse
  end

  def depth_first_search(node)
    node.traversed = true
    node.connections.each do |connected|
      depth_first_search(connected) unless connected.traversed?
    end
  end

  def breadth_first_search(start_node)
    untraversed = [start_node]

    until untraversed.empty?
      node = untraversed.shift
      node.traversed = true
      node.connections.each do |connected|
        untraversed << connected unless connected.traversed?
      end
    end
  end

  attr_accessor :nodes

  class Node
    def initialize(name, connections = [])
      @name = name
      @connections = connections
      @traversed = false
    end

    def connect(node)
      connections << node
      connections.uniq!
    end

    def reset
      @traversed = false
      @parent = nil
      @distance = Float::INFINITY
    end

    def print
      puts "#{name}: #{connections.map(&:name).join(', ')}"
    end

    attr_accessor :name, :connections, :traversed, :parent, :distance
    alias_method :traversed?, :traversed
  end
end

# Usage
graph = Graph.new
a = graph.add_node('a')
b = graph.add_node('b')
c = graph.add_node('c')
d = graph.add_node('d')
e = graph.add_node('e')
f = graph.add_node('f')
g = graph.add_node('g')
h = graph.add_node('h')
i = graph.add_node('i')
j = graph.add_node('j')

graph.connect_nodes(a, b)
graph.connect_nodes(a, c)
graph.connect_nodes(a, d)
graph.connect_nodes(d, e)
graph.connect_nodes(e, c)
graph.connect_nodes(b, g)
graph.connect_nodes(c, h)
graph.connect_nodes(c, f)
graph.connect_nodes(g, h)
graph.connect_nodes(h, f)
graph.connect_nodes(i, j)

puts 'Testing depth first search:'
puts "a and f are #{graph.connected_depth?(a, f) ? '' : 'not '}connected"
puts "a and i are #{graph.connected_depth?(a, i) ? '' : 'not '}connected\n\n"

puts 'Testing breadth first search:'
puts "a and f are #{graph.connected_breadth?(a, f) ? '' : 'not '}connected"
puts "a and i are #{graph.connected_breadth?(a, i) ? '' : 'not '}connected\n\n"

puts 'Testing find_shortest_path:'
path_a_to_h = graph.find_shortest_path(a, h)
if path_a_to_h.any?
  puts "path from a to h: #{path_a_to_h.map(&:name).join(', ')}"
else
  puts 'no path from a to h'
end

path_e_to_g = graph.find_shortest_path(e, g)
if path_e_to_g.any?
  puts "path from e to g: #{path_e_to_g.map(&:name).join(', ')}"
else
  puts 'no path from e to g'
end

path_a_to_i = graph.find_shortest_path(a, i)
if path_a_to_i.any?
  puts "path from a to i: #{path_a_to_i.map(&:name).join(', ')}"
else
  puts 'no path from a to i'
end

Output:

Testing depth first search:
a and f are connected
a and i are not connected

Testing breadth first search:
a and f are connected
a and i are not connected

Testing find_shortest_path:
path from a to h: a, c, h
path from e to g: e, c, h, g
no path from a to i