class RoutePlanner
Constants
- Infinity
Public Class Methods
new(graph_info)
click to toggle source
# File lib/route_planner.rb, line 6 def initialize(graph_info) @graph = { } graph_info.scan(/\w\w\d+/).each do |x| start = x[0,1] finish = x[1,1] @graph[start] ||= { } @graph[start][finish] = x[2..-1].to_i end end
Public Instance Methods
distance(path)
click to toggle source
Determines the distance between two points (towns). Returns nil if no path is available.
# File lib/route_planner.rb, line 18 def distance(path) dist = 0 path.each_char.map.inject do |prev, cur| return nil unless @graph[prev][cur] dist += @graph[prev][cur] cur end dist end
shortest_distance(start, finish)
click to toggle source
# File lib/route_planner.rb, line 36 def shortest_distance(start, finish) all_nodes = @graph.each.map { |k,v| [k, v.keys] }.flatten.uniq dist = { } all_nodes.each { |x| dist[x] = Infinity } dist[start] = 0 if start == finish then all_nodes.delete(start) dist[start] = Infinity @graph[start].each { |nxt, how_far| dist[nxt] = how_far } end while not all_nodes.empty? do min_node = all_nodes.min { |a,b| dist[a] <=> dist[b] } if !min_node || min_node == Infinity return nil end all_nodes.delete(min_node) @graph[min_node].each_key do |v| alt = dist[min_node] + (@graph[min_node][v] || Infinity) dist[v] = alt if dist[v] && alt < dist[v] end end return nil if dist[finish] == Infinity dist[finish] end
trips_number(start, finish, opts = { })
click to toggle source
Number of possible trips between two points (towns)
# File lib/route_planner.rb, line 29 def trips_number(start, finish, opts = { }) opts = { :min_stops => 1, :max_stops => Infinity, :max_distance => Infinity }.merge(opts) total = 0 explore_routes(start, finish, opts) { total += 1} total end
Private Instance Methods
explore_routes(start, finish, opts, stats = {:distance => 0, :stops => 0}, &callback)
click to toggle source
Traverses the graph until maximum stops or distance is reached.
# File lib/route_planner.rb, line 67 def explore_routes(start, finish, opts, stats = {:distance => 0, :stops => 0}, &callback) lower_bound_ok = stats[:stops] >= opts[:min_stops] upper_bound_ok = stats[:distance] <= opts[:max_distance] && stats[:stops] <= opts[:max_stops] callback.call(stats[:path]) if start == finish && lower_bound_ok && upper_bound_ok # Recursion basis: stop exploration when reached upper-bound restrictions if upper_bound_ok @graph[start].each do |nxt, dist| inner_stats = {:distance => stats[:distance] + dist, :stops => stats[:stops] + 1} explore_routes(nxt, finish, opts, inner_stats, &callback) end end end