class Algorithmable::Graphs::Traversals::BreadthFirst
Public Class Methods
new(graph, source)
click to toggle source
# 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
Public Instance Methods
path_to(vertex)
click to toggle source
# 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)
click to toggle source
# File lib/algorithmable/graphs/traversals/breadth_first.rb, line 16 def visited?(vertex) @visited[vertex] end
Private Instance Methods
traverse(graph, vertex)
click to toggle source
# File lib/algorithmable/graphs/traversals/breadth_first.rb, line 34 def traverse(graph, vertex) queue = ::Queue.new @visited[vertex] = true queue.enq vertex until queue.empty? next_vertex = queue.deq graph.adjacency(next_vertex).each do |neighbour_vertex| next if visited? neighbour_vertex @edge_to[neighbour_vertex] = next_vertex @visited[neighbour_vertex] = true queue.enq neighbour_vertex end end end