Module: DijkstraFast::ShortestPath

Included in:
Graph
Defined in:
lib/dijkstra_fast/shortest_path.rb

Overview

Interface to allow arbitrary classes to calculate the shortest path between two "items" using a native implementation of Dijkstra's algorithm.

Examples:


class GraphOne
  include DijkstraFast::ShortestPath

  def connections(source)
    source.find_next do |dest, distance|
      yield dest, distance
    end
  end
end

distance, path = GraphOne.new.shortest_path(source, dest)

class GraphTwo
  include DijkstraFast::ShortestPath

  def initialize
    # All edges have distance 1
    @edges = { 1 => [2, 3], 2 => [3] }
  end

  def connections(source, &block)
    @edges.fetch(source, []).each(&block)
  end
end

distance = GraphTwo.new.shortest_distance(source, dest)

class GraphThree
  include DijkstraFast::ShortestPath

  def connections(source)
    case source
    when 'A'
      yield 'B', 3
      yield 'C' # Default distance 1
    when 'B'
      yield 'C', 10
    end
  end
end

distance, path = GraphThree.new.shortest_path(source, dest)

See Also:

Instance Method Summary collapse

Instance Method Details

#connections(source) {|Object, int| ... } ⇒ nil

Returns the edges originating at source

Parameters:

  • source (Object) —

    Any Ruby object that represents the source item

Yields:

  • (Object, int) —

    A connection to destination object with given distance

Returns:

  • (nil) 


64
65
66
 
# File 'lib/dijkstra_fast/shortest_path.rb', line 64

def connections(source)
  # Does nothing by default but should be implemented by class
end

#shortest_distance(source, dest, 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.

Returns:

  • (int) 


91
92
93
 
# File 'lib/dijkstra_fast/shortest_path.rb', line 91

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

#shortest_path(source, dest, 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.

Returns:

  • (Array<int, Array>) 


78
79
80
 
# File 'lib/dijkstra_fast/shortest_path.rb', line 78

def shortest_path(source, dest, progress: false)
  Native.new(self).send(:shortest_path, source, dest, progress: progress)
end