class DFS

Public Class Methods

new(graph, source) click to toggle source
# File lib/rbutils/graph/dfs.rb, line 4
def initialize(graph, source)
  @graph = graph
  @source = source
  @visited = []
  @edge_to = {}

  #perform dfs
  dfs(source)
end

Public Instance Methods

dfs(node) click to toggle source
# File lib/rbutils/graph/dfs.rb, line 14
def dfs(node)
  #mark node as visited
  @visited << node
  
  #take each adjacent node
  node.adjacents.each do |adj|
    next if @visited.include?(adj)
    #perform dfs
    dfs(adj)
    #check edges
    @edge_to[adj] = node
  end
end
path_to(node) click to toggle source
# File lib/rbutils/graph/dfs.rb, line 28
def path_to(node)
  return unless @visited.include?(node)
  path = []
  curr = node
  
  #get the paths from the specified node to the
  #source
  while(curr != @source) do
    path.unshift(curr)
    curr = @edge_to[curr]
  end
  path.unshift(@source)
end