Module: DijkstraFast

Defined in:
lib/dijkstra_fast.rb,
lib/dijkstra_fast/graph.rb,
lib/dijkstra_fast/version.rb,
lib/dijkstra_fast/shortest_path.rb,
lib/dijkstra_fast/no_path_exists_error.rb

Overview

When graph nodes "know" which nodes they are connected to, one of the two class methods on this module can be be used directly to calculate the shortest distance between nodes. Node objects must implement a method (by default connections) which yields all connected nodes and (optionally) the distance to that connected node. If the yield only supplies the connected node, a defualt distance of 1 is used.

It is important to ensure that hash and eql? are properly implemented so that two objects that are logically the same are treatest thusly.

Examples:


class SomethingWithConnections
  def find_next
    yield SomethingWithConnections.new('C'), 2
    yield SomethingWithConnections.new('D'), 4
  end

  def hash
    # implement me
  end

  def eql?(other)
    # implement me
  end
end

a = SomethingWithConnections.new('A')
b = SomethingWithConnections.new('B')
distance, path = DijkstraFast.shortest_path(a, b, connections: :find_next)

class SomethingElseWithConnections
  def connections
    yield # implement me
    yield # implement me
  end
end

a = SomethingElseWithConnections.new
b = SomethingElseWithConnections.new
distance = DijkstraFast.shortest_distance(a, b)

Defined Under Namespace

Modules: ShortestPath Classes: Graph, NoPathExistsError

Constant Summary collapse

VERSION =

Current gem version

'1.5.3'

Class Method Summary collapse

Class Method Details

.shortest_distance(source, dest, connections: 'connections', progress: false) ⇒ int

Finds the shortest distance between items

Parameters:

  • source (Object) —

    Any Ruby object that represents the source item

  • dest (Object) —

    Any Ruby object that represents the destination item

  • progress (Boolean|String|Proc) (defaults to: false) —

    If falsey (default), no progress will be displayed. If a Proc is given, it will be yielded progress (completed / total) as progress is made. If otherwise truthy the ruby-progressbar gem will be required and displayed; if passed a String it will be used as the progress bar's format.

  • connections (Symbol|String) (defaults to: 'connections') —

    The method to call on each item to obtain adjacent items in the graph.

Returns:

  • (int) 


86
87
88
 
# File 'lib/dijkstra_fast.rb', line 86

def self.shortest_distance(source, dest, connections: 'connections', progress: false)
  shortest_path(source, dest, connections: connections, progress: progress).first
end

.shortest_path(source, dest, connections: 'connections', progress: false) ⇒ Array<int, Array>

Finds the shortest path between items, returning both the path as well as the total distance travelled.

Parameters:

  • source (Object) —

    Any Ruby object that represents the source item

  • dest (Object) —

    Any Ruby object that represents the destination item

  • progress (Boolean|String|Proc) (defaults to: false) —

    If falsey (default), no progress will be displayed. If a Proc is given, it will be yielded progress (completed / total) as progress is made. If otherwise truthy the ruby-progressbar gem will be required and displayed; if passed a String it will be used as the progress bar's format.

  • connections (Symbol|String) (defaults to: 'connections') —

    The method to call on each item to obtain adjacent items in the graph. Defaults to 'connections'

Returns:

  • (Array<int, Array>) 


67
68
69
70
71
72
73
 
# File 'lib/dijkstra_fast.rb', line 67

def self.shortest_path(source, dest, connections: 'connections', progress: false)
  clazz = Class.new { include DijkstraFast::ShortestPath }
  clazz.define_method(:connections) do |source, &block|
    source.send(connections, &block)
  end
  clazz.new.shortest_path(source, dest, progress: progress)
end