Commit 1b281e9

mo khan <mo@mokhan.ca>
2025-01-23 01:01:48
Add ruby code to prove graph traversal
main
1 parent 08fe640
Changed files (4)
assignments
3
graph.rb
main.rb
3-solution.md
3431709-assignment-3.pdf
assignments/3/graph.rb
@@ -0,0 +1,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)
assignments/3/main.rb
@@ -1,158 +0,0 @@
-#!/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
-
-=begin
-  A<->B: 5
-  A<->D: 6
-  A<->F: 3
-  B<->C: 4
-  B<->E: 2
-  C<->D: 3
-  C<->E: 1
-  C<->G: 2
-  D<->E: 1
-  F<->G: 8
-=end
-
-# class Edge
-#   attr_reader :source, :destination, :distance
-
-#   def initialize(source, destination, distance)
-#     @source = source
-#     @destination = destination
-#     @distance = distance
-#   end
-
-#   def to_s
-#     "#{source.title}->#{destination.title}: #{distance}"
-#   end
-
-# end
-
-# class Node
-#   attr_reader :title, :edges
-
-#   def initialize(title:)
-#     @title = title
-#     @edges = []
-#   end
-
-#   def to(node, distance)
-#     @edges.push(Edge.new(self, node, distance))
-#   end
-
-#   def each
-#     @edges.each do |edge|
-#       yield edge
-#     end
-#   end
-
-#   def to_s
-#     title
-#   end
-
-#   def inspect
-#     to_s
-#   end
-# end
-
-class Graph
-  def initialize
-    @nodes = Hash.new { |h, k| h[k] = Set.new }
-  end
-
-  def connect(source, destination, weight)
-    @nodes[source] << destination
-    @nodes[destination] << source
-  end
-
-  def simple_paths(source, destination)
-    return [source] if source == destination
-
-    @nodes[source].each do |other|
-      puts other
-      items = simple_paths(other, destination)
-      # if items.any?
-      #   return [source, items]
-      # end
-    end
-
-    []
-  end
-
-  def inspect
-    @nodes.inspect
-  end
-end
-
-# a = Node.new(title: "A")
-# b = Node.new(title: "B")
-# c = Node.new(title: "C")
-# d = Node.new(title: "D")
-# e = Node.new(title: "E")
-# f = Node.new(title: "F")
-# g = Node.new(title: "G")
-
-
-# a.to(b, 5)
-# a.to(d, 6)
-# a.to(f, 3)
-# b.to(c, 4)
-# b.to(e, 2)
-# c.to(d, 3)
-# c.to(e, 1)
-# c.to(g, 2)
-# d.to(e, 1)
-# f.to(g, 8)
-
-# [a,b,c,d,e,f,g].each do |node|
-#   node.each do |edge|
-#     puts edge.to_s
-#   end
-# end
-
-# puts ""
-# puts "Paths from A to G"
-# assert_includes([a,b,c,g], results)
-# assert_includes([a,b,e,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,d,c,g],
-#   [a,d,e,b,c,g],
-#   [a,d,e,c,g],
-#   [a,f,g]
-# ], results)
-
-
-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"
-
-graph.simple_paths(:a, :g)
assignments/3-solution.md
@@ -45,13 +45,14 @@ Chapter 7:
     F<->G: 8
   ```
 
-  There are 6 simple paths
+  There are 7 simple paths
 
   ```plaintext
   | Path        |
   | ----        |
   | 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   |
@@ -60,13 +61,16 @@ Chapter 7:
 
 >  b. What is the shortest path from node A to node G? What is the overall delay?
 
-  The shortest path has a distance of 10. The overall delay is 11.
+  The shortest path has a distance of 10.
+  The overall delay is 11 (`((11 + 10 + 13 + 11 + 15 + 10 + 11)/7) = 11`).
+
 
   ```plaintext
   | Path        | Total Distance |
   | ----        | -------------- |
   | a,b,c,g     | 5+4+2 = 11     |
   | a,b,e,c,g   | 5+2+1+2 = 10   |
+  | a,b,e,d,c,g | 5+2+1+3+2 = 13 |
   | a,d,c,g     | 6+3+2 = 11     |
   | a,d,e,b,c,g | 6+1+2+4+2 = 15 |
   | a,d,e,c,g   | 6+1+1+2 = 10   |
@@ -95,6 +99,12 @@ Chapter 7:
   | a,f,g       | 3+8 = 11       |
   ```
 
+The following code can be used to prove these results:
+
+```ruby
+!include assignments/3/graph.rb
+```
+
 Chapter 8:
 
 > 9. Using a Caesar cipher with s = 5, decode the received message RTAJ TZY FY IF
3431709-assignment-3.pdf
Binary file