#!/usr/bin/env ruby

require 'set'

def assert_equal(expected, actual)
  raise [expected, actual].inspect unless expected == actual
end

def assert_includes(expected, actual)
  puts [expected, 'not found in', actual].inspect unless actual.include?(expected)
end

class Graph
  def initialize
    @graph = Hash.new { |h, k| h[k] = Set.new }
  end

  def connect(source, destination, _distance)
    @graph[source] << destination
    @graph[destination] << source
  end

  def paths_between(source, destination)
    visited = Hash.new { |h, k| h[k] = false }
    [].tap do |paths|
      traverse(source, destination, visited) do |found|
        paths.push(found.dup)
      end
    end
  end

  def inspect
    @graph.inspect
  end

  private

  def traverse(source, destination, visited, path = [])
    visited[source] = true
    path << source

    if source == destination
      yield path
    else
      @graph[source].each do |i|
        if visited[i] == false
          traverse(i, destination, visited, path) do |path|
            yield path
          end
        end
      end
    end

    path.pop
    visited[source] = false
  end
end

graph = Graph.new
graph.connect(:a, :b, 5)
graph.connect(:a, :d, 6)
graph.connect(:a, :f, 3)
graph.connect(:b, :c, 4)
graph.connect(:b, :e, 2)
graph.connect(:c, :d, 3)
graph.connect(:c, :e, 1)
graph.connect(:c, :g, 2)
graph.connect(:d, :e, 1)
graph.connect(:f, :g, 8)
puts graph.inspect

puts ""
puts "Paths from A to G"
results = graph.paths_between(:a, :g)
results.each do |result|
  puts result.inspect
end
assert_includes([:a,:b,:c,:g], results)
assert_includes([:a,:b,:e,:c,:g], results)
assert_includes([:a,:b,:e,:d,:c,:g], results)
assert_includes([:a,:d,:c,:g], results)
assert_includes([:a,:d,:e,:b,:c,:g], results)
assert_includes([:a,:d,:e,:c,:g], results)
assert_includes([:a,:f,:g], results)
assert_equal([
  [:a,:b,:c,:g],
  [:a,:b,:e,:c,:g],
  [:a,:b,:e,:d,:c,:g],
  [:a,:d,:c,:g],
  [:a,:d,:e,:b,:c,:g],
  [:a,:d,:e,:c,:g],
  [:a,:f,:g]
], results)

puts "Without E"
graph = Graph.new
graph.connect(:a, :b, 5)
graph.connect(:a, :d, 6)
graph.connect(:a, :f, 3)
graph.connect(:b, :c, 4)
graph.connect(:c, :d, 3)
graph.connect(:c, :g, 2)
graph.connect(:f, :g, 8)
puts graph.inspect
results = graph.paths_between(:a, :g)
results.each do |result|
  puts result.inspect
end
assert_equal([
  [:a,:b,:c,:g],
  [:a,:d,:c,:g],
  [:a,:f,:g]
], results)