# Leveraging special graph shapes in Graphs

Let the compiler do the work

In a previous post, we pushed the boundaries of the Graphs.jl abstraction to see how conforming the algorithms are to the declared interface, noticing some implied assumptions that were not stated. This has led to the development of VertexSafeGraphs.jl and soon to some work on Graphs.jl itself.

Another way to push the abstraction came out of the
JuliaNantes workshop:
leveraging some special structure of graphs to optimize some specific operations.
A good parallel can be established be with the `LinearAlgebra`

package from
Julia Base, which defines special matrices such as `Diagonal`

and `Symmetric`

and `Adjoint`

, implementing the `AbstractMatrix`

interface but without storing
all the entries.

## A basic example

Suppose you have a path graph or chain, this means any vertex is connected to
its predecessor and successor only, except the first and last vertices.
Such graph can be represented by a `Graphs.SimpleGraph`

:

```
import Graphs
const LG = Graphs
g = LG.path_graph(10)
for v in 1:9
@assert LG.has_edge(g, v, v+1) # should not explode
end
```

This is all fine, but we are encoding in an adjacency list some structure that we are aware of from the beginning. If you are used to thinking in such way, “knowing it from the beginning” can be a hint that it can be encoded in terms of types and made zero-cost abstractions. The real only runtime information of a path graph (which is not available before receiving the actual graph) is its size $n$. The only thing to do is implement the handful of methods from the Graphs interface.

```
struct PathGraph{T <: Integer} <: LG.AbstractGraph{T}
nv::Int
end
LG.edgetype(::PathGraph) = LG.Edge{Int}
LG.is_directed(::Type{<:PathGraph}) = false
LG.nv(g::PathGraph) = g.nv
LG.ne(g::PathGraph) = LG.nv(g) - 1
LG.vertices(g::PathGraph) = 1:LG.nv(g)
LG.edges(g::PathGraph) = [LG.Edge(i, i+1) for i in 1:LG.nv(g)-1]
LG.has_vertex(g::PathGraph, v) = 1 <= v <= LG.nv(g)
function LG.outneighbors(g::PathGraph, v)
LG.has_vertex(g, v) || return Int[]
LG.nv(g) > 1 || return Int[]
if v == 1
return [2]
end
if v == LG.nv(g)
return [LG.nv(g)-1]
end
return [v-1, v+1]
end
LG.inneighbors(g::PathGraph, v) = outneighbors(g, v)
function LG.has_edge(g::PathGraph, v1, v2)
if !has_vertex(g, v1) || !has_vertex(g, v2)
return false
end
return abs(v1-v2) == 1
end
```

## A more striking example

`PathGraph`

may leave you skeptical as to the necessity of such machinery, and
you are right. A more interesting example might be complete graphs. Again for
these, the only required piece of information is the number of vertices,
which is a lot lighter than storing all the possible edges. We can make a
parallel with FillArrays.jl,
implicitly representing the entries of a matrix.

### Use cases

The question of when to use a special-encoded graph is quite open. This type can be used with all functions assuming a graph-like behaviour, but is immutable, it is therefore not the most useful when you construct these special graphs as a starting point for an algorithm mutating them.

## Performance

As of now, simple benchmarks will show that the construction of special graphs
is cheaper than the creation of the adjacency lists for `Graphs.SimpleGraph`

.
Actually using them for “global” algorithms is another story:

```
function f(G, nv)
g = G(nv)
pr = pagerank(g)
km = kruskal_mst(g)
return (g, pr, km)
end
```

Trying to benchmark this function on `PathGraph`

shows it is way worse than
the corresponding SimpleGraph structure, the `CompleteGraph`

implementation is
about the same order of allocations and runtime as its list-y counterpart.

The suspect for the lack of speedup is the `edges`

operation, optimized with a custom edge
iterator in Graphs and returning a heap-allocated `Array`

in SpecialGraphs
for now. Taking performance seriously will requiring tackling this before
anything else. Other opportunities for optimization may include returning
StaticArrays and
re-implementing optional methods such as `Graphs.adjacency_matrix`

using specialized matrix types.

## Conclusion and further reading

The work on these graph structures is happening in SpecialGraphs.jl, feel free to file issues and submit pull requests. Also check out the matrix-based graph prototype in this post.