Layout algorithms for graphs and trees in pure Julia.
Linux, OSX :
Windows :
Spring-Electric Force Directed Placement algorithm as explained in Efficient and High Quality Force-Directed Graph Drawing by Yifan Hu.
Module Name : SFDP
layout(adjacency_matrix,dimension;startpostitions,tol,C,K,iterations)adjacency_matrix- sparse/full adjacency matrix that represents the graphdimension- dimension in which the layouting code has to be generated.dimensioncan be an integer specifying the dimension or aPointtype, eg.Point3f0which denotes 3D.startpositions- co-ordinates of the layout to start with. By default, a random layout is used (kwarg)tol- permitted distance between current and calculated co-ordinate. Lower the tolerance, more the number of iterations (kwarg)C, K- used to scale the layout (kwarg)iterations- Number of iterations we apply the forces (kwarg)
positions - co-ordinates of nodes in the layout
A user can move between iterations using a Layout object.
using LightGraphs
using NetworkLayout:SFDP
g = WheelGraph(10)
a = adjacency_matrix(g) # generates a sparse adjacency matrix
network = layout(a,Point2f0,tol=0.1,C=1,K=1,iterations=10) # generate 2D layoutUsing Iterator :
g = WheelGraph(10)
a = adjacency_matrix(g)
tol = 0.1
C = 0.2
K = 1
iterations = 100
network = Layout(a,locs,tol,C,K,iterations)
state = start(network)
while !done(network,state)
network, state = next(network,state)
end
return network.positions
The image shows a LightGraphs.WheelGraph(10) object layout generated by SFDP Algorithm.
Buchheim Tree Drawing as explained in Improving Walker's Algorithm to Run in Linear Time by Christoph Buchheim, Michael Junger and Sebastian Leipert.
Module Name : Buchheim
layout(adjacency_list; nodesize)adjacency_list- adjacency list that represents the treenodesize- sizes of nodes (used to position the nodes) (kwarg)
positions- co-ordinates of the layout
using NetworkLayout:Buchheim
adj_list = Vector{Int}[ # adjacency list
[2,3,4],
[5,6],
[7],
[],
[],
[],
[]
]
nodesize = [1,2.3,1.2,2,3,1.4,0.8]
locs = layout(adj_list,nodesize=nodesize) # generating the layout for the tree
The image shows a LightGraphs.BinaryTree(4) object layout by Buchheim Algorithm.
Spring/Repulsion model of Fruchterman and Reingold (1991). Original code taken from GraphLayout.jl
Module Name : Spring
layout(adjacency_matrix,dimension;startpositions,C,iterations,initialtemp)adjacency_matrix- sparse/full adjacency matrix that represents the graphdimension- dimension in which the layouting code has to be generated.dimensioncan be an integer specifying the dimension or aPointtype, eg.Point3f0which denotes 3D.startpositions- co-ordinates of the layout to start with. By default, a random layout is used (kwarg)iterations- Number of iterations we apply the forces (kwarg)C- Constant to fiddle with density of resulting layout (kwarg)initialtemp- Initial "temperature", controls movement per iteration (kwarg)
positions - co-ordinates of nodes in the layout
A user can move between iterations using a Layout object.
using LightGraphs
using NetworkLayout:Spring
g = WheelGraph(30)
a = adjacency_matrix(g) # generates a sparse adjacency matrix
network = layout(a,Point2f0,C=2.0,iterations=100,K=2.0) # generate 2D layoutUsing Iterator :
g = WheelGraph(30)
a = adjacency_matrix(g)
iterations = 200
C = 2.0
initialtemp = 2.0
network = Layout(a,locs,C,iterations,initialtemp)
state = start(network)
while !done(network,state)
network, state = next(network,state)
end
return network.positions
The image shows a LightGraphs.WheelGraph(10) object layout generated by Spring Algorithm.
Based on the algorithm explained in "Graph Drawing by Stress Majorization" by Emden R Gansner, Yehuda Koren and Stephen North. Original code taken from GraphLayout.jl
Module Name : Stress
layout(δ,dimension;startpositions,weights,iterations,abstols,reltols,abstolx)δ- Matrix of pairwise distances (Adjacency Matrix can be used)dimension- dimension in which the layouting code has to be generated.dimensioncan be an integer specifying the dimension or aPointtype, eg.Point3f0which denotes 3D.weights- Matrix of weights (kwarg)startpositions- co-ordinates of the layout to start with. By default, a random layout is used (kwarg)iterations- Number of iterations we apply the forces (kwarg)abstols- Absolute tolerance for convergence of stress (kwarg)reltols- Relative tolerance for convergence of stress (kwarg)abstolx- Absolute tolerance for convergence of layout (kwarg)
positions - co-ordinates of nodes in the layout
A user can move between iterations using a Layout object.
using LightGraphs
using NetworkLayout:Stress
g = CompleteGraph(10)
a = adjacency_matrix(g) # generates a sparse adjacency matrix
network = layout(a,2) # generate 2D layoutUsing Iterator :
g = CompleteGraph(10)
δ = adjacency_matrix(g)
startpositions=rand(Point{3, Float64}, size(δ,1))
iter = Layout(δ, Point{3,Float64}; startpositions=startpositions)
state = start(iter)
while !done(iter, state)
iter, state = next(iter, state)
end
iter.positions
The image shows a LightGraphs.CompleteGraph(10) object layout using Stress Algorithm.
Uses the technique of Spectral Graph Drawing, which is an under-appreciated method of graph layouts; easier, simpler, and faster than the more common spring-based methods. Original code taken from PlotRecipes.jl
Module Name : Spectral
layout(adjacency_matrix; node_weights, kw...)adjacency_matrix- Adjacency Matrix in dense/sparse formatnode_weights- weights for different nodes (kwarg)
positions - co-ordinates of nodes in the layout
using LightGraphs
using NetworkLayout:Spectral
g = CompleteGraph(10)
a = adjacency_matrix(g) # generates a sparse adjacency matrix
network = layout(a) # generate 3D layout
The image shows a LightGraphs.CompleteGraph(10) object layout by Spectral Algorithm.
Position nodes on a circle. Original code taken from GraphPlot.jl
Module Name : Circular
layout(adjacency_matrix)adjacency_matrix- Adjacency Matrix in dense/sparse format
positions - co-ordinates of nodes in the layout
using LightGraphs
using NetworkLayout:Circular
g = CompleteGraph(30)
a = adjacency_matrix(g) # generates a sparse adjacency matrix
network = layout(a) # generate 2D layout
The image shows a LightGraphs.CompleteGraph(10) object layout using Circular Algorithm.
Position nodes in concentric circles. Original code taken from GraphPlot.jl
Module Name : Shell
layout(adjacency_matrix;nlist)adjacency_matrix- Adjacency Matrix in dense/sparse formatnlist- Shell-wise separation of nodes (kwarg)
positions - co-ordinates of nodes in the layout
using LightGraphs
using NetworkLayout:Shell
g = CompleteGraph(30)
n = Array(Vector{Int},2)
n[1] = [1:15]
n[2] = [16:30]
a = adjacency_matrix(g) # generates a sparse adjacency matrix
network = layout(a,nlist=n) # generate 2D layout
This figure shows a LightGraphs.CompleteGraph(30) object in 2 shells.
The iterative algorithms have been benchmarked using 3 different graphs: LightGraphs.WheelGraph(10), LightGraphs.WheelGraph(100) and jagmesh1. The number of iterations is fixed on 100. The following graph is obtained which shows SFDP to be the fastest in a general scenario, but Stress Algorithm is faster when the number of edges per graph is comparatively less, as in jagmesh1.
NOTE : All screenshots are generated using NetworkViz.jl, ThreeJS.jl and Escher.jl. The plot used is generated using Gadfly.jl