Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Graph algorithms in lua

License

NotificationsYou must be signed in to change notification settings

chen0040/lua-graph

Repository files navigation

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

localg=require('luagraphs.data.graph').create(6)g:addEdge(0,5)-- bidirectional edge connecting 0 and 5g: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 listfork=0,g:vertexCount()-1do-- iterate through all the vertices in glocalv=g:vertexAt(k)localadj_v=g:adj(v)-- adjacency list for vertex vlocaltext=''fori=0,adj_v:size()-1dotext=text..','..adj_v:get(i):other(v)endprint(text)end

Create an undirected unweighted graph and add / remove vertices later

localg=require('luagraphs.data.graph').create(6)g:addEdge(0,5)-- bidirectional edge connecting 0 and 5g: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) insteadg:addEdge(-1,10)g:addEdge(9,2)g:addEdge(-1,0)print(g:containsVertex(9))-- return trueprint(g:containsVertex(-1))-- return trueprint(g:containsVertex(8))-- return falseprint(g:vertexCount())-- return 9-- to remove a vertex, can just call g:removeVertex(vertexId)-- code below prints the adjacency listfork=0,g:vertexCount()-1do-- iterate through all the vertices in glocalv=g:vertexAt(k)localadj_v=g:adj(v)-- adjacency list for vertex vlocaltext=''fori=0,adj_v:size()-1dotext=text..','..adj_v:get(i):other(v)endprint(text)end

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

localvertices=require('luagraphs.data.list').create()vertices:add(3)vertices:add(5)vertices:add(10)localg=require('luagraphs.data.graph').createFromVertexList(vertices)print(g:vertexCount())-- return 3g:addVertexIfNotExists(4)g:addVertexIfNotExists(5)print(g:vertexCount())-- return 4g:addEdge(0,5)-- add a new vertex 0 and a bidirectional edge connecting 0 and 5print(g:vertexCount())-- return 5g:removeVertex(10)print(g:vertexCount())-- return 4-- code below prints the adjacency listfork=0,g:vertexCount()-1do-- iterate through all the vertices in glocalv=g:vertexAt(k)localadj_v=g:adj(v)-- adjacency list for vertex vlocaltext=''fori=0,adj_v:size()-1dotext=text..','..adj_v:get(i):other(v)endprint(text)end

Create an directed unweighted graph

localg=require('luagraphs.data.graph').create(6,true)-- true means it is directedg:addEdge(0,5)-- edge directed from 0 to 5g: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 listfork=0,g:vertexCount()-1do-- iterate through all vertices in glocalv=g:vertexAt(k)localadj_v=g:adj(v)-- adjacency list for vertex vlocaltext=''fori=0,adj_v:size()-1dolocale=adj_v:get(i)text=text..','..e:other(v)endprint(text)end

Create an undirected weighted graph

localg=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 5g: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 listfork=0,g:vertexCount()-1do-- iterate through all vertices in glocalv=g:vertexAt(k)localadj_v=g:adj(v)-- adjacency list for vertex vlocaltext=''fori=0,adj_v:size()-1dolocale=adj_v:get(i)text=text..','..e:other(v)..'('..e.weight..')'endprint(text)end

Create an directed weighted graph

localg=require('luagraphs.data.graph').create(6,true)-- true means directedg:addEdge(0,5,1.2)-- bidirectional edge with weight equal to 1.2 and connecting between 0 and 5g: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 listfork=0,g:vertexCount()-1do-- iterate through all vertices in glocalv=g:vertexAt(k)localadj_v=g:adj(v)-- adjacency list for vertex vlocaltext=''fori=0,adj_v:size()-1dolocale=adj_v:get(i)text=text..','..e:other(v)..'('..e.weight..')'endprint(text)end

Depth First Search

localg=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)localdfs=require('luagraphs.search.DepthFirstSearch').create()locals=0dfs:run(g,s)fork=0,g:vertexCount()-1dolocalv=g:vertexAt(k)ifv~=sanddfs:hasPathTo(v)thenprint('has path to'..v)localpath=dfs:getPathTo(v)localpathText=''whilepath:isEmpty()==falsedolocalx=path:pop()ifpathText==''thenpathText=pathText..xelsepathText=pathText..' ->'..xendendprint(pathText)endend

Breadth First Search

localg=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)localbfs=require('luagraphs.search.BreadthFirstSearch').create()locals=0bfs:run(g,s)fork=0,g:vertexCount()-1dolocalv=g:vertexAt(k)ifv~=sandbfs:hasPathTo(v)thenlocalpath=bfs:getPathTo(v)localpathText=''whilepath:isEmpty()==falsedolocalx=path:pop()ifpathText==''thenpathText=pathText..xelsepathText=pathText..' ->'..xendendprint(pathText)endend

