class Trainworks::GraphAlgorithm

GraphAlgorithm is used to calculate direct distances, shortest path and other paths between nodes. It assumes graph is a hash of adjacencies of a directed-positively-weighted-possibly-cyclic-graph @example Example of a graph

'A' => { 'B' => 5 },
'B' => { 'C' => 5 },
'C' => { 'B' => 4 }

Public Class Methods

new(graph) click to toggle source
# File lib/trainworks/graph_algorithm.rb, line 14
def initialize(graph)
  @graph = graph
end

Public Instance Methods

distance(cities) click to toggle source

@param [Array] cities is a set of nodes @return [Number] the distance traveled from city to city in cities @return [String] “NO SUCH ROUTE” when one of the citis is not connected to another @example

algorithm.distance(['A', 'B', 'C']) => 10
# File lib/trainworks/graph_algorithm.rb, line 23
def distance(cities)
  distance = 0
  begin
    cities.each_cons(2) do |(from, to)|
      distance += go(from: from, to: to)
    end
  rescue NoSuchRoute => e
    distance = e.to_s
  end

  distance
end
shortest_distance(from:, to:) click to toggle source

@param [Object] from the starting point @param [Object] to the goal @return [Number] the shortest distance from `from` to `to` @see GraphAlgorithm#trips trips @raise NoSuchRoute It calls {trips} to find all paths between the starting point and the goal and returns the shortest distance found. If there's no path between `from` and `to` it raises {NoSuchRoute}

# File lib/trainworks/graph_algorithm.rb, line 114
def shortest_distance(from:, to:)
  shortest_distance = trips(from: from, to: to).values.min
  raise NoSuchRoute if shortest_distance.nil?
  shortest_distance
end
trips(from:, to:, current_distance: 0, current_path: [from], all_paths: {}) click to toggle source

@param [Object] from the starting point @param [Object] to the goal @return [Hash] all possible trips from the starting point to the goal without repeating loops

# File lib/trainworks/graph_algorithm.rb, line 90
def trips(from:, to:, current_distance: 0, current_path: [from], all_paths: {})
  routes(from).map do |city, _paths|
    next_current_path = [*current_path, city]
    next_current_distance = current_distance + go(from: from, to: city)
    all_paths[next_current_path] = next_current_distance if arrived?(city, to)
    next if arrived?(city, to) || already_visited?(next_current_path, city)
    trips(
      from: city,
      to: to,
      current_distance: next_current_distance,
      current_path: next_current_path,
      all_paths: all_paths
    )
  end
  all_paths
end
trips_with_exact_stops(from:, to:, stops:) click to toggle source

@param [Object] from the starting point @param [Object] to the goal @param [Number] stops the maximum number of stops between from and to the algorithm is allowed to travel @return [Array<Array>] all possible trips from the starting point to the goal with maximum stops equal to `stops` @see GraphAlgorithm#trips_with_max_stops trips_with_max_stops it calls {trips_with_max_stops} and filter out the trips that don't have the exact number of stops as `stops`

# File lib/trainworks/graph_algorithm.rb, line 56
def trips_with_exact_stops(from:, to:, stops:)
  total_path_size = stops + 1 # a path includes the stops plus the origin
  trips_with_max_stops(from: from, to: to, stops: stops).select do |path|
    path.size == total_path_size
  end
end
trips_with_max_distance(from:, to:, max_distance:, total_paths: [from], solutions: {}, current_distance: 0) click to toggle source

@param [Object] from the starting point @param [Object] to the goal @param [Number] max_distance the maximum distance between from and to the algorithm is allowed to travel @return [Array<Array>] all trips from the starting point to the goal with maximum stops equal to `max_distance` Since we calculate the distance by adding up the distances between the nodes, the edges must have positive distances otherwise it's not garateed the algorithm will reach a stop.

# File lib/trainworks/graph_algorithm.rb, line 69
def trips_with_max_distance(from:, to:, max_distance:, total_paths: [from], solutions: {}, current_distance: 0)
  routes(from).map do |city, _paths|
    next_current_distance = current_distance + go(from: from, to: city)
    return solutions.keys if next_current_distance >= max_distance
    next_total_paths = [*total_paths, city]
    solutions[next_total_paths] = next_current_distance if arrived?(city, to)
    trips_with_max_distance(
      from: city,
      to: to,
      max_distance: max_distance,
      total_paths: next_total_paths,
      solutions: solutions,
      current_distance: next_current_distance
    )
  end
  solutions.keys
end
trips_with_max_stops(from:, to:, stops:, total_paths: [from], solutions: []) click to toggle source

@param [Object] from the starting point @param [Object] to the goal @param [Number] stops the maximum number of stops between from and to the algorithm is allowed to travel @return [Array<Array>] all possible trips from the starting point to the goal with maximum stops equal to `stops`

# File lib/trainworks/graph_algorithm.rb, line 40
def trips_with_max_stops(from:, to:, stops:, total_paths: [from], solutions: [])
  routes(from).map do |city, _paths|
    return solutions if 0 >= stops
    next_total_paths = [*total_paths, city]
    solutions.push(next_total_paths) if arrived?(city, to)
    trips_with_max_stops(from: city, to: to, stops: stops - 1, total_paths: next_total_paths, solutions: solutions)
  end
  solutions
end

Private Instance Methods

already_visited?(path, current_city) click to toggle source

if the current_city can be found more than one time in the path it means we already visited it.

# File lib/trainworks/graph_algorithm.rb, line 135
def already_visited?(path, current_city)
  path.count(current_city) > 1
end
arrived?(current, goal) click to toggle source
# File lib/trainworks/graph_algorithm.rb, line 129
def arrived?(current, goal)
  current == goal
end
go(from:, to:) click to toggle source

these are helper methods to deal with finding keys in the graph an its value in case of not finding the keys (`from` and `to`) it raises `NoSuchRoute`

# File lib/trainworks/graph_algorithm.rb, line 141
def go(from:, to:)
  routes(from).fetch(to) { raise NoSuchRoute }
end
routes(city) click to toggle source
# File lib/trainworks/graph_algorithm.rb, line 145
def routes(city)
  @graph.fetch(city) { raise NoSuchRoute }
end