class Ogr::BreadthFirstSearch

Class implements Breadth First Search in graphs

Attributes

colors[RW]
distance[R]
graph[RW]
parents[R]
to_visit[RW]
visited[R]

Public Class Methods

new(graph) click to toggle source
# File lib/ogr/breadth_first_search.rb, line 6
def initialize(graph)
  @graph = graph
  @colors = Hash.new(:white)
  @parents = {}
  @visited = []
  @distance = Hash.new(Float::INFINITY)
  @to_visit = SimpleQueue.new
end

Public Instance Methods

Private Instance Methods

visit_neighbors(u) click to toggle source
# File lib/ogr/breadth_first_search.rb, line 39
def visit_neighbors(u)
  graph.neighbors(u).each do |v|
    visit_node(v, u) unless visited?(v)
  end
end
visit_node(v, from) click to toggle source
# File lib/ogr/breadth_first_search.rb, line 45
def visit_node(v, from)
  colors[v] = :grey
  parents[v] = from
  distance[v] = distance[from] + 1
  to_visit.enqueue v
end
visit_source(s) { |v| ... } click to toggle source
# File lib/ogr/breadth_first_search.rb, line 28
def visit_source(s)
  distance[s] = 0
  to_visit.enqueue s
  until to_visit.empty?
    v = to_visit.dequeue
    visit_neighbors(v)
    colors[v] = :black
    visited << (block_given? ? yield(v) : v)
  end
end
visited?(v) click to toggle source
# File lib/ogr/breadth_first_search.rb, line 52
def visited?(v)
  colors[v] != :white
end