dummy-link

NetworkLayout

Layout algorithms for graphs and trees in pure Julia.

Readme

NetworkLayout.jl

Layout algorithms for graphs and trees in pure Julia.

Coverage Status

Linux, OSX : Build Status

Windows : Build status

Algorithms

Scalable Force Directed Placement

Spring-Electric Force Directed Placement algorithm as explained in Efficient and High Quality Force-Directed Graph Drawing by Yifan Hu.

Module Name : SFDP

Usage

layout(adjacency_matrix,dimension;startpostitions,tol,C,K,iterations)
arguments
  • 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)
returns

positions - co-ordinates of nodes in the layout

iterator

A user can move between iterations using a Layout object.

Example

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

sfdp

The image shows a LightGraphs.WheelGraph(10) object layout generated by SFDP Algorithm.

Buchheim Tree Drawing

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

Usage

layout(adjacency_list; nodesize)
arguments
  • adjacency_list - adjacency list that represents the tree
  • nodesize - sizes of nodes (used to position the nodes) (kwarg)
returns
  • positions - co-ordinates of the layout

Example

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

tree

The image shows a LightGraphs.BinaryTree(4) object layout by Buchheim Algorithm.

Spring/Repulsion Model

Spring/Repulsion model of Fruchterman and Reingold (1991). Original code taken from GraphLayout.jl

Module Name : Spring

Usage

layout(adjacency_matrix,dimension;startpositions,C,iterations,initialtemp)
arguments
  • 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)
returns

positions - co-ordinates of nodes in the layout

iterator

A user can move between iterations using a Layout object.

Example

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

spring

The image shows a LightGraphs.WheelGraph(10) object layout generated by Spring Algorithm.

Stress Majorization

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

Usage

layout(δ,dimension;startpositions,weights,iterations,abstols,reltols,abstolx)
arguments
  • δ - 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)
returns

positions - co-ordinates of nodes in the layout

iterator

A user can move between iterations using a Layout object.

Example

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

stress

The image shows a LightGraphs.CompleteGraph(10) object layout using Stress Algorithm.

Spectral Layout 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

Usage

layout(adjacency_matrix; node_weights, kw...)
arguments
  • adjacency_matrix - Adjacency Matrix in dense/sparse format
  • node_weights - weights for different nodes (kwarg)
returns

positions - co-ordinates of nodes in the layout

Example

using LightGraphs
using NetworkLayout:Spectral
g = CompleteGraph(10)
a = adjacency_matrix(g) # generates a sparse adjacency matrix
network = layout(a) # generate 3D layout

spectral

The image shows a LightGraphs.CompleteGraph(10) object layout by Spectral Algorithm.

Circular Layout Algorithm

Position nodes on a circle. Original code taken from GraphPlot.jl

Module Name : Circular

Usage

layout(adjacency_matrix)
arguments
  • adjacency_matrix - Adjacency Matrix in dense/sparse format
returns

positions - co-ordinates of nodes in the layout

Example

using LightGraphs
using NetworkLayout:Circular
g = CompleteGraph(30)
a = adjacency_matrix(g) # generates a sparse adjacency matrix
network = layout(a) # generate 2D layout

circular

The image shows a LightGraphs.CompleteGraph(10) object layout using Circular Algorithm.

Shell Layout Algorithm

Position nodes in concentric circles. Original code taken from GraphPlot.jl

Module Name : Shell

Usage

layout(adjacency_matrix;nlist)
arguments
  • adjacency_matrix - Adjacency Matrix in dense/sparse format
  • nlist - Shell-wise separation of nodes (kwarg)
returns

positions - co-ordinates of nodes in the layout

Example

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

shell

This figure shows a LightGraphs.CompleteGraph(30) object in 2 shells.

Benchmarks

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.

bench

NOTE : All screenshots are generated using NetworkViz.jl, ThreeJS.jl and Escher.jl. The plot used is generated using Gadfly.jl

First Commit

07/25/2016

Last Touched

about 1 month ago

Commits

88 commits