Dijkstra's algorithm in DCI -- Example in Ruby

dijkstras_dci.rb

#!/usr/bin/env ruby
#
######################################################################################################################################
# Taken here http://fulloo.info/Examples/RubyExamples/Dijkstra/DijkstraListing.html and carefully corrected to be more ruby idiomatic.
######################################################################################################################################
#
# Example in Ruby -- Dijkstra's algorithm in DCI
#    Modified and simplified for a Manhattan geometry with 8 roles
#
#
#
# Demonstrates an example where:
#
#    - objects of class Node play several roles simultaneously
#      (albeit spread across Contexts: a Node can
#      play the CurrentIntersection in one Context and an Eastern or
#      Southern Neighbor in another)
#    - stacked Contexts (to implement recursion)
#     - mixed access of objects of Node through different
#      paths of role elaboration (the root is just a node,
#      whereas others play roles)
#    - there is a significant pre-existing data structure called
#      a Geometry (plays the Map role) which contains the objects
#      of instance. Where DCI comes in is to ascribe roles to those
#      objects and let them interact with each other to evaluate the
#      minimal path through the network
#    - true to core DCI we are almost always concerned about
#      what happens between the objects (paths and distance)
#      rather than in the objects themselves (which have
#      relatively uninteresting properties like "name")
#    - equality of nodes is not identity, and several
#      nodes compare equal with each other by standard
#      equality (eql?)
#    - returns references to the original data objects
#      in a vector, to describe the resulting path
#
# There are some curiosities
#
#    - east_neighbor and south_neighbor were typographically equivalent,
#      so I folded them into a single role: Neighbor. That type still
#      serves the two original roles
#    - Roles are truly scoped to the use case context
#    - The Map and DistanceLabeledGraphNode roles have to be
#      duplicated in two Contexts. blah blah blah
#    - Node inheritance is replaced by injecting two roles
#       into the object
#    - Injecting roles no longer adds new fields to existing
#       data objects.
#    - There is an intentional call to distance_between while the
#       Context is still extant, but outside the scope of the
#       Context itself. Should that be legal?
#    - I have added a tentative_distance_values array to the Context
#       to support the algorithm. Its data are shared across the
#       roles of the CalculateShortestPath Context
#    - nearest_unvisited_node_to_target is now a feature of Map,
#       which seems to reflect better coupling than in the old
#       design

# Global boilerplate

def infinity
  2**(0.size * 8 -2) -1
end

module ContextAccessor
  def context
    Thread.current[:context]
  end

  def context=(ctx)
    Thread.current[:context] = ctx
  end

  def execute_in_context
    old_context = self.context
    self.context = self
    yield
  ensure
    self.context = old_context
  end
end

#
# Consider street corners on a Manhattan grid. We want to find the
# minimal path from the most northeast city to the most
# southeast city. Use Dijstra's algorithm
#

# Data classes

Edge = Struct.new :from, :to

class Node
  attr_reader :name

  def initialize(name)
    @name = name
  end

  def eql?(another_node)
    # Nodes are == equal if they have the same name. This is explicitly
    # defined here to call out the importance of the difference between
    # object equality and identity
    name == another_node.name
  end

  def ==(another_node)
    # Equality used in the Map algorithms is object identity
    super
  end
end

#
# --- Geometry is the interface to the data class that has all
# --- the information about the map. This is kind of silly in Ruby
#

# In the domain model we have a general model of streets and avenues. The notions of
# an east and south neighbor are not part of the domain model, but are germane to
# the Dijkstra problem. Though they evaluate to the same thing we use different
# names to reflect these two different (mental) models of Manhattan streets.
class ManhattanGeometry
  def east_neighbor_of(a) end
  def south_neighbor_of(a) end
  def root; end
  def destination; end
  def nodes; @nodes end
end

#
# --------- Contexts: the home of the use cases for the example --------------
#

#
# ---------- This is the main Context for shortest path calculation -----------
#

