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
search(source = nil, &block)
click to toggle source
# File lib/ogr/breadth_first_search.rb, line 15 def search(source = nil, &block) if source visit_source(source, &block) else graph.each_vertex { |v| visit_source(v, &block) unless visited?(v) } end visited end
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