DCI Example: Dijkstra


#!/usr/bin/env ruby
# 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 Distance_labeled_graph_node 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; return (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
    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(n); @name = n 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 differnce between
        # object equality and identity
        return 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
#



class ManhattanGeometry
    def initialize; end
    

    # 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.


    
    def east_neighbor_of(a); return nil end
    def south_neighbor_of(a); return nil end
    
    def root; return nil end
    def destination; return nil end
    def nodes; return @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
    
    def pathTo; @pathTo end
    def east_neighbor; @east_neighbor end
    def south_neighbor; @south_neighbor end
    def path; @path end
    def map; @map end
    def current; @current end
    def destination; @destination end
    def tentative_distance_values; @tentative_distance_values end
    
    # 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
    
    def unvisited; @unvisited end

    

    # Initialization


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

            # All nodes play the role of Distance_labeled_graph_node. 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.

            |node| node.extend Distance_labeled_graph_node
        }
        
        @east_neighbor = map.east_neighbor_of(origin_node)
        if east_neighbor != nil
            east_neighbor.extend EastNeighbor
        end
        
        @south_neighbor = map.south_neighbor_of(origin_node)
        if south_neighbor != nil
            south_neighbor.extend SouthNeighbor
        end

    end
    

    # 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, pathto_hash = nil,
              tentative_distance_values_hash = nil)
        @destination = target_node
        
        rebind(origin_node, geometries)
        
        execute(path_vector, unvisited_hash, pathto_hash, tentative_distance_values_hash)
    end


    # There are eight roles in the algorithm:
    #
    # pathTo, 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 Distance_labeled_graph_node
    

        # 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
            retval = Array.new
            if south_neighbor != nil
                if unvisited[south_neighbor] == true; retval << south_neighbor end
            end
            if east_neighbor != nil
                if unvisited[east_neighbor] == true; retval << east_neighbor end
            end
            return retval
        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; self.set_tentative_distance_to(x);
                return :distance_was_udated
            else return :distance_was_not_udated end
        end
    end
    
    module SouthNeighbor
        include ContextAccessor
        
        def relable_node_as(x)
            if x < self.tentative_distance; self.set_tentative_distance_to(x);
                return :distance_was_udated
            else return :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)
            return @distances[Edge.new(a, b)]
        end
        
        def origin; return 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 {
                |intersection|
                if unvisited[intersection]
                    if intersection.tentative_distance < min
                        min = intersection.tentative_distance
                        selection = intersection
                    end
                end
            }
            return selection
        end
    end
    
    
    def do_inits(path_vector, unvisited_hash, pathto_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 = Hash.new
        

            # 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 = Hash.new
            

            # 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 = Array.new
            

            # The pathTo 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

            @pathTo = Hash.new

        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
            @pathTo = pathto_hash
        end
    end
    
    

    # This is the method that starts the work. Called from initialize.

    def execute(path_vector, unvisited_hash, pathto_hash, tentative_distance_values_hash)
        execute_in_context do
            do_inits(path_vector, unvisited_hash, pathto_hash,
                tentative_distance_values_hash)

            # Calculate tentative distances of unvisited neighbors

            unvisited_neighbors = current.unvisited_neighbors

            if unvisited_neighbors != nil
                unvisited_neighbors.each {
                    |neighbor|
                    net_distance = current.tentative_distance +
                        map.distance_between(current, neighbor)
                    if neighbor.relable_node_as(net_distance) == :distance_was_udated
                        pathTo[neighbor] = current
                    end
                }
            end
            unvisited.delete(current)
            

            # Are we done?

            if map.unvisited.size == 0
                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,
                   pathTo, tentative_distance_values)
            end
        end
    end
    
    
    def each
        path.each { |node| yield node }
    end
    

    # This method does a simple traversal of the data structures (following pathTo)
    # to build the directed traversal vector for the minimum path

    def save_path(pathVector)
        node = destination
        begin
            pathVector << node
            node = pathTo[node]
        end while node != nil
    end

end

# This is the main Context for shortest distance calculation


class CalculateShortestDistance
    include ContextAccessor

    def tentative_distance_values; @tentative_distance_values end
    def path; @path end
    def map; @map end
    def current; @current end
    def destination; @destination 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 Distance_labeled_graph_node
    

        # 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
    
    def rebind(origin_node, geometries)
        @current = origin_node
        @destination = geometries.destination
        @map = geometries
        map.extend Map
        map.nodes.each {
            |node|
            node.extend Distance_labeled_graph_node
        }
    end
    
    def initialize(origin_node, target_node, geometries)
        rebind(origin_node, geometries)
        @tentative_distance_values = Hash.new
    end
    
    def distance
        execute_in_context do
            @current.set_tentative_distance_to(0)
            @path = CalculateShortestPath.new(current, destination, map).path
            retval = 0
            previous_node = nil
            path.reverse_each {
                |node|
                if previous_node.nil?
                    retval = 0
                else
                    retval += map.distance_between(previous_node, node)
                end
                previous_node = node
            }
            return retval
        end
    end
end


#
# --- Here are some test data
#


class ManhattanGeometry1 < ManhattanGeometry
    def initialize
        super()
        @nodes = Array.new
        @distances = Hash.new
        
        names = [ "a", "b", "c", "d", "a", "b", "g", "h", "i"]

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

        # 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
        #


        @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]
    
        9.times { |i|
            9.times { |j|
                @distances[Edge.new(@nodes[i], @nodes[j])] = infinity
            }
        }

        @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 = Hash.new
        @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; return @a end
    def destination; return @i end
end


class ManhattanGeometry2 < ManhattanGeometry
    def initialize
        super()
        @nodes = Array.new
        @distances = Hash.new
        
        names = [ "a", "b", "c", "d", "a", "b", "g", "h", "i", "j", "k"]

        11.times { |j| @nodes << Node.new(names[j]) }

        # 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]
    
        11.times { |i|
            11.times { |j|
                @distances[Edge.new(@nodes[i], @nodes[j])] = infinity
            }
        }

        @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 = Hash.new
        @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 = 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[@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; return @a end
    def destination; return @k end
end

#
# --- Main Program: test driver
#


geometries = ManhattanGeometry1.new
path = CalculateShortestPath.new(geometries.root, geometries.destination, geometries)
print "Path is: "
path.each {
    |node|
        print "#{node.name} "
};
print "\n"
puts "distance is #{CalculateShortestDistance.new(geometries.root, geometries.destination, geometries).distance}"

puts("")

geometries = ManhattanGeometry2.new
path = CalculateShortestPath.new(geometries.root, geometries.destination, geometries)
print "Path is: "
last_node = nil
path.each {
    |node|
        if last_node != nil; print " - #{geometries.distance_between(node, last_node)} - " end
        print "#{node.name}"
        last_node = node
};
print "\n"
puts "distance is #{CalculateShortestDistance.new(geometries.root, geometries.destination, geometries).distance}"