class Mementus::BreadthFirstSearch

Public Class Methods

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

Public Instance Methods

each(&block) click to toggle source
# File lib/mementus/breadth_first_search.rb, line 11
def each(&block)
  visit(@start_id, &block)
end

Private Instance Methods

visit(id, &block) click to toggle source
# File lib/mementus/breadth_first_search.rb, line 17
def visit(id, &block)
  @queue << @graph.node(id)

  while next_node = @queue.shift
    next if @visited[next_node]

    @visited[next_node] = true
    block.call(next_node)
    @queue.concat(@graph.outgoing(next_node.id))
  end
end