node_spec.rb

class Node
  def initialize(name, parents = [])
    @name, @parents = name, parents
  end

  attr_reader :name, :parents

  def root?
    parents.empty?
  end

  def paths(path = [self])
    root? ? [path] : parents.inject([]) {|acc, p| acc + p.paths([p] + path) }
  end
end

describe Node do
  def have_paths(*expect)
    simple_matcher("have paths: #{expect.inspect}") do |node|
      node.paths.map {|p| p.map(&:name) } == expect
    end
  end

  context 'linear' do
    before do
      @n1 = Node.new(:n1)
      @n2 = Node.new(:n2, [@n1])
      @n3 = Node.new(:n3, [@n2])
    end

    it { @n1.should have_paths([:n1]) }
    it { @n2.should have_paths([:n1, :n2]) }
    it { @n3.should have_paths([:n1, :n2, :n3]) }
  end

  context 'branch and merge' do
    before do
      @n1 = Node.new(:n1)
      @n2 = Node.new(:n2, [@n1])
      @n3 = Node.new(:n3, [@n1])
      @n4 = Node.new(:n4, [@n2, @n3])
    end

    it { @n1.should have_paths([:n1]) }
    it { @n2.should have_paths([:n1, :n2]) }
    it { @n3.should have_paths([:n1, :n3]) }
    it { @n4.should have_paths([:n1, :n2, :n4], [:n1, :n3, :n4]) }
  end

  context 'branch and merge (complex)' do
    before do
      @n1 = Node.new(:n1)
      @n2 = Node.new(:n2, [@n1])
      @n3 = Node.new(:n3, [@n1])
      @n4 = Node.new(:n4, [@n2, @n3])
      @n5 = Node.new(:n5, [@n3])
      @n6 = Node.new(:n6, [@n4, @n5])
    end

    it { @n6.should have_paths([:n1, :n2, :n4, :n6], [:n1, :n3, :n4, :n6], [:n1, :n3, :n5, :n6]) }
  end
end