Graph algorithm sample

# frozen_string_literal: true

# blah blah blah
class Node
  attr_reader :name
  attr_accessor :edges

  def initialize(name)
    @name = name
    @edges = []
  end

  def add_edge(node)
    edges.push(node)
  end
end

class Graph
end

require 'set'

def dep_resolve(node, resolved, unresolved = Set.new)
  puts node.name
  unresolved.add(node)
  node.edges.each do |edge|
    unless resolved.include?(edge)
      if unresolved.include?(edge)
        raise StandardError, "circular reference detected: #{node.name} -> #{edge.name}"
      end
      dep_resolve(edge, resolved, unresolved)
    end
  end
  resolved.push(node)
  unresolved.delete(node)
end

resolved = []
a = Node.new('a')
b = Node.new('b')
c = Node.new('c')
d = Node.new('d')
e = Node.new('e')

a.add_edge(b)    # a depends on b
a.add_edge(d)    # a depends on d
b.add_edge(c)    # b depends on c
b.add_edge(e)    # b depends on e
c.add_edge(d)    # c depends on d
c.add_edge(e)    # c depends on e
d.add_edge(b)

pp a
puts

dep_resolve(a, resolved)

p resolved.map(&:name)