Graphs in Julia with LightGraphs¶

Structure, abstractions and algorithms¶

Mathieu Besançon
JuliaGraphs

Twitter for live-complaints: @matbesancon

Re-using / citing the materials:

First things first, logistics¶

Follow the slides at https://matbesancon.github.io/slides/JuliaNantes/Graphs.html
Repository at https://github.com/matbesancon/JuliaNantesWorkshop

In [1]:

# Run this notebook in the exact same environment
import Pkg
Pkg.activate("$(@__DIR__)..")
Pkg.instantiate()

  Updating registry at `~/.julia/registries/General`
  Updating git-repo `https://github.com/JuliaRegistries/General.git`

In [2]:

using LightGraphs
using GraphPlot: gplot
import Random
import MetaGraphs
using Colors: @colorant_str
using SimpleWeightedGraphs: SimpleWeightedGraph

What is a graph?¶

Vertices and edges:
$G = (V, E)$
$V = \{1, 2, 3, ...\}$
$E = \{(1,2), (1,3), ...\}$

Let's get to implementation¶

Where things go wrong$^{TM}$

How would you go about implementing a graph in your favourite programming language?

First take, dense adjacency matrix:

Easy, but doesn't scale well.
Graphs are usually sparse.

Sparse matrix, scales better:

using SparseArrays

graph2 = spzeros(Int, 3, 3)
graph2[1,2] = graph2[1,3] = 1

Adjacency list, redundancy for faster lookup, faster vertex insertion.

graph3 = [Int[] for _ in 1:3]
push!(graph3[1], 2, 3)

Implementation is hard¶

Getting things right
Match all (many) use cases
Staying flexible

Slightly different use cases $\Rightarrow$ must re-write all algorithms?

What's LightGraphs take on this?¶

Define a graph as an expected behaviour, not an implementation
Build algorithms assuming only this behaviour

Graph abstraction¶

Say you define a type G which you want to be a graph, the following methods are required:

LightGraphs.edges(::G)
LightGraphs.edgetype(::G)
LightGraphs.is_directed(::Type{G})
LightGraphs.ne(::G)
LightGraphs.nv(::G)
LightGraphs.vertices(::G)

LightGraphs.outneighbors(::G, v)
LightGraphs.inneighbors(::G, v)
LightGraphs.has_vertex(::G, v)

LightGraphs.has_edge(::G, i, j)

... And that's it

Quick tour of graph types¶

Simple(Di)Graph¶

Sane default, scales well.

In [3]:

Random.seed!(40)
sg = SimpleDiGraph(5)
add_edge!(sg, 2, 3)
add_edge!(sg, 1, 3)
add_edge!(sg, 4, 3)
add_edge!(sg, 4, 5)
gplot(sg, nodelabel = vertices(sg))

Out[3]:

Standard graphs¶

In [4]:

Random.seed!(42)
wg = LightGraphs.WheelGraph(7)
gplot(wg, nodelabel = vertices(wg))

Out[4]:

In [5]:

Random.seed!(42)
sdg = LightGraphs.StarDiGraph(10)
gplot(sdg, nodelabel = vertices(sdg))

Out[5]:

Random graph generators¶

In [6]:

Random.seed!(30)
ba = barabasi_albert(10, 3, 3)
gplot(ba, nodelabel = vertices(ba))

Out[6]:

MetaGraphs¶

Graphs with meta-information on edges and vertices. Add any arbitrary field (like a Dict) to edges.

In [7]:

meta_wheel = MetaGraphs.MetaGraph(wg)

# add information on vertices
MetaGraphs.set_prop!(meta_wheel, 1, :central, true)
for j in 2:nv(meta_wheel)
    MetaGraphs.set_prop!(meta_wheel, j, :central, false)
end

In [8]:

Random.seed!(42)
nodecolors = [MetaGraphs.get_prop(meta_wheel, i, :central) ? colorant"red" : colorant"blue" for i in vertices(meta_wheel)]

gplot(meta_wheel, nodelabel = vertices(meta_wheel), nodefillc = nodecolors)

Out[8]:

In [9]:

# add information on edges
for e in edges(meta_wheel)
    if src(e) == 1
        MetaGraphs.set_prop!(meta_wheel, e, :type, "rayon")
    else
        MetaGraphs.set_prop!(meta_wheel, e, :type, "perimeter")
    end
end

ewidth = [MetaGraphs.get_prop(meta_wheel, e, :type) == "rayon" ? 0.6 : 2.5 for e in edges(meta_wheel)];

In [10]:

Random.seed!(42)

gplot(meta_wheel, nodelabel = vertices(meta_wheel), nodefillc = nodecolors, edgelinewidth = ewidth)

Out[10]:

SimpleWeightedGraphs¶

In many contexts, only weights associated with edges is required: meet SimpleWeightedGraphs.

In [11]:

