class Algorithmable::Graphs::Traversals::DepthFirst

Public Class Methods

new(graph, source) click to toggle source
# File lib/algorithmable/graphs/traversals/depth_first.rb, line 7
def initialize(graph, source)
  @visited = []
  @edge_to = []
  @source = source
  traverse graph, source
end

Public Instance Methods

path_to(vertex) click to toggle source
# File lib/algorithmable/graphs/traversals/depth_first.rb, line 18
def path_to(vertex)
  fail UnvisitedVertexError, vertex unless visited?(vertex)
  path = []
  finish = vertex
  while finish != @source
    path.push finish
    finish = @edge_to[finish]
  end
  path.push @source
  path
end
visited?(vertex) click to toggle source
# File lib/algorithmable/graphs/traversals/depth_first.rb, line 14
def visited?(vertex)
  @visited[vertex]
end

Private Instance Methods

traverse(graph, vertex) click to toggle source
# File lib/algorithmable/graphs/traversals/depth_first.rb, line 32
def traverse(graph, vertex)
  @visited[vertex] = true
  graph.adjacency(vertex).each do |neighbour_vertex|
    unless visited? neighbour_vertex
      @edge_to[neighbour_vertex] = vertex
      traverse graph, neighbour_vertex
    end
  end
end