class Apsp::ShortestPath
Public Class Methods
shortest_path(from, to)
click to toggle source
# File lib/apsp.rb, line 6 def self.shortest_path(from, to) @form = form @path = 0 @from_id = from.id.to_i @to_id = to.id.to_i if (from.id != @to_id) from = @form.class.find(@from_id) @hash_to_push = {} @visiting_queue = [] @path = [] @hash_to_push[@from_id.to_s] = 0 @visiting_queue << @from_id find_path(from) if @success create_path(@to_id) @path.reverse! return @path else false end end end
Public Instance Methods
create_path(key)
click to toggle source
# File lib/apsp.rb, line 52 def create_path(key) @path << @form.class.find(key).name if key == @from_id return else create_path(@hash_to_push[key.to_s]) end end
find_path(check_station)
click to toggle source
# File lib/apsp.rb, line 29 def find_path(check_station) # p "@hash_to_push", @hash_to_push # p "@visiting_queue", @visiting_queue check_station.connections.each do|s| if s.connect_id == @to_id @hash_to_push[s.connect_id.to_s] = check_station.id @success = true return elsif !@hash_to_push.has_key?(s.connect_id.to_s) @hash_to_push[s.connect_id.to_s] = check_station.id @visiting_queue << s.connect_id end end @visiting_queue.shift if @visiting_queue.length>0 find_path(@form.class.find(@visiting_queue[0])) else @success = false return end end