Class: Apsp::ShortestPath

Inherits:
Object
  • Object
show all
Defined in:
lib/apsp.rb

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

.shortest_path(from, to) ⇒ Object 



6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
# 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

Instance Method Details

#create_path(key) ⇒ Object 



52
53
54
55
56
57
58
59
 
# 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) ⇒ Object 



29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
# 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