Skip to content

chen0040/lua-graph

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

45 Commits
note
note
 
 
rockspecs
rockspecs
 
 
spec
spec
 
 
src/luagraphs
src/luagraphs
 
 
.gitignore
.gitignore
 
 
.travis.yml
.travis.yml
 
 
LICENSE
LICENSE
 
 
README.md
README.md
 
 
Vagrantfile
Vagrantfile
 
 
Vagrantfile.config.yml
Vagrantfile.config.yml
 
 

Repository files navigation

lua-graph

Graph algorithms in lua

Features

The graph algorithms covered:

  • Graph data structure (directed / undirected / weighted / unweighted)
  • Depth first search
  • Breadth 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 g:addEdge(2, 4) g:addEdge(2, 3) g:addEdge(1, 2) g:addEdge(0, 1) g:addEdge(3, 4) g:addEdge(3, 5) g:addEdge(0, 2) 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 adj_v = g:adj(v) -- adjacency list for vertex v 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 g:addEdge(2, 4) g:addEdge(2, 3) g:addEdge(1, 2) g:addEdge(0, 1) g:addEdge(3, 4) g:addEdge(3, 5) g:addEdge(0, 2) -- expand the graph by another 3 vertices: -1, 9, and 10 -- if you want to add a vertex without adding an edge, can just call g:addVertexIfNotExists(vertexId) instead g:addEdge(-1, 10) g:addEdge(9, 2) g:addEdge(-1, 0) 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 adj_v = g:adj(v) -- adjacency list for vertex v 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() vertices:add(3) vertices:add(5) vertices:add(10) local g = require('luagraphs.data.graph').createFromVertexList(vertices) print(g:vertexCount()) -- return 3 g:addVertexIfNotExists(4) g:addVertexIfNotExists(5) 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 adj_v = g:adj(v) -- adjacency list for vertex v 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 g:addEdge(2, 4) g:addEdge(2, 3) g:addEdge(1, 2) g:addEdge(0, 1) g:addEdge(3, 4) g:addEdge(3, 5) g:addEdge(0, 2) 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 adj_v = g:adj(v) -- adjacency list for vertex v local text = '' for i = 0, adj_v:size()-1 do local e = adj_v:get(i) 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 g:addEdge(2, 4, 2.2) g:addEdge(2, 3, 1.2) g:addEdge(1, 2, 1.2) g:addEdge(0, 1, 2.2) g:addEdge(3, 4, 1.2) g:addEdge(3, 5, 2.2) g:addEdge(0, 2, 2.2) 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 adj_v = g:adj(v) -- adjacency list for vertex v local text = '' for i = 0, adj_v:size()-1 do local e = adj_v:get(i) 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 g:addEdge(2, 4, 2.2) g:addEdge(2, 3, 1.2) g:addEdge(1, 2, 1.2) g:addEdge(0, 1, 2.2) g:addEdge(3, 4, 1.2) g:addEdge(3, 5, 2.2) g:addEdge(0, 2, 2.2) 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 adj_v = g:adj(v) -- adjacency list for vertex v local text = '' for i = 0, adj_v:size()-1 do local e = adj_v:get(i) text = text .. ', ' .. e:other(v) .. '(' .. e.weight .. ')'  end print(text) end

Depth First Search

local g = require('luagraphs.data.graph').create(6) g:addEdge(0, 5) g:addEdge(2, 4) g:addEdge(2, 3) g:addEdge(1, 2) g:addEdge(0, 1) g:addEdge(3, 4) g:addEdge(3, 5) g:addEdge(0, 2) 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

Breadth First Search

