Module: HasShortestPath

Extended by:
ActiveSupport::Concern
Defined in:
lib/has_shortest_path.rb,
lib/has_shortest_path/version.rb

Defined Under Namespace

Modules: ClassMethods

Constant Summary collapse

Infinity = 
1.0/0
VERSION = 
"0.0.1"

Instance Method Summary collapse

Instance Method Details

#shortest_path(final_destination, options = {}) ⇒ Object

shortest_path returns an array of intermediate edges in between this edge and the destination (exclusive). The array is empty if there are no intermediate edges. The array is nil if there is no available path.

  • final_destination: The edge record to attempt to find the shortest path to.

  • options[:recompute]: If set to true, all intermediate work will be discarded.



43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
# File 'lib/has_shortest_path.rb', line 43

def shortest_path final_destination, options = {}
  self.reload && @shortest_path_cache = nil if options[:recompute]
  build_cache
  
  # 1. Build an adjacency matrix out of this model's relevent records
  @shortest_path_cache[:w_table] = gen_w_table unless @shortest_path_cache[:w_table].present?
  
  # 2. Perform Floyd's shortest path algorithm
  @shortest_path_cache[:p_table] = floyd(@shortest_path_cache[:w_table], @shortest_path_cache[:w_size]) unless @shortest_path_cache[:p_table].present?
  
  # 3. Attempt to reconstruct a path to final_destination
  # Only attempt reconstruction if final_destination is in the table!
  # If final_destination is in the table, there must be a path, otherwise it would not have
  # been included by traverse_all_edges
  final_index = index_from_edge(final_destination)
  if(final_index < @shortest_path_cache[:w_size] && final_index != nil) then
    reconstruct_path(index_from_edge(self), final_index, @shortest_path_cache[:p_table])
  else
    nil
  end
end