Class: Ogr::DepthFirstSearch

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

Overview

Class implements Breadth First Search in graphs

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(graph) ⇒ DepthFirstSearch

Returns a new instance of DepthFirstSearch.



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

def initialize(graph)
  @graph = graph
  @parents = {}
  @marked = {}
  @visited = []
  @distance = {}
end

Instance Attribute Details

#distance ⇒ Object

Returns the value of attribute distance.



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

def distance
  @distance
end

#marked ⇒ Object

Returns the value of attribute marked.



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

def marked
  @marked
end

#parents ⇒ Object

Returns the value of attribute parents.



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

def parents
  @parents
end

#visited ⇒ Object

Returns the value of attribute visited.



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

def visited
  @visited
end

Instance Method Details

#dfs(v, from = nil, &block) ⇒ Object 



21
22
23
24
25
26
27
28
 
# File 'lib/ogr/graphs/depth_first_search.rb', line 21

def dfs(v, from = nil, &block)
  marked[v] = true
  visited << (block_given? ? yield(v) : v)
  parents[v] = from
  graph.neighbors(v).reverse_each do |u|
    dfs(u, v, &block) unless marked[u]
  end
end

#search(u, &block) ⇒ Object 



15
16
17
18
19
 
# File 'lib/ogr/graphs/depth_first_search.rb', line 15

def search(u, &block)
  reset!
  dfs(u, &block)
  visited
end