1#!/usr/bin/env ruby
  2
  3require 'set'
  4
  5def assert_equal(expected, actual)
  6  raise [expected, actual].inspect unless expected == actual
  7end
  8
  9def assert_includes(expected, actual)
 10  puts [expected, 'not found in', actual].inspect unless actual.include?(expected)
 11end
 12
 13class Graph
 14  def initialize
 15    @graph = Hash.new { |h, k| h[k] = Set.new }
 16  end
 17
 18  def connect(source, destination, _distance)
 19    @graph[source] << destination
 20    @graph[destination] << source
 21  end
 22
 23  def paths_between(source, destination)
 24    visited = Hash.new { |h, k| h[k] = false }
 25    [].tap do |paths|
 26      traverse(source, destination, visited) do |found|
 27        paths.push(found.dup)
 28      end
 29    end
 30  end
 31
 32  def inspect
 33    @graph.inspect
 34  end
 35
 36  private
 37
 38  def traverse(source, destination, visited, path = [])
 39    visited[source] = true
 40    path << source
 41
 42    if source == destination
 43      yield path
 44    else
 45      @graph[source].each do |i|
 46        if visited[i] == false
 47          traverse(i, destination, visited, path) do |path|
 48            yield path
 49          end
 50        end
 51      end
 52    end
 53
 54    path.pop
 55    visited[source] = false
 56  end
 57end
 58
 59graph = Graph.new
 60graph.connect(:a, :b, 5)
 61graph.connect(:a, :d, 6)
 62graph.connect(:a, :f, 3)
 63graph.connect(:b, :c, 4)
 64graph.connect(:b, :e, 2)
 65graph.connect(:c, :d, 3)
 66graph.connect(:c, :e, 1)
 67graph.connect(:c, :g, 2)
 68graph.connect(:d, :e, 1)
 69graph.connect(:f, :g, 8)
 70puts graph.inspect
 71
 72puts ""
 73puts "Paths from A to G"
 74results = graph.paths_between(:a, :g)
 75results.each do |result|
 76  puts result.inspect
 77end
 78assert_includes([:a,:b,:c,:g], results)
 79assert_includes([:a,:b,:e,:c,:g], results)
 80assert_includes([:a,:b,:e,:d,:c,:g], results)
 81assert_includes([:a,:d,:c,:g], results)
 82assert_includes([:a,:d,:e,:b,:c,:g], results)
 83assert_includes([:a,:d,:e,:c,:g], results)
 84assert_includes([:a,:f,:g], results)
 85assert_equal([
 86  [:a,:b,:c,:g],
 87  [:a,:b,:e,:c,:g],
 88  [:a,:b,:e,:d,:c,:g],
 89  [:a,:d,:c,:g],
 90  [:a,:d,:e,:b,:c,:g],
 91  [:a,:d,:e,:c,:g],
 92  [:a,:f,:g]
 93], results)
 94
 95puts "Without E"
 96graph = Graph.new
 97graph.connect(:a, :b, 5)
 98graph.connect(:a, :d, 6)
 99graph.connect(:a, :f, 3)
100graph.connect(:b, :c, 4)
101graph.connect(:c, :d, 3)
102graph.connect(:c, :g, 2)
103graph.connect(:f, :g, 8)
104puts graph.inspect
105results = graph.paths_between(:a, :g)
106results.each do |result|
107  puts result.inspect
108end
109assert_equal([
110  [:a,:b,:c,:g],
111  [:a,:d,:c,:g],
112  [:a,:f,:g]
113], results)