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

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