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 graph
• dimension - dimension in which the layouting code has to be generated. dimension can be an integer specifying the dimension or a Point type, eg. Point3f0 which 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 layout

Using 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 tree
• nodesize - 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 graph
• dimension - dimension in which the layouting code has to be generated. dimension can be an integer specifying the dimension or a Point type, eg. Point3f0 which 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 layout

Using 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. dimension can be an integer specifying the dimension or a Point type, eg. Point3f0 which 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 layout

Using 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 format
• node_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 format
• nlist - 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