g = SimpleWeightedGraph(3)
# add edge src ⇒ dst w
add_edge!(g, 1, 2, 0.5)
add_edge!(g, 2, 3, 0.8)
add_edge!(g, 1, 3, 2.0)
g

Out[11]:

{3, 3} undirected simple Int64 graph with Float64 weights

Batteries included: essential algorithms¶

Search¶

In [12]:

Random.seed!(42)
gplot(wg, nodelabel = vertices(wg))

Out[12]:

In [13]:

Random.seed!(42)
order = LightGraphs.dfs_parents(wg, 1)
gplot(wg, nodelabel = order)

Out[13]:

In [14]:

Random.seed!(42)
order = LightGraphs.bfs_parents(wg, 1)
gplot(wg, nodelabel = order)

Out[14]:

Minimum Spanning Tree¶

Kruskal & Prim algorithms

In [15]:

Random.seed!(30)
ba = barabasi_albert(10, 3, 3)

st = kruskal_mst(ba)
edge_width = [e ∈ st ? 2.5 : 1.0 for e in edges(ba)]
edge_color = [e ∈ st ? colorant"red" : colorant"lightgray" for e in edges(ba)]

gplot(ba, nodelabel = vertices(ba), edgelinewidth = edge_width, edgestrokec = edge_color)

Out[15]:

NB: when available, uses the edge weights (for SimpleWeightedGraph for instance)

PageRank¶

In [16]:

Random.seed!(30)

ranks = pagerank(ba)
gplot(ba, nodelabel = vertices(ba), nodesize = ranks)

Out[16]:

Applications of LightGraphs¶

Source: Graph interfaces in JuliaGraphs M. Besançon, J. Fairbanks, JuliaCon 2018, London

Other noteworthy applications¶

TrafficAssignment.jl: equilibrium of user flow in road traffic problems
PorousMaterials.jl: materials science
NetworkDynamics.jl: differential equations and system dynamics on graphs
Mamba.jl: Markov Chain Monte Carlo

Demo time¶

Let us create a new graph type, our beloved WheelGraph.

What information is needed? Only the number of vertices.

In [17]:

"""
A custom type to store wheel graphs.
"""
struct WGraph <: AbstractGraph{Int}
    nv::Int
end

LightGraphs.edgetype(::WGraph) = Edge{Int}
LightGraphs.is_directed(::WGraph) = false
LightGraphs.is_directed(::Type{WGraph}) = false
LightGraphs.nv(g::WGraph) = g.nv
LightGraphs.ne(g::WGraph) = (nv(g)-1) * 2
LightGraphs.vertices(g::WGraph) = 1:nv(g)

In [18]:

function LightGraphs.edges(g::WGraph)
    edges = Vector{Edge{Int}}()
    # add inner edges
    for j in 1:nv(g)-1
        push!(edges, Edge(1, j+1))
    end
    # add perimeter
    for j in 2:nv(g)-1
        push!(edges, Edge(j, j+1))        
    end
    push!(edges, Edge(2, nv(g)))
    return edges
end

In [19]:

function LightGraphs.outneighbors(g::WGraph, v)
    if v == 1
        return collect(2:nv(g))
    end
    if v == 2
        return [1, 3, nv(g)]
    end
    if v == nv(g)
        return [1, 2, nv(g)-1]
    end
    return [1, v-1, v+1]
end

LightGraphs.inneighbors(g::WGraph, v) = outneighbors(g, v)

In [20]:

LightGraphs.has_vertex(g::WGraph, v) = v <= nv(g)

function LightGraphs.has_edge(g::WGraph, v1, v2)
    if v1 > v2
        return has_edge(g, v2, v1)
    end
    if !has_vertex(g, v1) || !has_vertex(g, v2)
        return false
    end
    # rayon
    if v1 == 1 && v2 > 1
        return true
    end
    # perimeter
    if v2 == v1 + 1
        return true
    end
    # boundary conditions
    if v1 == 2 && v2 == nv(g)
        return true
    end
    return false
end

In [21]:

wg = LightGraphs.WheelGraph(7)
Random.seed!(42)
gplot(wg, nodelabel = vertices(wg))

Out[21]:

In [22]:

wg2 = WGraph(7)
Random.seed!(42)
gplot(wg2, nodelabel = vertices(wg2))

Out[22]:

In [23]:

ranks = pagerank(wg2)
Random.seed!(42)
gplot(wg2, nodelabel = vertices(wg2), nodesize = ranks)

Out[23]:

Reading more¶

LightGraphs documentation for the abstract graph interface
Defining a graph type based on any matrix: https://matbesancon.github.io/post/2018-08-17-abstract_graph/

Getting help:

Julia Slack, #graphs channel
Julia Discourse forum
Some issues? Let the developers know: http://github.com/JuliaGraphs/LightGraphs.jl

Homework¶

Try it out
Define your own graph! Examples: CompleteGraph, PathGraph