class CalculateShortestPath
  # Housekeeping crap

  include ContextAccessor

  # These are handles to to the roles
  attr_reader :path_to, :east_neighbor, :south_neighbor, :path, :map,
              :current, :destination, :tentative_distance_values,
              # This is a shortcut to information that really belongs in the Map.
              # To keep roles stateless, we hold the Map's unvisited structure in the
              # Context object. We access it as though it were in the map
              :unvisited

  # Public initialize. It's overloaded so that the public version doesn't
  # have to pass a lot of crap; the initialize method takes care of
  # setting up internal data structures on the first invocation. On
  # recursion we override the defaults
  def initialize(origin_node, target_node, geometries, path_vector = nil, unvisited_hash = nil, path_to_hash = nil,
    tentative_distance_values_hash = nil)
    @destination = target_node

    rebind origin_node, geometries

    execute path_vector, unvisited_hash, path_to_hash, tentative_distance_values_hash
  end

  # This is the method that starts the work. Called from initialize.
  def execute(path_vector, unvisited_hash, path_to_hash, tentative_distance_values_hash)
    execute_in_context do
      do_inits path_vector, unvisited_hash, path_to_hash, tentative_distance_values_hash

      # Calculate tentative distances of unvisited neighbors
      unvisited_neighbors = current.unvisited_neighbors

      unless unvisited_neighbors.nil?
        unvisited_neighbors.each do |neighbor|
          net_distance = current.tentative_distance + map.distance_between(current, neighbor)
          if neighbor.relable_node_as(net_distance) == :distance_was_udated
            path_to[neighbor] = current
          end
        end
      end
      unvisited.delete current

      # Are we done?
      if map.unvisited.empty?
        save_path(@path)
      else
        # The next current node is the one with the least distance in the
        # unvisited set
        selection = map.nearest_unvisited_node_to_target

        # Recur
        CalculateShortestPath.new selection, destination, map, path, unvisited,
                                  path_to, tentative_distance_values
      end
    end
  end

  def each
    path.each { |node| yield node }
  end

  private

  def rebind(origin_node, geometries)
    @current = origin_node
    @map = geometries
    @map.extend Map
    @current.extend CurrentIntersection

    # All nodes play the role of DistanceLabeledGraphNode. This is not a
    # canonical DCI role, since a proper DCI role designates a unique object
    # in any context. This is a role in the sense of Child being a role, and
    # in a given Context I want to address all the children in the room at once.
    # It works fine as a methodful role, less obviously fine as a methodless
    # role.
    geometries.nodes.each do |node|
      node.extend DistanceLabeledGraphNode
    end

    @east_neighbor = map.east_neighbor_of origin_node
    @east_neighbor.extend EastNeighbor if @east_neighbor

    @south_neighbor = map.south_neighbor_of(origin_node)
    @south_neighbor.extend SouthNeighbor if @south_neighbor
  end

  def do_inits(path_vector, unvisited_hash, path_to_hash, tentative_distance_values_hash)
    # The conditional switches between the first and subsequent instances of the
    # recursion (the algorithm is recursive in graph contexts)

    if path_vector.nil?
      # Since path_vector isn't set up, this is the first iteration of the recursion
      @tentative_distance_values = {}

      # This is the fundamental data structure for Dijkstra's algorithm, called
      # "Q" in the Wikipedia description. It is a boolean hash that maps a
      # node onto false or true according to whether it has been visited
      @unvisited = {}

      # These initializations are directly from the description of the algorithm
      map.nodes.each { |node| @unvisited[node] = true }
      unvisited.delete map.origin
      map.nodes.each { |node| node.set_tentative_distance_to infinity }
      map.origin.set_tentative_distance_to 0

      # The path array is kept in the outermost context and serves to store the
      # return path. Each recurring context may add something to the array along
      # the way. However, because of the nature of the algorithm, individual
      # Context instances don't deliver "partial paths" as partial answers.
      @path = []

      # The path_to map is a local associative array that remembers the
      # arrows between nodes through the array and erases them if we
      # re-label a node with a shorter distance
      @path_to = {}
    else
      # We are recurring. Just copy the values copied in from the previous iteration
      # of the recursion
      @tentative_distance_values = tentative_distance_values_hash
      @unvisited = unvisited_hash
      @path = path_vector
      @path_to = path_to_hash
    end
  end

  # This method does a simple traversal of the data structures (following path_to)
  # to build the directed traversal vector for the minimum path
  def save_path(path_vector)
    node = destination
    begin
      path_vector << node
      node = path_to[node]
    end while node
  end

  # There are eight roles in the algorithm:
  #
  # path_to, which is the interface to whatever accumulates the path
  # current, which is the current intersection in the recursive algorithm
  # east_neighbor, which lies DIRECTLY to the east of current
  # south_neighbor, which is DIRECTLy to its south
  # destination, the target node
  # map, which is the oracle for the geometry
  # tentative_distance_values, which supports the algorithm, and is
  # owned by the CalculateShortestPath context (it is context data)
  #
  #
  # The algorithm is straight from Wikipedia:
  #
  # http://en.wikipedia.org/wiki/Dijkstra's_algorithm
  #
  # and reads directly from the distance method, below

  module DistanceLabeledGraphNode
    # Access to roles and other Context data

    include ContextAccessor

    def tentative_distance_values
      context.tentative_distance_values
    end

    # Role Methods

    def tentative_distance
      tentative_distance_values[self]
    end

    def set_tentative_distance_to(x)
      tentative_distance_values[self] = x
    end
  end

  module CurrentIntersection

    # Access to roles and other Context data

    include ContextAccessor

    def unvisited
      context.map.unvisited
    end

    def south_neighbor
      context.south_neighbor
    end

    def east_neighbor
      context.east_neighbor
    end

    # Role Methods

    def unvisited_neighbors
      [].tap do |result|
        result << south_neighbor if unvisited[south_neighbor]
        result << east_neighbor if unvisited[east_neighbor]
      end
    end
  end

  # This module serves to provide the methods both for the
  # east_neighbor and south_neighbor roles
  module EastNeighbor
    include ContextAccessor

    def relable_node_as(x)
      if x < self.tentative_distance
        set_tentative_distance_to x
        :distance_was_udated
      else
        :distance_was_not_udated
      end
    end
  end

  module SouthNeighbor
    include ContextAccessor

    def relable_node_as(x)
      if x < self.tentative_distance
        set_tentative_distance_to x
        :distance_was_udated
      else
        :distance_was_not_udated
      end
    end
  end

  # "Map" as in cartography rather than Computer Science...
  #
  # Map is a DCI role. The role in this example is played by an
  # object representing a particular Manhattan geometry
  module Map
    # Access to roles and other Context data

    include ContextAccessor

    # These data are physically in the Context. There used to be a bit
    # affixed to each node used in the Dijkstra algorithm, but that violated
    # the encapsulation of the node. Data classes should be able to be used
    # unmodified by the DCI framework — except for the addition of roles,
    # and it's important that roles be stateless. So we put the data in
    # the Context. However, it is logically associated with the Mpa: think
    # of putting a check mark on the map next to each node, as it is
    # visited. So we put the accessor for the univisted vector here

    def unvisited
      context.unvisited
    end

    # Role Methods

    def distance_between(a, b)
      @distances[Edge.new(a, b)]
    end

    def origin
      root
    end

    # These two functions presume always traveling
    # in a southern or easterly direction
    def next_down_the_street_from(x); east_neighbor_of x end
    def next_along_the_avenue_from(x); south_neighbor_of x end

    def nearest_unvisited_node_to_target
      min = infinity
      selection = nil
      unvisited.each_key do |intersection|
        if unvisited[intersection] && intersection.tentative_distance < min
          min = intersection.tentative_distance
          selection = intersection
        end
      end

      selection
    end
  end