Connected Components

localg=require('luagraphs.data.graph').create(13)-- undirected graphg: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)localcc=require('luagraphs.connectivity.ConnectedComponents').create()cc:run(g)print('count:'..cc.count)print(cc.count)-- return 3 connected componentsfork=0,g:vertexCount()-1dolocalv=g:vertexAt(k)print('id['..v..']:'..cc:component(v))end

Strongly Connected Components

localgraph=require('luagraphs.data.graph').create(13,true)-- directed graphgraph: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)localscc=require('luagraphs.connectivity.StronglyConnectedComponents').create()scc:run(graph)print(scc.count)-- return 5 componentsfork=0,graph:vertexCount()-1dolocalv=graph:vertexAt(k)print('id['..v..']:'..scc:component(v))end

Topological Sort

localdag=require('luagraphs.data.graph').create(7,true)-- directed acyclic graphdag: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)localts=require('luagraphs.sort.TopologicalSort').create()ts:run(dag)localpath=ts:path()fori=0,path:size()-1doprint('sort #'..i..':'..path:get(i))end

Minimum Spanning Tree (Kruskal)

localmst=require('luagraphs.mst.KruskalMST').create()localg=require('luagraphs.data.graph').create(8)-- undirected graph with weighted edgesg:addEdge(0,7,0.16)-- 0.16 is the weight of the edge between 0 and 7g: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)localpath=mst.pathprint(path:size())-- return 7fori=0,path:size()-1dolocale=path:get(i)print(e:from()..' ->'..e:to()..' ('..e.weight..')')end

Minimum Spanning Tree (Prim)

localmst=require('luagraphs.mst.PrimMST').create()localg=require('luagraphs.data.graph').create(8)-- undirected graph with weighted edgesg:addEdge(0,7,0.16)-- 0.16 is the weight of the edge between 0 and 7g: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)localpath=mst.pathprint(path:size())-- return 7fori=0,path:size()-1dolocale=path:get(i)print(e:from()..' ->'..e:to()..' ('..e.weight..')')end

Minimum Spanning Tree (Eager Prim)

localmst=require('luagraphs.mst.EagerPrimMST').create()localg=require('luagraphs.data.graph').create(8)-- undirected graph with weighted edgesg:addEdge(0,7,0.16)-- 0.16 is the weight of the edge between 0 and 7g: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)localpath=mst.pathprint(path:size())-- return 7fori=0,path:size()-1dolocale=path:get(i)print(e:from()..' ->'..e:to()..' ('..e.weight..')')end

Shortest Paths (Dijkstra)

localg=require('luagraphs.data.graph').create(8,true);-- directed weighted graphg:addEdge(0,1,5.0)-- edge from 0 to 1 is 5.0 in distanceg: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)localsource=0localdijkstra=require('luagraphs.shortest_paths.Dijkstra').create()dijkstra:run(g,source)-- 0 is the id of the source node in the path searchfork=0,g:vertexCount()-1dolocalv=g:vertexAt(k)ifv~=sourceanddijkstra:hasPathTo(v)thenprint('path from 0 to'..v..' ( cost:'..dijkstra:getPathLength(v)..' )')localpath=dijkstra:getPathTo(v)fori=0,path:size()-1doprint('# from'..path:get(i):from()..' to'..path:get(i):to()..' ( distance:'..path:get(i).weight..' )')endendend

Shortest Paths (Topological Sort)

localg=require('luagraphs.data.graph').create(8,true);-- directed weighted graphg:addEdge(0,1,5.0)-- edge from 0 to 1 is 5.0 in distanceg: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)localsource=0localfinder=require('luagraphs.shortest_paths.Dijkstra').create()finder:run(g,source)-- 0 is the source node in the path searchfork=0,g:vertexCount()-1dolocalv=g:vertexAt(k)ifv~=sourceandfinder:hasPathTo(v)thenprint('path from 0 to'..v..' ( cost:'..finder:getPathLength(v)..' )')localpath=finder:getPathTo(v)fori=0,path:size()-1doprint('# from'..path:get(i):from()..' to'..path:get(i):to()..' ( distance:'..path:get(i).weight..' )')endendend

MinCut-MaxFlow (Ford Fulkerson implementation)

localg=require('luagraphs.data.network').FlowNetwork.create(8);g:addEdge(0,1,10);-- capacity from vertex 0 to vertex 1 is 10g: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);localmethod=require('luagraphs.flow.FordFulkerson').create()localmaxFlow=method:run(g,0,7)print('FordFulkerson max flow:'..maxFlow)localminCuts=method:minCuts()fori=0,minCuts:size()-1dolocale=minCuts:get(i)print('min cut:'..e:toString())end
[8]ページ先頭
©2009-2025 Movatter.jp