Class: Ogr::BreadthFirstSearch

Inherits:
Object
  • Object
show all
Defined in:
lib/ogr/graphs/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

Returns a new instance of BreadthFirstSearch.



7
8
9
10
11
12
13
14
 
# File 'lib/ogr/graphs/breadth_first_search.rb', line 7

def initialize(graph)
  @graph = graph
  @colors = {}
  @parents = {}
  @visited = []
  @distance = {}
  @to_visit = SimpleQueue.new
end

Instance Attribute Details

#distance ⇒ Object

Returns the value of attribute distance.



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

def distance
  @distance
end

#parents ⇒ Object

Returns the value of attribute parents.



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

def parents
  @parents
end

#visited ⇒ Object

Returns the value of attribute visited.



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

def visited
  @visited
end

Instance Method Details

#search(s) ⇒ Object 



16
17
18
19
20
21
22
23
24
25
26
27
 
# File 'lib/ogr/graphs/breadth_first_search.rb', line 16

def search(s)
  # TODO: Check if source exists in graph
  reset!
  visit_source(s)
  until to_visit.empty?
    v = to_visit.dequeue
    visit_neighbors(v)
    colors[v] = :black
    visited << (block_given? ? yield(v) : v)
  end
  visited
end