Class: Mormon::OSM::Algorithm::Random

Inherits:
Base
  • Object
show all
Defined in:
lib/mormon/osm_router.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(router, options = {}) ⇒ Random

Returns a new instance of Random.



102
103
104
105
 
# File 'lib/mormon/osm_router.rb', line 102

def initialize(router, options = {})
  super
  @breadth = options[:breadth] || 2
end

Instance Attribute Details

#breadth ⇒ Object

Returns the value of attribute breadth.



100
101
102
 
# File 'lib/mormon/osm_router.rb', line 100

def breadth
  @breadth
end

Instance Method Details

#enqueue(node_start, node_end, transport, current_route, visited, max_amplitude) ⇒ Object 



113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
# File 'lib/mormon/osm_router.rb', line 113

def enqueue(node_start, node_end, transport, current_route, visited, max_amplitude)
  current_route ||= []
  visited       ||= []

  if node_start == node_end
    @queue << current_route.dup
  else
    visited << node_start
    neighbors = @router.loader.routing[transport][node_start.to_s]

    if neighbors
      neighbors   = neighbors.keys.map(&:to_i)
      not_visited = neighbors - (neighbors & visited)
      
      # random sort in order to not take the same order for neighbors every time.
      not_visited.sort_by { rand }.each do |neighbor|
        # limit the width of the route go further more than max_distance the distance between start and end
        next if distance(neighbor, node_end) > max_amplitude 
        current_route << neighbor
        enqueue neighbor, node_end, transport, current_route, visited, max_amplitude
        current_route.delete neighbor
      end
    end
    
    visited.delete node_start
  end
end

#route(node_start, node_end, transport) ⇒ Object 



107
108
109
110
111
 
# File 'lib/mormon/osm_router.rb', line 107

def route(node_start, node_end, transport)
  max_amplitude = @breadth * distance(node_start, node_end)
  enqueue node_start, node_end, transport, [node_start], [], max_amplitude
  @queue.any? ? ["success", @queue[rand(@queue.size-1)]] : ["no_route", []]
end