Class: Algorithmable::Graphs::Traversals::BreadthFirst

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

Constant Summary

Constants included from Errors

Errors::TraversalError, Errors::UnvisitedVertexError

Instance Method Summary collapse

Constructor Details

#initialize(graph, source) ⇒ BreadthFirst 



8
9
10
11
12
13
14
 
# File 'lib/algorithmable/graphs/traversals/breadth_first.rb', line 8

def initialize(graph, source)
  vertices_size = graph.vertices.size
  @visited = Array.new(vertices_size - 1)
  @edge_to = Array.new(vertices_size - 1)
  @source = source
  traverse graph, source
end

Instance Method Details

#path_to(vertex) ⇒ Object 



20
21
22
23
24
25
26
27
28
29
30
 
# File 'lib/algorithmable/graphs/traversals/breadth_first.rb', line 20

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 



16
17
18
 
# File 'lib/algorithmable/graphs/traversals/breadth_first.rb', line 16

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