end

# This is the main Context for shortest distance calculation
class CalculateShortestDistance
  include ContextAccessor

  attr_reader :tentative_distance_values, :path, :map, :current, :destination

  def initialize(origin_node, target_node, geometries)
    rebind origin_node, geometries
    @tentative_distance_values = {}
  end

  def distance
    execute_in_context do
      @current.set_tentative_distance_to 0
      @path = CalculateShortestPath.new(current, destination, map).path
      result = 0
      previous_node = nil
      path.reverse_each do |node|
        if previous_node.nil?
          result = 0
        else
          result += map.distance_between(previous_node, node)
        end
        previous_node = node
      end
      result
    end
  end

  private

  def rebind(origin_node, geometries)
    @current = origin_node
    @destination = geometries.destination
    @map = geometries
    map.extend Map
    map.nodes.each do |node|
      node.extend DistanceLabeledGraphNode
    end
  end

  module Map
    include ContextAccessor

    def distance_between(a, b)
      @distances[Edge.new(a, b)]
    end

    # These two functions presume always travelling
    # in a southern or easterly direction
    def next_down_the_street_from(x)
      east_neighbor_of x
    end

    def next_along_the_avenue_from(x)
      south_neighbor_of x
    end
  end

  module DistanceLabeledGraphNode
    # Access to roles and other Context data
    include ContextAccessor

    def tentative_distance_values
      context.tentative_distance_values
    end

    def tentative_distance
      tentative_distance_values[self]
    end

    def set_tentative_distance_to(x)
      tentative_distance_values[self] = x
    end
  end
