Ozzypig

Graph

Feb 25th, 2018
301
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. -- Graph class
  2. -- ModuleScript with GraphNode, GraphEdge and FloydWarshall ModuleScripts inside
  3. -- by Ozzypig (Twitter: @Ozzypig, ozzypig.com)
  4.  
  5. local GraphNode = require(script:WaitForChild("GraphNode"))
  6. local FloydWarshallMixin = require(script:WaitForChild("FloydWarshall"))
  7.  
  8. local Graph = {}
  9. Graph.__index = Graph
  10.  
  11. -- Functions relating to Floyd-Warshall algorithm implementation
  12. for k, v in pairs(FloydWarshallMixin) do Graph[k] = v end
  13.  
  14. function Graph.new()
  15.     local self = setmetatable({
  16.         nodeCount = 0;
  17.         nodes = {}; -- nodes[node] = node.value (usually just true)
  18.         nodesByIndex = {};
  19.        
  20.         edgeCount = 0;
  21.         edges = {}; -- edge[edge] = edge.value (usually weight)
  22.         edgesByIndex = {};
  23.     }, Graph)
  24.    
  25.     return self
  26. end
  27.  
  28. function Graph:newNode(...)
  29.     local node = GraphNode.new(...)
  30.     node.index = self.nodeCount + 1
  31.     self.nodes[node] = node.value
  32.     self.nodesByIndex[node.index] = node
  33.     self.nodeCount = self.nodeCount + 1
  34.     return node
  35. end
  36.  
  37. function Graph:newEdge(nodeOrigin, nodeTarget, ...)
  38.     local edge = nodeOrigin:newEdgeTo(nodeTarget, ...)
  39.     edge.index = self.edgeCount + 1
  40.     self.edges[edge] = edge.value
  41.     self.edgesByIndex[edge.index] = edge
  42.     self.edgeCount = self.edgeCount + 1
  43.     nodeOrigin:addEdge(edge)
  44. end
  45.  
  46. function Graph:eachNode()
  47.     return pairs(self.nodes)
  48. end
  49.  
  50. function Graph:eachEdge()
  51.     return pairs(self.edges)
  52. end
  53.  
  54. function Graph:randomNode()
  55.     return self.nodesByIndex[math.random(1, #self.nodesByIndex)]
  56. end
  57.  
  58. function Graph:randomEdge()
  59.     return self.edgesByIndex[math.random(1, #self.edgesByIndex)]
  60. end
  61.  
  62. return Graph
RAW Paste Data