Skip to content

Instantly share code, notes, and snippets.

@nazargulov

nazargulov/bfs.rb

Last active April 2, 2019 13:52
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save nazargulov/f7c94b62c7c96a3c5471 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save nazargulov/f7c94b62c7c96a3c5471 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
bfs.rb
# Put unvisited nodes on a queue
# Solves the shortest path problem: Find path from "source" to "target"
# that uses the fewest number of edges
# It's not recursive (like depth first search)
#
# The steps are quite simple:
# * Put s into a FIFO queue and mark it as visited
# * 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
class BreathFirstSearch
def initialize(graph, source_node, end_node, max_depth = 100, max = 1)
@graph = graph
@node = source_node
@end_node = end_node
@visited = []
@edge_to = {}
@edge1_to = {}
@depth = {}
@max_depth = (max_depth > 0) ? max_depth : 1000
@max_path = max
bfs1(source_node)
end
def shortest_path_to(node)
return unless has_path_to?(node)
path = []
while(node != @node) do
path.unshift(node) # unshift adds the node to the beginning of the array
node = @edge_to[node]
end
path.unshift(@node)
end
def path_to
paths = []
while(@edge1_to[@end_node].length > 0) do
node = @end_node
path = []
interrupted = false
last_path = true
while(node && node != @node) do
path.unshift(node)
node = if @edge1_to[node].length == 1
@edge1_to[node].last
else
last_path = false
@edge1_to[node].pop
end
interrupted = true unless node
end
break if interrupted
path.unshift(@node)
if path.uniq.length == path.length && !paths.include?(path)
paths << path
break if paths.length >= @max_path
end
break if last_path
end
paths.sort { |x, y| x.length <=> y.length }
end
private
def bfs(node)
# Remember, in the breath 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
def bfs1(node)
queue = []
queue << node
@depth[node] = 1
while queue.any?
current_node = queue.shift # remove first element
current_node.adjacents.each do |adjacent_node|
if @edge1_to[current_node] && @edge1_to[current_node].include?(adjacent_node)
next
end
@depth[adjacent_node] = @depth[current_node] + 1
queue << adjacent_node
push_edge(adjacent_node, current_node)
end
break if @depth[current_node] > @max_depth
end
end
def push_edge(adjacent_node, current_node)
@edge1_to[adjacent_node] = [] unless @edge1_to[adjacent_node]
@edge1_to[adjacent_node].unshift(current_node)
end
# If we visited the node, so there is a path
# from our source node to it.
def has_path_to?(node)
@visited.include?(node)
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment