Class: Ogr::BreadthFirstSearch

Inherits:
Object
  • Object
show all
Defined in:
lib/ogr/breadth_first_search.rb

Overview

Class implements Breadth First Search in graphs

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(graph) ⇒ BreadthFirstSearch 



6
7
8
9
10
11
12
13
 
# 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

Instance Attribute Details

#distance ⇒ Object (readonly)

Returns the value of attribute distance.



4
5
6
 
# File 'lib/ogr/breadth_first_search.rb', line 4

def distance
  @distance
end

#parents ⇒ Object (readonly)

Returns the value of attribute parents.



4
5
6
 
# File 'lib/ogr/breadth_first_search.rb', line 4

def parents
  @parents
end

#visited ⇒ Object (readonly)

Returns the value of attribute visited.



4
5
6
 
# File 'lib/ogr/breadth_first_search.rb', line 4

def visited
  @visited
end

Instance Method Details

#search(source = nil, &block) ⇒ Object 



15
16
17
18
19
20
21
22
 
# 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