bellman ford search


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

Source Code

-- Bellman Ford single source shortest path search algorithm implementation
-- See : https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

-- Notes : this is a generic implementation of Bellman Ford search algorithm.
-- It is devised to be used on waypoint graphs.
-- The BellmanFord class expects a handler to be initialized. Roughly said, the handler
-- is an interface between your graph and the search algorithm.
-- The passed-in handler should implement those functions.
-- handler.getNode(...)    -> returns a Node (instance of node.lua)
-- handler.getAllNodes()   -> returns an array list of all nodes in the graph
-- handler.getAllEdges()   -> returns an array list of all edges in the graph

-- See utils/graph.lua for reference

-- The generic Node class provided (see utils/node.lua) should also be implemented
-- through the handler. Basically, it should describe how nodes are labelled
-- and tested for equality for a custom search space.
-- The following functions should be implemented:
-- function Node:initialize(...) -> creates a Node with custom attributes
-- function Node:toString()      -> returns a unique string representation of
--                                  the node, for debug purposes

-- Dependencies
local class = require 'utils.class'

-- Clears nodes data between consecutive path requests.
local function resetForNextSearch(bellmanford)
  local nodes = bellmanford.handler.getAllNodes()
  for _, node in pairs(nodes) do
    node.parent = nil
    node.distance = math.huge
  end
end

-- Builds and returns the path to the goal node
local function backtrace(node)
  local path = {}
  repeat
    table.insert(path, 1, node)
    node = node.parent
  until not node
  return path
end

-- Initializes Bellman Ford search with a custom handler
local BellmanFord = class()
function BellmanFord:initialize(handler)
  self.handler = handler
end

-- Processes the graph for shortest paths
-- source : the starting node from which the search will spread.
-- target : the goal node
--   When done, the shortest path from one node to another can easily 
--   backtraced by indexing the parent field of a node. 
-- Return : if target supplied, returns the shortest path from source 
--   to target.
function BellmanFord:process(source, target)
  resetForNextSearch(self)
  source.distance = 0
  local nodes = self.handler.getAllNodes()
  local edges = self.handler.getAllEdges()

  -- Relaxing all edges |V| - 1 times
  for i = 1, #nodes - 1 do
    for i, edge in ipairs(edges) do
      local u, v, w = edge.from, edge.to, edge.weight
      local tempDistance = u.distance + w
      if tempDistance < v.distance then
        v.distance, v.parent = tempDistance, u
      end
    end
  end

  -- Checking for negative cycles
  for i, edge in ipairs(edges) do
    local u, v, w = edge.from, edge.to, edge.weight
    local tempDistance = u.distance + w
    assert(tempDistance >= v.distance, 'Negative cycle found!')
  end
  
  if target then return backtrace(target) end
end

return BellmanFord
-- Tests for dijkstra.lua
local BellmanFord = require 'bellmanford'

local total, pass = 0, 0

local function dec(str, len)
  return #str < len
     and str .. (('.'):rep(len-#str))
      or str:sub(1,len)
end

local function same(t, p, comp)
  for k,v in ipairs(t) do
    if not comp(v, p[k]) then return false end
  end
  return true
end

local function run(message, f)
  total = total + 1
  local ok, err = pcall(f)
  if ok then pass = pass + 1 end
  local status = ok and 'PASSED' or 'FAILED'
  print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

run('Testing Bellman Ford', function()
  local comp = function(a, b) return a.x == b[1] and a.y == b[2] end
  local graph = require 'utils.graph'

  graph.addNode('A')
  graph.addNode('B')
  graph.addNode('C')
  graph.addNode('D')
  graph.addNode('E')
  graph.addEdge('A','B',-1)
  graph.addEdge('A','C',4)
  graph.addEdge('B','C',3)
  graph.addEdge('B','D',2)
  graph.addEdge('D','B',1)
  graph.addEdge('D','C',5)
  graph.addEdge('B','E',2)
  graph.addEdge('E','D',-3)

  local bf = BellmanFord(graph)
  local nodeA = graph.getNode('A')
  local nodeD = graph.getNode('D')
  local pathAtoD = bf:process(nodeA, nodeD)

  assert(graph.getNode('A').distance,  0)
  assert(graph.getNode('B').distance, -1)
  assert(graph.getNode('C').distance,  2)
  assert(graph.getNode('D').distance, -2)
  assert(graph.getNode('E').distance,  1)

  assert(pathAtoD[1], graph.getNode('A'))
  assert(pathAtoD[2], graph.getNode('B'))
  assert(pathAtoD[3], graph.getNode('E'))
  assert(pathAtoD[4], graph.getNode('D'))
end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
  :format(total, pass, total-pass, (pass*100/total)))