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