Class: Ogr::DepthFirstSearch

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

Overview

Class implements Depth 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
 
# File 'lib/ogr/depth_first_search.rb', line 7

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

Instance Attribute Details

#visited ⇒ Object (readonly)

Returns the value of attribute visited.



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

def visited
  @visited
end

Instance Method Details

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



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

def search(source = nil, &block)
  if source
    dfs(source, &block)
  else
    graph.vertexes.each { |v| dfs(v, &block) unless marked[v] }
  end
  visited
end