18

2

7

8

# NetworkLayout.jl

Layout algorithms for graphs and trees in pure Julia.

Linux, OSX :

Windows :

## 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)
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

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
[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

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)
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.

### 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)
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.

### 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
``````

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
``````

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
``````

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`.

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

07/25/2016

28 days ago

90 commits