class Ogr::DepthFirstSearch
Class implements Depth First Search in graphs
Attributes
graph[R]
marked[R]
stack[R]
visited[R]
Public Class Methods
new(graph)
click to toggle source
# File lib/ogr/depth_first_search.rb, line 7 def initialize(graph) @graph = graph @marked = {} @visited = [] end
Public Instance Methods
search(source = nil, &block)
click to toggle source
# 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
Private Instance Methods
dfs(v, &block)
click to toggle source
# File lib/ogr/depth_first_search.rb, line 24 def dfs(v, &block) @stack = [v] while u = stack.pop visit(u, &block) end end
visit(v) { |v| ... }
click to toggle source
# File lib/ogr/depth_first_search.rb, line 31 def visit(v) return if marked[v] visited << (block_given? ? yield(v) : v) marked[v] = true stack.concat(graph.neighbors(v)) end