Ozzypig

FloydWarshall

Feb 26th, 2018
330
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. -- FloydWarshall mixin for Graph class
  2. -- ModuleScript inside Graph ModuleScript
  3. -- by Ozzypig (Twitter: @Ozzypig, ozzypig.com)
  4.  
  5. -- Floyd-Warshall algorithm: shortest path between all nodes in a graph
  6. -- *    Runs in O(|V|^3) in best, worst and average cases
  7. -- *    assumes no negative cycles in a graph
  8.  
  9. local FloydWarshallMixin = {}
  10.  
  11. FloydWarshallMixin.pathsGenerated = false
  12. FloydWarshallMixin.nodeDist = nil
  13. FloydWarshallMixin.nodeNext = nil
  14.  
  15. function FloydWarshallMixin:floydWarshall()
  16.     local nodes = {}
  17.     for node in self:eachNode() do
  18.         table.insert(nodes, node)
  19.     end
  20.    
  21.     local edges = {}
  22.     for edge in self:eachEdge() do
  23.         table.insert(edges, edge)
  24.     end
  25.    
  26.     --print(("Flyod-Warshall Algorithm (Edges: %d, Vertices: %d)"):format(#edges, #nodes))
  27.    
  28.     -- |V|x|V| array of minimum distances from node i to j initialized to infinity
  29.     local nodeDist = {}
  30.     -- |V|x|V| array of vertex indices initialized to null
  31.     local nodeNext = {}
  32.     for i = 1, #nodes do
  33.         nodeDist[i] = {}
  34.         nodeNext[i] = {}
  35.         for j = 1, #nodes do
  36.             nodeDist[i][j] = math.huge
  37.             nodeNext[i][j] = nil -- redundant, but good for completeness
  38.         end
  39.     end
  40.    
  41.     -- initialize distances
  42.     for edge in self:eachEdge() do
  43.         local u, v = edge.origin.index, edge.target.index
  44.         nodeDist[u][v] = edge.value
  45.         nodeNext[u][v] = v
  46.     end
  47.    
  48.     -- the standard floyd-warshall implementation
  49.     local sum
  50.     for k = 1, #nodes do
  51.         for i = 1, #nodes do
  52.             for j = 1, #nodes do
  53.                 sum = nodeDist[i][k] + nodeDist[k][j]
  54.                 if nodeDist[i][j] > sum then
  55.                     nodeDist[i][j] = sum
  56.                     nodeNext[i][j] = nodeNext[i][k]
  57.                 end
  58.             end
  59.         end
  60.     end
  61.    
  62.     self.nodeDist = nodeDist
  63.     self.nodeNext = nodeNext
  64.     self.pathsGenerated = true
  65. end
  66.  
  67. function FloydWarshallMixin:path(nodeStart, nodeEnd)
  68.     assert(self.pathsGenerated, "Must call :floydWarshall() before :path(...) in order to generate paths")
  69.     local u, v = nodeStart.index, nodeEnd.index
  70.     local path = {}
  71.     if not self.nodeNext[u][v] then return path end
  72.     -- Recover the path
  73.     table.insert(path, self.nodesByIndex[u])
  74.     while u ~= v do
  75.         u = self.nodeNext[u][v]
  76.         table.insert(path, self.nodesByIndex[u])
  77.     end
  78.     return path
  79. end
  80.  
  81. return FloydWarshallMixin
RAW Paste Data