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