Class: Trainworks::GraphAlgorithm

Inherits:
Object
  • Object
show all
Defined in:
lib/trainworks/graph_algorithm.rb

Overview

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

Examples:

Example of a graph

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

Defined Under Namespace

Classes: NoSuchRoute

Instance Method Summary collapse

Constructor Details

#initialize(graph) ⇒ GraphAlgorithm

Returns a new instance of GraphAlgorithm.



14
15
16
 
# File 'lib/trainworks/graph_algorithm.rb', line 14

def initialize(graph)
  @graph = graph
end

Instance Method Details

#distance(cities) ⇒ Number, String

Examples:

algorithm.distance(['A', 'B', 'C']) => 10

Parameters:

  • cities (Array) —

    is a set of nodes

Returns:

  • (Number) —

    the distance traveled from city to city in cities

  • (String) —

    "NO SUCH ROUTE" when one of the citis is not connected to another



23
24
25
26
27
28
29
30
31
32
33
34
 
# 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:) ⇒ Number

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

Parameters:

  • from (Object) —

    the starting point

  • to (Object) —

    the goal

Returns:

  • (Number) —

    the shortest distance from from to to

Raises:

  • NoSuchRoute

See Also:



114
115
116
117
118
 
# 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: {}) ⇒ Hash

Returns all possible trips from the starting point to the goal without repeating loops.

Parameters:

  • from (Object) —

    the starting point

  • to (Object) —

    the goal

Returns:

  • (Hash) —

    all possible trips from the starting point to the goal without repeating loops



90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
 
# 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:) ⇒ Array<Array>

it calls #trips_with_max_stops and filter out the trips that don't have the exact number of stops as stops

Parameters:

  • from (Object) —

    the starting point

  • to (Object) —

    the goal

  • stops (Number) —

    the maximum number of stops between from and to the algorithm is allowed to travel

Returns:

  • (Array<Array>) —

    all possible trips from the starting point to the goal with maximum stops equal to stops

See Also:



56
57
58
59
60
61
 
# 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) ⇒ Array<Array>

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.

Parameters:

  • from (Object) —

    the starting point

  • to (Object) —

    the goal

  • max_distance (Number) —

    the maximum distance between from and to the algorithm is allowed to travel

Returns:

  • (Array<Array>) —

    all trips from the starting point to the goal with maximum stops equal to max_distance



69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
# 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: []) ⇒ Array<Array>

Returns all possible trips from the starting point to the goal with maximum stops equal to stops.

Parameters:

  • from (Object) —

    the starting point

  • to (Object) —

    the goal

  • stops (Number) —

    the maximum number of stops between from and to the algorithm is allowed to travel

Returns:

  • (Array<Array>) —

    all possible trips from the starting point to the goal with maximum stops equal to stops



40
41
42
43
44
45
46
47
48
 
# 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