end

if __FILE__ == $0

  #
  # --- Here are some test data
  #

  class ManhattanGeometry1 < ManhattanGeometry
    def initialize
      super

      @nodes, @distances = [], {}

      names = %w(a b c d a b g h i)

      3.times do |i|
        3.times do |j|
          @nodes << Node.new(names[(i*3)+j])
        end
      end

      # Aliases to help set up the grid. Grid is of Manhattan form:
      #
      #    a - 2 - b - 3 - c
      #    |       |       |
      #    1       2       1
      #    |       |       |
      #    d - 1 - e - 1 - f
      #    |               |
      #    2               4
      #    |               |
      #    g - 1 - h - 2 - i
      #

      %w(a b c d e f g h i).each_with_index do |name, index|
        instance_variable_set :"@#{name}", @nodes[index]
      end

      9.times do |i|
        9.times do |j|
          @distances[Edge.new(@nodes[i], @nodes[j])] = infinity
        end
      end

      @distances[Edge.new(@a, @b)] = 2
      @distances[Edge.new(@b, @c)] = 3
      @distances[Edge.new(@c, @f)] = 1
      @distances[Edge.new(@f, @i)] = 4
      @distances[Edge.new(@b, @e)] = 2
      @distances[Edge.new(@e, @f)] = 1
      @distances[Edge.new(@a, @d)] = 1
      @distances[Edge.new(@d, @g)] = 2
      @distances[Edge.new(@g, @h)] = 1
      @distances[Edge.new(@h, @i)] = 2
      @distances[Edge.new(@d, @e)] = 1
      @distances.freeze

      @next_down_the_street_from = {}
      @next_down_the_street_from[@a] = @b
      @next_down_the_street_from[@b] = @c
      @next_down_the_street_from[@d] = @e
      @next_down_the_street_from[@e] = @f
      @next_down_the_street_from[@g] = @h
      @next_down_the_street_from[@h] = @i
      @next_down_the_street_from.freeze

      @next_along_the_avenue_from = Hash.new
      @next_along_the_avenue_from[@a] = @d
      @next_along_the_avenue_from[@b] = @e
      @next_along_the_avenue_from[@c] = @f
      @next_along_the_avenue_from[@d] = @g
      @next_along_the_avenue_from[@f] = @i
      @next_along_the_avenue_from.freeze
    end

    def east_neighbor_of(a)
      @next_down_the_street_from[a]
    end

    def south_neighbor_of(a)
      @next_along_the_avenue_from[a]
    end

    def root; @a end
    def destination; @i end
  end

  class ManhattanGeometry2 < ManhattanGeometry
    def initialize
      super

      @nodes = %w(a b c d a b g h i j k).map { |name| Node.new name }

      # Aliases to help set up the grid. Grid is of Manhattan form:
      #
      #    a - 2 - b - 3 - c - 1 - j
      #    |       |       |       |
      #    1       2       1       |
      #    |       |       |       |
      #    d - 1 - e - 1 - f       1
      #    |               |       |
      #    2               4       |
      #    |               |       |
      #    g - 1 - h - 2 - i - 2 - k

      @a = @nodes[0]
      @b = @nodes[1]
      @c = @nodes[2]
      @d = @nodes[3]
      @e = @nodes[4]
      @f = @nodes[5]
      @g = @nodes[6]
      @h = @nodes[7]
      @i = @nodes[8]
      @j = @nodes[9]
      @k = @nodes[10]

      @distances = {}
      @nodes.each do |i|
        @nodes.each do |j|
          @distances[Edge.new(i, j)] = infinity
        end
      end

      @distances[Edge.new(@a, @b)] = 2
      @distances[Edge.new(@b, @c)] = 3
      @distances[Edge.new(@c, @f)] = 1
      @distances[Edge.new(@f, @i)] = 4
      @distances[Edge.new(@b, @e)] = 2
      @distances[Edge.new(@e, @f)] = 1
      @distances[Edge.new(@a, @d)] = 1
      @distances[Edge.new(@d, @g)] = 2
      @distances[Edge.new(@g, @h)] = 1
      @distances[Edge.new(@h, @i)] = 2
      @distances[Edge.new(@d, @e)] = 1
      @distances[Edge.new(@c, @j)] = 1
      @distances[Edge.new(@j, @k)] = 1
      @distances[Edge.new(@i, @k)] = 2
      @distances.freeze

      @next_down_the_street_from = {}
      @next_down_the_street_from[@a] = @b
      @next_down_the_street_from[@b] = @c
      @next_down_the_street_from[@c] = @j
      @next_down_the_street_from[@d] = @e
      @next_down_the_street_from[@e] = @f
      @next_down_the_street_from[@g] = @h
      @next_down_the_street_from[@h] = @i
      @next_down_the_street_from[@i] = @k
      @next_down_the_street_from.freeze

      @next_along_the_avenue_from = {}
      @next_along_the_avenue_from[@a] = @d
      @next_along_the_avenue_from[@b] = @e
      @next_along_the_avenue_from[@c] = @f
      @next_along_the_avenue_from[@d] = @g
      @next_along_the_avenue_from[@f] = @i
      @next_along_the_avenue_from[@j] = @k
      @next_along_the_avenue_from.freeze
    end

    def east_neighbor_of(a)
      @next_down_the_street_from[a]
    end

    def south_neighbor_of(a)
      @next_along_the_avenue_from[a]
    end

    def root
      @a
    end

    def destination
      @k
    end
  end

  require "test/unit"

  class TestManhattanGeometry < Test::Unit::TestCase

    def test_manhattan_geometries_1
      geometries = ManhattanGeometry1.new
      path = CalculateShortestPath.new(geometries.root, geometries.destination, geometries)
      names = []
      path.each { |node| names << node.name }

      assert_equal %w(i h g d a), names
      assert_equal 6, CalculateShortestDistance.new(geometries.root, geometries.destination, geometries).distance
    end

    def test_manhattan_geometries_2
      geometries = ManhattanGeometry2.new
      path = CalculateShortestPath.new(geometries.root, geometries.destination, geometries)
      actual = []
      current_node = nil
      path.each do |node|
        if current_node
          actual <<  geometries.distance_between(node, current_node)
        end
        actual << node.name
        current_node = node
      end
      assert_equal ["k", 1, "j", 1, "c", 3, "b", 2, "a"], actual

      assert_equal 7, CalculateShortestDistance.new(geometries.root, geometries.destination, geometries).distance
    end
  end
end