/ lua-graph Public

Graph algorithms in lua

# chen0040/lua-graph

Switch branches/tags
Nothing to show

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

## Files

Failed to load latest commit information.
Type
Name
Commit time

# lua-graph

Graph algorithms in lua

# Features

The graph algorithms covered:

• Graph data structure (directed / undirected / weighted / unweighted)
• Depth first search
• Connected components
• Strongly connected components
• Topological sort
• Minimum spanning tree (Kruskal)
• Minimum spanning tree (Prim)
• Max flow min cut
• Dijkstra shortest paths
• Topogical sort shortest paths
• Bellman Ford shortest paths

# Notes

For developers who have been using library 1.0.2, the main changes are:

• graph.V is removed and replaced with graph:vertexCount() and graph:vertexAt(index) method for iterating all vertices: this change was introduced so that graph vertices do not need to start with vertex 0 and do not need to be consecutive integer (can be any label).
• graph:addVertexIfNotExists: allows user to add vertices later after the graph is created
• graph:removeVertex: allows user to delete a vertex and its edges
• graph:addEdge: Now if the vertices on which the edge is to be added does not exists in the graph, they will be automatically added

# Install

`luarocks install luagraphs`

# Usage

### Create an undirected unweighted graph

```local g = require('luagraphs.data.graph').create(6)
g:addEdge(0, 5) -- bidirectional edge connecting 0 and 5

print(g:vertexCount()) -- return 6

-- code below prints the adjacency list
for k = 0, g:vertexCount() -1 do -- iterate through all the vertices in g
local v = g:vertexAt(k)
local text = ''
for i = 0, adj_v:size()-1 do
text = text .. ', ' .. adj_v:get(i):other(v)
end
print(text)
end```

### Create an undirected unweighted graph and add / remove vertices later

```local g = require('luagraphs.data.graph').create(6)
g:addEdge(0, 5) -- bidirectional edge connecting 0 and 5

-- expand the graph by another 3 vertices: -1, 9, and 10

print(g:containsVertex(9)) -- return true
print(g:containsVertex(-1)) -- return true
print(g:containsVertex(8)) -- return false

print(g:vertexCount()) -- return 9

-- to remove a vertex, can just call g:removeVertex(vertexId)

-- code below prints the adjacency list
for k = 0, g:vertexCount() -1 do -- iterate through all the vertices in g
local v = g:vertexAt(k)
local text = ''
for i = 0, adj_v:size()-1 do
text = text .. ', ' .. adj_v:get(i):other(v)
end
print(text)
end```

### Create an undirected unweighted graph from a list of vertices and expand or shrink it

```local vertices = require('luagraphs.data.list').create()

local g = require('luagraphs.data.graph').createFromVertexList(vertices)

print(g:vertexCount()) -- return 3

print(g:vertexCount()) -- return 4

g:addEdge(0, 5) -- add a new vertex 0 and a bidirectional edge connecting 0 and 5

print(g:vertexCount()) -- return 5

g:removeVertex(10)

print(g:vertexCount()) -- return 4

-- code below prints the adjacency list
for k = 0, g:vertexCount() -1 do -- iterate through all the vertices in g
local v = g:vertexAt(k)
local text = ''
for i = 0, adj_v:size()-1 do
text = text .. ', ' .. adj_v:get(i):other(v)
end
print(text)
end```

### Create an directed unweighted graph

```local g = require('luagraphs.data.graph').create(6, true) -- true means it is directed
g:addEdge(0, 5) -- edge directed from 0 to 5

print(g:vertexCount()) -- return 6

-- code below prints the adjacency list
for k = 0, g:vertexCount() -1 do -- iterate through all vertices in g
local v = g:vertexAt(k)
local text = ''
for i = 0, adj_v:size()-1 do
text = text .. ', ' .. e:other(v)
end
print(text)
end```

### Create an undirected weighted graph

```local g = require('luagraphs.data.graph').create(6)
g:addEdge(0, 5, 1.2) -- bidirectional edge with weight equal to 1.2 and connecting between 0 and 5

print(g:vertexCount()) -- return 6

-- code below prints the adjacency list
for k = 0, g:vertexCount() -1 do -- iterate through all vertices in g
local v = g:vertexAt(k)
local text = ''
for i = 0, adj_v:size()-1 do
text = text .. ', ' .. e:other(v) .. '(' .. e.weight .. ')'
end
print(text)
end```

### Create an directed weighted graph

```local g = require('luagraphs.data.graph').create(6, true) -- true means directed
g:addEdge(0, 5, 1.2) -- bidirectional edge with weight equal to 1.2 and connecting between 0 and 5

print(g:vertexCount()) -- return 6

-- code below prints the adjacency list
for k = 0, g:vertexCount() -1 do -- iterate through all vertices in g
local v = g:vertexAt(k)
local text = ''
for i = 0, adj_v:size()-1 do
text = text .. ', ' .. e:other(v) .. '(' .. e.weight .. ')'
end
print(text)
end```

### Depth First Search

```local g = require('luagraphs.data.graph').create(6)
local dfs = require('luagraphs.search.DepthFirstSearch').create()
local s = 0
dfs:run(g, s)

for k = 0, g:vertexCount()-1 do
local v = g:vertexAt(k)
if v ~= s and dfs:hasPathTo(v) then
print('has path to ' .. v)
local path = dfs:getPathTo(v)
local pathText = ''
while path:isEmpty() == false do
local x = path:pop()
if pathText == '' then
pathText = pathText .. x
else
pathText = pathText .. ' -> ' .. x
end
end
print(pathText)

end
end```

