Advertisement

Graph

Feb 25th, 2018
762
0
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
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement