Follow the slides at https://matbesancon.github.io/slides/JuliaNantes/Graphs.html
Repository at https://github.com/matbesancon/JuliaNantesWorkshop
# 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`
using LightGraphs
using GraphPlot: gplot
import Random
import MetaGraphs
using Colors: @colorant_str
using SimpleWeightedGraphs: SimpleWeightedGraph
Vertices and edges:
$G = (V, E)$
$V = \{1, 2, 3, ...\}$
$E = \{(1,2), (1,3), ...\}$
Where things go wrong$^{TM}$
How would you go about implementing a graph in your favourite programming language?
First take, dense adjacency matrix:
graph1 = [
0 1 1
0 0 0
0 0 0
]
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)
Slightly different use cases $\Rightarrow$ must re-write all algorithms?
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
Sane default, scales well.
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))
Random.seed!(42)
wg = LightGraphs.WheelGraph(7)
gplot(wg, nodelabel = vertices(wg))
Random.seed!(42)
sdg = LightGraphs.StarDiGraph(10)
gplot(sdg, nodelabel = vertices(sdg))
Random.seed!(30)
ba = barabasi_albert(10, 3, 3)
gplot(ba, nodelabel = vertices(ba))
Graphs with meta-information on edges and vertices. Add any arbitrary field (like a Dict
) to edges.
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
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)
# 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)];
Random.seed!(42)
gplot(meta_wheel, nodelabel = vertices(meta_wheel), nodefillc = nodecolors, edgelinewidth = ewidth)
In many contexts, only weights associated with edges is required: meet SimpleWeightedGraphs.
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
{3, 3} undirected simple Int64 graph with Float64 weights
Random.seed!(42)
gplot(wg, nodelabel = vertices(wg))
Random.seed!(42)
order = LightGraphs.dfs_parents(wg, 1)
gplot(wg, nodelabel = order)
Random.seed!(42)
order = LightGraphs.bfs_parents(wg, 1)
gplot(wg, nodelabel = order)
Kruskal & Prim algorithms
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)