Skip to content

Instantly share code, notes, and snippets.

@solutus
Last active Jun 21, 2019
Embed
What would you like to do?
# usage BfsTraverse.call(order) { |order| order.related_orders }
# usage BfsTraverse.call(order) { |order| order.related_orders }
class BfsTraverse
def call(element, &adjacents_proc)
node = Node.new(element, &adjacents_proc)
BreadthFirstSearch.new(node).to_a.map(&:element)
end
class Node
attr_reader :element
def initialize(element, &adjacents_proc)
@element = element
@adjacents_proc = adjacents_proc
end
def adjacents
@adjacents_proc.call(@element).map { |element| Node.new(element, &@adjacents_proc) }
end
def ==(other)
@element == other.element
end
def hash
@element.hash
end
end
class BreadthFirstSearch
def initialize(node)
@node = node
@visited = []
@edge_to = {}
bfs(node)
end
def to_a
@visited
end
private
# https://raw.githubusercontent.com/brianstorti/ruby-graph-algorithms/master/breadth_first_search/breadth_first_search.rb
def bfs(node)
# Remember, in the breadth first search we always
# use a queue. In ruby we can represent both
# queues and stacks as an Array, just by using
# the correct methods to deal with it. In this case,
# we use the "shift" method to remove an element
# from the beginning of the Array.
# First step: Put the source node into a queue and mark it as visited
queue = []
queue << node
@visited << node
# Second step: Repeat until the queue is empty:
# - Remove the least recently added node n
# - add each of n's unvisited adjacents to the queue and mark them as visited
while queue.any?
current_node = queue.shift # remove first element
current_node.adjacents.each do |adjacent_node|
next if @visited.include?(adjacent_node)
queue << adjacent_node
@visited << adjacent_node
@edge_to[adjacent_node] = current_node
end
end
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment