Finds the shortest path in a graph, allowing unusual cost definitions
Ruby
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
lib
spec
.gitignore
.rspec
.travis.yml
Gemfile
Guardfile
LICENSE
README.md
Rakefile
cruise_config.rb
routr.gemspec

README.md

Routr

Build Status

Implements Dijkstra's algorithm to find the shortest path in a graph.

The cost of an edge can be more general than just a numeric value. You can inject a method for calculating the distance from source to the next node given the distance from source to the current node and the properties of an edge. A possible use case is the one used by PeerPost: nodes are people, an edge is a connection between specifying when those people regularly meet, you inject a method that calculates when people meet next after a specified time.

Usage

class MyInterface
  NETWORK = {
    'A' => { 'B' => 50, 'C' => 100 },
    'B' => { 'D' => 50 },
    'C' => { 'D' => 10 },
    'D' => {}
  }

  # This will be used if :initial_distance is not supplied to calculate_route
  def initial_distance
    0
  end

  def neighbours_of(node_key)
    NETWORK[node_key].keys
  end

  def calculate_new_distance(distance_so_far, a_key, b_key)
    distance_so_far + NETWORK[a_key][b_key]
  end
end

route = Routr.new(MyInterface.new).calculate_route(
  :from => 'A',
  :to => 'D',
  :initial_distance => 0
)

route.hops.count       # => 2
route.members.count    # => 3

route.hops.first.from     # => 'A' 
route.hops.first.to       # => 'B' 
route.hops.first.distance # => 50
route.hops.last.from      # => 'B' 
route.hops.last.to        # => 'D' 
route.hops.last.distance  # => 100

route.members.first      # => 'A'
route.members.last       # => 'D'

route.distance   # => 100

If you have normal addible edge costs, you can replace the calculate_new_distance method with edge_distance:

def edge_cost(a_key, b_key)
    NETWORK[a_key][b_key]
  end

License

Copyright 2012, Levente Bagi

Released under the MIT License, see the LICENSE file.