traverse.rb

require 'rspec'
require 'forwardable'
require 'pry'
require 'set'

class ListyThing
  extend Forwardable
  def_delegators :@data, :<<, :empty?, :concat
  def initialize
    @data = []
  end
end

class MyQueue < ListyThing
  def get
    @data.shift
  end
end

class Stack < ListyThing
  def get
    @data.pop
  end
end

class Graph
  def initialize(unions)
    @unions = unions
  end
  def shortest_path(start, finish, storage=Stack.new)
    visited = Set.new
    storage << [start]
    visited.add start
    until storage.empty?
      path = storage.get
      node = path.last
      visited.add node
      paths = @unions[node].reject{|n| visited.include? n}.map{|n| path + [n]}
      p = paths.find {|p| p.last == finish}
      return p if p
      storage.concat(paths)
    end
  end
end

describe Graph do
  it "finds the shortest path" do
    unions = { 1 => [2,4],
               2 => [1,3,5],
               3 => [2,11],
               4 => [1,5,7],
               5 => [2,4,6,8],
               6 => [5,9,10],
               7 => [4,13],
               8 => [5,14],
               9 => [6,12],
               10 => [6,11],
               11 => [3,10],
               12 => [9],
               13 => [7,13],
               14 => [8,13]
    }
 
    graph = Graph.new(unions)
    expect(graph.shortest_path(1,12, Stack.new)).to eq [1, 2, 5, 6, 9, 12]
    expect(graph.shortest_path(1,12, MyQueue.new)).to eq [1, 2, 5, 6, 9, 12]
  end
 
  it "" do
    unions = { 1 => [2,3],
               2 => [1],
               3 => [1]    }
 
    graph = Graph.new(unions)
    expect(graph.shortest_path(1,3)).to eq [1, 3]
  end
end