local g = require('luagraphs.data.graph').create(6) g:addEdge(0, 5) g:addEdge(2, 4) g:addEdge(2, 3) g:addEdge(1, 2) g:addEdge(0, 1) g:addEdge(3, 4) g:addEdge(3, 5) g:addEdge(0, 2) local bfs = require('luagraphs.search.BreadthFirstSearch').create() 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 g:addEdge(0, 5) g:addEdge(4, 3) g:addEdge(0, 1) g:addEdge(9, 12) g:addEdge(6, 4) g:addEdge(5, 4) g:addEdge(0, 2) g:addEdge(11, 12) g:addEdge(9,10) g:addEdge(0, 6) g:addEdge(7, 8) g:addEdge(9, 11) g:addEdge(5, 3) 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 graph:addEdge(4, 2) graph:addEdge(2, 3) graph:addEdge(3, 2) graph:addEdge(6, 0) graph:addEdge(0, 1) graph:addEdge(2, 0) graph:addEdge(11, 12) graph:addEdge(12, 9) graph:addEdge(9, 10) graph:addEdge(9, 11) graph:addEdge(8, 9) graph:addEdge(10, 12) graph:addEdge(11, 4) graph:addEdge(4, 3) graph:addEdge(3, 5) graph:addEdge(7, 8) graph:addEdge(8, 7) graph:addEdge(5, 4) graph:addEdge(0, 5) graph:addEdge(6, 4) graph:addEdge(6, 9) graph:addEdge(7, 6) 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 dag:addEdge(0, 5) dag:addEdge(0, 2) dag:addEdge(0, 1) dag:addEdge(3, 6) dag:addEdge(3, 5) dag:addEdge(3, 4) dag:addEdge(5, 4) dag:addEdge(6, 4) dag:addEdge(6, 0) dag:addEdge(3, 2) dag:addEdge(1, 4) 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 g:addEdge(2, 3, 0.17) g:addEdge(1, 7, 0.19) g:addEdge(0, 2, 0.26) g:addEdge(5, 7, 0.28) g:addEdge(1, 3, 0.29) g:addEdge(1, 5, 0.32) g:addEdge(2, 7, 0.34) g:addEdge(4, 5, 0.35) g:addEdge(1, 2, 0.36) g:addEdge(4, 7, 0.37) g:addEdge(0, 4, 0.38) g:addEdge(6, 2, 0.4) g:addEdge(3, 6, 0.52) g:addEdge(6, 0, 0.58) g:addEdge(6, 4, 0.93) 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 g:addEdge(2, 3, 0.17) g:addEdge(1, 7, 0.19) g:addEdge(0, 2, 0.26) g:addEdge(5, 7, 0.28) g:addEdge(1, 3, 0.29) g:addEdge(1, 5, 0.32) g:addEdge(2, 7, 0.34) g:addEdge(4, 5, 0.35) g:addEdge(1, 2, 0.36) g:addEdge(4, 7, 0.37) g:addEdge(0, 4, 0.38) g:addEdge(6, 2, 0.4) g:addEdge(3, 6, 0.52) g:addEdge(6, 0, 0.58) g:addEdge(6, 4, 0.93) 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 g:addEdge(2, 3, 0.17) g:addEdge(1, 7, 0.19) g:addEdge(0, 2, 0.26) g:addEdge(5, 7, 0.28) g:addEdge(1, 3, 0.29) g:addEdge(1, 5, 0.32) g:addEdge(2, 7, 0.34) g:addEdge(4, 5, 0.35) g:addEdge(1, 2, 0.36) g:addEdge(4, 7, 0.37) g:addEdge(0, 4, 0.38) g:addEdge(6, 2, 0.4) g:addEdge(3, 6, 0.52) g:addEdge(6, 0, 0.58) g:addEdge(6, 4, 0.93) 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 g:addEdge(0, 4, 9.0) g:addEdge(0, 7, 8.0) g:addEdge(1, 2, 12.0) g:addEdge(1, 3, 15.0) g:addEdge(1, 7, 4.0) g:addEdge(2, 3, 3.0) g:addEdge(2, 6, 11.0) g:addEdge(3, 6, 9.0) g:addEdge(4, 5, 5.0) g:addEdge(4, 6, 20.0) g:addEdge(4, 7, 5.0) g:addEdge(5, 2, 1.0) g:addEdge(5, 6, 13.0) g:addEdge(7, 5, 6.0) g:addEdge(7, 2, 7.0) 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 g:addEdge(0, 4, 9.0) g:addEdge(0, 7, 8.0) g:addEdge(1, 2, 12.0) g:addEdge(1, 3, 15.0) g:addEdge(1, 7, 4.0) g:addEdge(2, 3, 3.0) g:addEdge(2, 6, 11.0) g:addEdge(3, 6, 9.0) g:addEdge(4, 5, 5.0) g:addEdge(4, 6, 20.0) g:addEdge(4, 7, 5.0) g:addEdge(5, 2, 1.0) g:addEdge(5, 6, 13.0) g:addEdge(7, 5, 6.0) g:addEdge(7, 2, 7.0) 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 g:addEdge(0, 2, 5); g:addEdge(0, 3, 15); g:addEdge(1, 4, 9); g:addEdge(1, 5, 15); g:addEdge(1, 2, 4); g:addEdge(2, 5, 8); g:addEdge(2, 3, 4); g:addEdge(3, 6, 16); g:addEdge(4, 5, 15); g:addEdge(4, 7, 10); g:addEdge(5, 7, 10); g:addEdge(5, 6, 15); g:addEdge(6, 2, 6); g:addEdge(6, 7, 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

About

Graph algorithms in lua

Topics

mincut dijkstra shortest-paths topological-sort breadth-first-search minimum-spanning-trees depth-first-search maxflow dijkstra-algorithm connected-components strongly-connected-components bellman-ford-algorithm

Resources

Readme

License

MIT license
Activity

Stars

69 stars

Watchers

4 watching

Forks

13 forks
Report repository

Releases

5 tags

Packages

No packages published

Contributors 2

  •  
  •  

Languages