class Mementus::DepthFirstSearch

Public Class Methods

new(graph, start_id, method=:out) click to toggle source
# File lib/mementus/depth_first_search.rb, line 3
def initialize(graph, start_id, method=:out)
  @graph = graph
  @start_id = start_id
  @method = method
  @visited = { @start_id => true }
end

Public Instance Methods

each(&block) click to toggle source
# File lib/mementus/depth_first_search.rb, line 10
def each(&block)
  visit(@graph.node(@start_id), &block)
end

Private Instance Methods

visit(node, &block) click to toggle source
# File lib/mementus/depth_first_search.rb, line 16
def visit(node, &block)
  block.call(node)
  @visited[node.id] = true

  method = case @method
    when :out then :outgoing
    when :in then :incoming
  end

  @graph.send(method, node.id).each do |adj_node|
    next if @visited[adj_node.id]
    visit(adj_node, &block)
  end
end