1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
#!/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)
|
