Code spike to see if joins can be modelled using a DAG

dm_query_graph.rb

require 'set'
require 'tsort'

module DataMapper
  class Query
    class Graph
      include TSort

      def initialize
        @graph   = Hash.new { |graph, target| graph[target] = Set.new }
        @aliases = {}
      end

      def name_for(node)
        @aliases.fetch(node, node.name)
      end

      def each_node(&block)
        tsort_each(&block)
        self
      end

      def each_edge(&block)
        each_node { |node| @graph[node].each(&block) }
      end

      def add_edge(source, target, key)
        @graph[target] << Edge.new(source, target, key)
        add_alias(target)
        self
      end

      def to_hash
        @graph.dup
      end

    private

      def tsort_each_node
        @graph.sort_by { |_, edges| edges.size }.each do |(node, _)|
          yield node
        end
      end

      def tsort_each_child(node)
        @graph[node].each { |edge| yield edge.source }
      end

      def add_alias(node)
        @aliases[node] ||= "#{node.name}_#{@graph[node].size}"
      end

      class Node
        attr_reader :name, :conditions

        def initialize(name, conditions = {})
          @name       = name.to_str
          @conditions = conditions.to_hash
        end

        def ==(other)
          name == other.name && conditions == other.conditions
        end

        def eql?(other)
          instance_of?(other.class) && self == other
        end

        def hash
          name.hash ^ conditions.hash
        end
      end # class Node

      class Edge
        attr_reader :source, :target, :join

        def initialize(source, target, join = {})
          @source = source
          @target = target
          @join   = join.to_hash
        end

        def ==(other)
          source == other.source &&
          target == other.target &&
          join   == other.join
        end

        def eql?(other)
          instance_of?(other.class) && self == other
        end

        def hash
          source.hash ^ target.hash ^ join.hash
        end
      end # class Edge

    end # class Graph
  end # class Query
end # module DataMapper

include DataMapper

graph = Query::Graph.new

customer    = Query::Graph::Node.new('customers')
order       = Query::Graph::Node.new('orders')
order_lines = Query::Graph::Node.new('order_lines')
items       = Query::Graph::Node.new('items')
affiliate   = Query::Graph::Node.new('affiliate')
shipment    = Query::Graph::Node.new('shipment')

graph.add_edge(customer,    order,       :id           => :customer_id)
graph.add_edge(order,       order_lines, :id           => :order_id)
graph.add_edge(order_lines, items,       :item_id      => :id)
graph.add_edge(customer,    affiliate,   :affiliate_id => :id)
graph.add_edge(customer,    affiliate,   :affiliate_id => :id)  # duplicate
graph.add_edge(order,       shipment,    :id           => :order_id)

graph.each_edge do |edge|
  puts "#{graph.name_for(edge.source)} -> #{graph.name_for(edge.target)}"
end