Class: Algorithmable::Graphs::Traversals::DepthFirst

Inherits:
Object
  • Object
show all
Includes:
Errors
Defined in:
lib/algorithmable/graphs/traversals/depth_first.rb

Constant Summary

Constants included from Errors

Errors::TraversalError, Errors::UnvisitedVertexError

Instance Method Summary collapse

Constructor Details

#initialize(graph, source) ⇒ DepthFirst

Returns a new instance of DepthFirst.



7
8
9
10
11
12
 
# File 'lib/algorithmable/graphs/traversals/depth_first.rb', line 7

def initialize(graph, source)
  @visited = []
  @edge_to = []
  @source = source
  traverse graph, source
end

Instance Method Details

#path_to(vertex) ⇒ Object 



18
19
20
21
22
23
24
25
26
27
28
 
# 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) ⇒ Boolean

Returns:

  • (Boolean) 


14
15
16
 
# File 'lib/algorithmable/graphs/traversals/depth_first.rb', line 14

def visited?(vertex)
  @visited[vertex]
end