i made this module script for the lolz but if you find it useful feel free to get it.
you can build cool graphs using adjacency matrices. for example:
this matrix:
{ --u1, u2, u3, u4
u1 {1, 2, 1, 1},
u2 {2, 0, 1, 0},
u3 {1, 1, 0, 1},
u4 {1, 0, 1, 0} }
converts to this graph:
made using my amazing ms paint skills
notice how the matrix is NxN size where N the number of vertices and its symetrical to the main diagonal. each element t[i][j] shows how many edges connect vertices i and j together.
you can currently:
- add/remove vertices
- add/remove edges (that connect 2 vertices together)
- check if there is a path that connects vertices u and v using the depth first search algorithm (works recursively)
- check if there is a direct path between 2 vertices
- check if a graph is k-regular and calculate the degree for a given vertex
plans for the future:
- you will be able to store different types of data in each vertex
- hamiltonian/eulerian graphs
- trees/binary trees
- directional graphs
& more suggestions…
feel free to suggest anything or comment on any bugs you may find. p.s. please pray that i pass my discrete mathematics class
Older versions:
Source code (Original)
local Graph = {}
Graph.__index = Graph
--[[
Create a new graph:
Parameters:
matrix: The adjacency matrix of the graph.
]]
function Graph.new(matrix: {any})
local newgraph = {}
setmetatable(newgraph, Graph)
newgraph.matrix = matrix
newgraph.vertices = #matrix
newgraph.edges = getEdges(matrix)
return newgraph
end
--[[
Get the edges of the graph.
]]
function getEdges(matrix): number
local e = 0
for i=1, #matrix do
for j=1, #matrix[i] do
e = e + matrix[i][j]
end
end
return e
end
--[[
Can you draw a path between 2 edges, u and v?
Uses the DFS algorithm.
Returns true or false, whether a path exists or not.
Parameters:
visited = {} -- ALWAYS START WITH AN EMPTY TABLE!
u = The starting vertex.
v = The ending vertex.
]]
function Graph:DFS(visited: {any}, u: number, v: number): boolean
if u == v then
return true
end
visited[u] = true
for neighbor = 1, #self.matrix do
if self.matrix[u][neighbor] >=1 and not visited[neighbor] then
if self:DFS(visited, neighbor, v) then
return true
end
end
end
return false
end
--[[
Are 2 vertices connected directly with eachother?
Parameters:
u: starting vertex
v: ending vertex
]]
function Graph:isReachable(u: number, v: number): boolean
return self.matrix[u][v] >= 1
end
--[[
Add an edge to the graph, connecting vertices u and v
]]
function Graph:addEdge(u, v)
self.matrix[u][v] = self.matrix[u][v] + 1
self.matrix[v][u] = self.matrix[v][u] + 1
self.edges += 1
end
--[[
Remove an edge from the graph, disconnecting vertices u and v
]]
function Graph:removeEdge(u, v)
if self.matrix[u][v] > 0 and self.matrix[v][u] > 0 then
self.matrix[u][v] = self.matrix[u][v] - 1
self.matrix[v][u] = self.matrix[v][u] - 1
self.edges -= 1
end
end
--[[
Add a vertex to the graph, expanding the adjacency matrix
]]
function Graph:addVertex()
local newrow = {}
for i = 1, #self.matrix do
table.insert(self.matrix[i], 0)
end
table.insert(self.matrix, {})
for i = 1, #self.matrix do
table.insert(self.matrix[#self.matrix], 0)
end
self.vertices += 1
end
--[[
Remove a vertex from the graph, adjusting the adjacency matrix
]]
function Graph:removeVertex(u)
table.remove(self.matrix, u)
for i = 1, #self.matrix do
table.remove(self.matrix[i], u)
end
self.vertices = self.vertices - 1
end
return Graph
Newest release:
Source code (Update #1)
local Graph = {}
Graph.__index = Graph
--[[
Create a new graph:
Parameters:
matrix: The adjacency matrix of the graph.
]]
function Graph.new(matrix: {any})
local newgraph = {}
setmetatable(newgraph, Graph)
newgraph.matrix = matrix
newgraph.vertices = #matrix
newgraph.edges = getEdges(matrix)
return newgraph
end
--[[
Get the edges of the graph.
]]
function getEdges(matrix): number
local e = 0
for i=1, #matrix do
for j=1, #matrix[i] do
e = e + matrix[i][j]
end
end
return e
end
--[[
Can you draw a path between 2 edges, u and v?
Uses the DFS algorithm.
Returns true or false, whether a path exists or not.
Parameters:
visited = {} -- ALWAYS START WITH AN EMPTY TABLE!
u = The starting vertex.
v = The ending vertex.
]]
function Graph:DFS(visited: {any}, u: number, v: number): boolean
if u == v then
return true
end
visited[u] = true
for neighbor = 1, #self.matrix do
if self.matrix[u][neighbor] >=1 and not visited[neighbor] then
if self:DFS(visited, neighbor, v) then
return true
end
end
end
return false
end
--[[
Are 2 vertices connected directly with eachother?
Parameters:
u: starting vertex
v: ending vertex
]]
function Graph:areNeighbors(u: number, v: number): boolean
return self.matrix[u][v] >= 1
end
--[[
Add an edge to the graph, connecting vertices u and v
]]
function Graph:addEdge(u, v)
self.matrix[u][v] = self.matrix[u][v] + 1
self.matrix[v][u] = self.matrix[v][u] + 1
self.edges += 1
end
--[[
Remove an edge from the graph, disconnecting vertices u and v
]]
function Graph:removeEdge(u, v)
if self.matrix[u][v] > 0 and self.matrix[v][u] > 0 then
self.matrix[u][v] = self.matrix[u][v] - 1
self.matrix[v][u] = self.matrix[v][u] - 1
self.edges -= 1
end
end
--[[
Add a vertex to the graph, expanding the adjacency matrix
]]
function Graph:addVertex()
local newrow = {}
for i = 1, #self.matrix do
table.insert(self.matrix[i], 0)
end
table.insert(self.matrix, {})
for i = 1, #self.matrix do
table.insert(self.matrix[#self.matrix], 0)
end
self.vertices += 1
end
--[[
Remove a vertex from the graph, adjusting the adjacency matrix
]]
function Graph:removeVertex(u)
table.remove(self.matrix, u)
for i = 1, #self.matrix do
table.remove(self.matrix[i], u)
end
self.vertices = self.vertices - 1
end
--[[
:getDegree(u)
get degree of vertex u
Parameters:
- u: a vertex
]]
function Graph:getDegree(u): number
local degree = 0
for j = 1, #self.matrix[u] do
degree = degree + self.matrix[u][j]
end
return degree
end
--[[
:isRegular()
returns:
-1 if the graph is not regular
or
k>0 which means the graph is k-regular
]]
function Graph:isRegular(): number
local k = -1
for u = 1, #self.matrix do
local degree = self:getDegree(u)
if k == -1 then
k = degree
elseif degree ~= k then
return -1
end
end
return k
end
return Graph