A quick adjacency list demo for a gantt chart.

adjacency_list.rb

Edge = Struct.new(:parent, :child, :attributes)

class AdjacencyList

  include Enumerable

  attr_reader :list
  attr_accessor :nodes

  def initialize
    @list = []
    @nodes = []
  end

  def each
    @list.each {|e| yield e}
  end

  def add(parent, child, attributes=nil)
    edge = Edge.new(parent, child, attributes)
    add_edge(edge)
  end

  def remove(parent, child, attributes=nil)
    edge = Edge.new(parent, child, attributes)
    remove_edge(edge)
  end

  def add_edge(edge)
    list << edge
    self.nodes |= [edge.parent, edge.child]
    true
  end

  # FIXME: conditionally prune the node list or don't remove edges
  def remove_edge
    list.delete(edge)
  end

  def find_parents(node)
    select {|e| e.child == node}.map {|e| e.parent }
  end

  def find_children(node)
    select {|e| e.parent == node}.map {|e| e.child }
  end

  # Use this to assemble a Gantt Chart
  def dfs(node)
    on_deck = find_children(node)
    output = [node]
    until on_deck.empty?
      node = on_deck.shift
      on_deck.unshift(*find_children(node))
      output << node
    end
    output
  end

  def inspect
    "Adjacency List (#{nodes.size} nodes)"
  end

end

usage.rb

a = AdjacencyList.new # => Adjacency List (0 nodes)
a.add :a, :b          # => true
a.add :a, :c          # => true
a.add :b, :d          # => true
a                     # => Adjacency List (4 nodes)
a.dfs :a              # => [:a, :b, :d, :c]