Class: ShortestPath::Finder

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(source, destination) ⇒ Finder

Returns a new instance of Finder.



8
9
10
11
 
# File 'lib/shortest_path/finder.rb', line 8

def initialize(source, destination)
  @source, @destination = source, destination
  @visited = {}
end

Instance Attribute Details

#begin_at ⇒ Object (readonly)

Returns the value of attribute begin_at.



51
52
53
 
# File 'lib/shortest_path/finder.rb', line 51

def begin_at
  @begin_at
end

#destination ⇒ Object (readonly)

Returns the value of attribute destination.



6
7
8
 
# File 'lib/shortest_path/finder.rb', line 6

def destination
  @destination
end

#end_at ⇒ Object (readonly)

Returns the value of attribute end_at.



51
52
53
 
# File 'lib/shortest_path/finder.rb', line 51

def end_at
  @end_at
end

#source ⇒ Object (readonly)

Returns the value of attribute source.



6
7
8
 
# File 'lib/shortest_path/finder.rb', line 6

def source
  @source
end

#timeout ⇒ Object

timeout is in seconds



50
51
52
 
# File 'lib/shortest_path/finder.rb', line 50

def timeout
  @timeout
end

#ways_finder ⇒ Object

Should return a map with accessible nodes and associated weight Example : { :a => 2, :b => 3 }



15
16
17
 
# File 'lib/shortest_path/finder.rb', line 15

def ways_finder
  @ways_finder
end

Instance Method Details

#context ⇒ Object

each node is related to an hash defining the context context is specific to the path solution between departure dans target node



37
38
39
 
# File 'lib/shortest_path/finder.rb', line 37

def context
  @context ||= {}
end

#duration ⇒ Object 



57
58
59
60
 
# File 'lib/shortest_path/finder.rb', line 57

def duration
  return nil unless begin_at
  (end_at or Time.now) - begin_at
end

#follow_way?(node, destination, weight, context = {}) ⇒ Boolean

Returns:

  • (Boolean) 


45
46
47
 
# File 'lib/shortest_path/finder.rb', line 45

def follow_way?(node, destination, weight, context={})
  true
end

#found?(node) ⇒ Boolean

Returns:

  • (Boolean) 


70
71
72
 
# File 'lib/shortest_path/finder.rb', line 70

def found?(node)
  node == destination      
end

#path_with_cache ⇒ Object Also known as: path

@end_at = Time.now

not_found ? [] : sorted_array

end



158
159
160
 
# File 'lib/shortest_path/finder.rb', line 158

def path_with_cache
  @path ||= path_without_cache
end

#path_without_cache ⇒ Object 



74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
# File 'lib/shortest_path/finder.rb', line 74

def path_without_cache
  @begin_at = Time.now
  
  pq = ::FastContainers::PriorityQueue.new(:min)
  # PQueue.new do |x,y| 
  #   search_heuristic(x) < search_heuristic(y)
  # end
  pq.push(source, 0)
  visit source
  shortest_distances[source] = 0

  not_found = !found?(source)

  while pq.size != 0 && not_found
    raise TimeoutError if timeout?

    v = pq.pop
    not_found = !found?(v)
    visit v

    weights = ways(v)

    if weights
      weights.keys.each do |w|
        w_distance = shortest_distances[v] + weights[w]
        
        if !visited?(w) and
            weights[w] and
            ( shortest_distances[w].nil? || shortest_distances[w] > w_distance) and 
            follow_way?(v, w, weights[w])
          shortest_distances[w] = w_distance
          previous[w] = v
          pq.push(w, search_heuristic(w) )
        end
      end
    end
  end

  @end_at = Time.now
  #puts previous.inspect
  not_found ? [] : sorted_array
end

#previous ⇒ Object 



29
30
31
 
# File 'lib/shortest_path/finder.rb', line 29

def previous
  @previous ||= {}
end

#refresh_context(node, context) ⇒ Object 



17
18
19
 
# File 'lib/shortest_path/finder.rb', line 17

def refresh_context( node, context)
  {}
end

#search_heuristic(node) ⇒ Object 



41
42
43
 
# File 'lib/shortest_path/finder.rb', line 41

def search_heuristic(node)
  shortest_distances[node]
end

#shortest_distances ⇒ Object 



25
26
27
 
# File 'lib/shortest_path/finder.rb', line 25

def shortest_distances
  @shortest_distances ||= {}
end

#sorted_array ⇒ Object 



163
164
165
166
167
168
169
170
171
172
173
 
# File 'lib/shortest_path/finder.rb', line 163

def sorted_array
  [].tap do |sorted_array|
    previous_id = destination
    previous.size.times do |t|
      sorted_array.unshift(previous_id)
      break if previous_id == source
      previous_id = previous[previous_id]
      raise "Unknown #{previous_id.inspect}" unless previous_id
    end
  end
end

#timeout? ⇒ Boolean

Returns:

  • (Boolean) 


53
54
55
 
# File 'lib/shortest_path/finder.rb', line 53

def timeout?
  timeout and (duration > timeout)
end

#visit(node) ⇒ Object 



66
67
68
 
# File 'lib/shortest_path/finder.rb', line 66

def visit(node)
  @visited[node] = true
end

#visited?(node) ⇒ Boolean

Returns:

  • (Boolean) 


62
63
64
 
# File 'lib/shortest_path/finder.rb', line 62

def visited?(node)
  @visited[node]
end

#ways(node, context = {}) ⇒ Object 



21
22
23
 
# File 'lib/shortest_path/finder.rb', line 21

def ways(node, context={})
  ways_finder.call node
end