Class: ShortestPath::Map

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(source) ⇒ Map

Returns a new instance of Map.



9
10
11
12
 
# File 'lib/shortest_path/map.rb', line 9

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

Instance Attribute Details

#max_distance ⇒ Object

Returns the value of attribute max_distance.



7
8
9
 
# File 'lib/shortest_path/map.rb', line 7

def max_distance
  @max_distance
end

#source ⇒ Object (readonly)

Returns the value of attribute source.



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

def source
  @source
end

#ways_finder ⇒ Object

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



16
17
18
 
# File 'lib/shortest_path/map.rb', line 16

def ways_finder
  @ways_finder
end

Instance Method Details

#follow_way?(node, destination, weight) ⇒ Boolean

Returns:

  • (Boolean) 


76
77
78
 
# File 'lib/shortest_path/map.rb', line 76

def follow_way?(node, destination, weight)
  max_distance.nil? or shortest_distances[node] + weight <= max_distance
end

#map ⇒ Object 



42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
# File 'lib/shortest_path/map.rb', line 42

def map
  @shortest_distances = {}
  @previous = {}

  pq = ::FastContainers::PriorityQueue.new(:min)

  pq.push(source, 0)
  visit source
  shortest_distances[source] = 0

  while !pq.empty?
    v = pq.pop
    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

  shortest_distances
end

#previous ⇒ Object 



26
27
28
 
# File 'lib/shortest_path/map.rb', line 26

def previous
  @previous ||= {}
end

#search_heuristic(node) ⇒ Object 



30
31
32
 
# File 'lib/shortest_path/map.rb', line 30

def search_heuristic(node)
  shortest_distances[node]
end

#shortest_distances ⇒ Object 



22
23
24
 
# File 'lib/shortest_path/map.rb', line 22

def shortest_distances
  @shortest_distances ||= {}
end

#visit(node) ⇒ Object 



38
39
40
 
# File 'lib/shortest_path/map.rb', line 38

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

#visited?(node) ⇒ Boolean

Returns:

  • (Boolean) 


34
35
36
 
# File 'lib/shortest_path/map.rb', line 34

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

#ways(node) ⇒ Object 



18
19
20
 
# File 'lib/shortest_path/map.rb', line 18

def ways(node)
  ways_finder.call node
end