# NetworkLayout.jl

Layout algorithms for graphs and trees in pure Julia.

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

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

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

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

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