```local g = require('luagraphs.data.graph').create(6)
local s = 0
bfs:run(g, s)

for k = 0, g:vertexCount()-1 do
local v = g:vertexAt(k)
if v ~= s and bfs:hasPathTo(v) then
local path = bfs:getPathTo(v)
local pathText = ''
while path:isEmpty() == false do
local x = path:pop()
if pathText == '' then
pathText = pathText .. x
else
pathText = pathText .. ' -> ' .. x
end
end
print(pathText)

end
end```

### Connected Components

```local g = require('luagraphs.data.graph').create(13) -- undirected graph

local cc = require('luagraphs.connectivity.ConnectedComponents').create()
cc:run(g)

print('count: ' .. cc.count)
print(cc.count) -- return 3 connected components
for k = 0,g:vertexCount()-1 do
local v = g:vertexAt(k)
print('id[' .. v .. ']: ' .. cc:component(v))
end```

### Strongly Connected Components

```local graph = require('luagraphs.data.graph').create(13, true) -- directed graph

local scc = require('luagraphs.connectivity.StronglyConnectedComponents').create()
scc:run(graph)
print(scc.count) -- return 5 components

for k = 0,graph:vertexCount()-1 do
local v = graph:vertexAt(k)
print('id[' .. v .. ']: ' .. scc:component(v))
end```

### Topological Sort

```local dag = require('luagraphs.data.graph').create(7, true) -- directed acyclic graph

local ts = require('luagraphs.sort.TopologicalSort').create()
ts:run(dag)

local path = ts:path()
for i=0, path:size()-1 do
print('sort #' .. i .. ': ' .. path:get(i))
end```

### Minimum Spanning Tree (Kruskal)

```local mst = require('luagraphs.mst.KruskalMST').create()
local g = require('luagraphs.data.graph').create(8) -- undirected graph with weighted edges
g:addEdge(0, 7, 0.16) -- 0.16 is the weight of the edge between 0 and 7

mst:run(g)

local path = mst.path

print(path:size()) -- return 7
for i=0,path:size()-1 do
local e = path:get(i)
print(e:from() .. ' -> ' .. e:to() .. ' (' .. e.weight .. ')')
end```

### Minimum Spanning Tree (Prim)

```local mst = require('luagraphs.mst.PrimMST').create()
local g = require('luagraphs.data.graph').create(8) -- undirected graph with weighted edges
g:addEdge(0, 7, 0.16) -- 0.16 is the weight of the edge between 0 and 7

mst:run(g)

local path = mst.path

print(path:size()) -- return 7
for i=0,path:size()-1 do
local e = path:get(i)
print(e:from() .. ' -> ' .. e:to() .. ' (' .. e.weight .. ')')
end```

### Minimum Spanning Tree (Eager Prim)

```local mst = require('luagraphs.mst.EagerPrimMST').create()
local g = require('luagraphs.data.graph').create(8) -- undirected graph with weighted edges
g:addEdge(0, 7, 0.16) -- 0.16 is the weight of the edge between 0 and 7

mst:run(g)

local path = mst.path

print(path:size()) -- return 7
for i=0,path:size()-1 do
local e = path:get(i)
print(e:from() .. ' -> ' .. e:to() .. ' (' .. e.weight .. ')')
end```

### Shortest Paths (Dijkstra)

```local g = require('luagraphs.data.graph').create(8, true); -- directed weighted graph

g:addEdge(0, 1, 5.0) -- edge from 0 to 1 is 5.0 in distance

local source = 0
local dijkstra = require('luagraphs.shortest_paths.Dijkstra').create()
dijkstra:run(g, source) -- 0 is the id of the source node in the path search
for k = 0,g:vertexCount()-1 do
local v = g:vertexAt(k)
if v ~= source and dijkstra:hasPathTo(v) then
print('path from 0 to ' .. v .. ' ( cost: '  .. dijkstra:getPathLength(v) .. ' )')
local path = dijkstra:getPathTo(v)
for i = 0,path:size()-1 do
print('# from ' .. path:get(i):from() .. ' to ' .. path:get(i):to() .. ' ( distance: ' .. path:get(i).weight .. ' )')
end
end
end```

### Shortest Paths (Topological Sort)

```local g = require('luagraphs.data.graph').create(8, true); -- directed weighted graph

g:addEdge(0, 1, 5.0) -- edge from 0 to 1 is 5.0 in distance

local source = 0
local finder = require('luagraphs.shortest_paths.Dijkstra').create()
finder:run(g, source) -- 0 is the source node in the path search
for k = 0,g:vertexCount()-1 do
local v= g:vertexAt(k)
if v ~= source and finder:hasPathTo(v) then
print('path from 0 to ' .. v .. ' ( cost: '  .. finder:getPathLength(v) .. ' )')
local path = finder:getPathTo(v)
for i = 0,path:size()-1 do
print('# from ' .. path:get(i):from() .. ' to ' .. path:get(i):to() .. ' ( distance: ' .. path:get(i).weight .. ' )')
end
end
end```

### MinCut-MaxFlow (Ford Fulkerson implementation)

```local g = require('luagraphs.data.network').FlowNetwork.create(8);

g:addEdge(0, 1, 10); -- capacity from vertex 0 to vertex 1 is 10

local method = require('luagraphs.flow.FordFulkerson').create()
local maxFlow = method:run(g, 0, 7)
print('FordFulkerson max flow: ' .. maxFlow)

local minCuts = method:minCuts()

for i = 0,minCuts:size()-1 do
local e =minCuts:get(i)
print('min cut: ' .. e:toString())
end```

Graph algorithms in lua

5 tags

## Packages 0

No packages published