07/25/2016

23 days ago

77 commits

Layout algorithms for graphs and trees in pure Julia.

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