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