Graph interfaces, bespoke graphs for every occasion¶

Mathieu Besançon, James Fairbanks

Outline¶

Why LightGraphs?
LightGraphs scope
Live code!
Conclusion

Why LightGraphs?¶

Graphs are fun... and useful.
Need for a simple, extensible graph library in Julia.
Watch Seth and James JuliaCon17 talk for motivation

Graph applications¶

Social interactions
Logistics

Less boring?¶

LightGraphs scope¶

LightGraphs' job is to...

Define the core interface: what does a type need to be a graph?
Implement essential algorithms on types implementing the interface

Core interface¶

Abstract graph type AbstractGraph

Some methods required on graphs f(graph):

LightGraphs.edges
LightGraphs.edgetype
LightGraphs.is_directed
LightGraphs.ne
LightGraphs.nv
LightGraphs.vertices

Methods required on nodes f(graph,node):

LightGraphs.outneighbors
LightGraphs.inneighbors
LightGraphs.has_vertex

Methods required for edges f(graph, edge):

LightGraphs.has_edge

Defining one own edge type:

Base.reverse
LightGraphs.dst
LightGraphs.src

Essential algorithms¶

In [1]:

using LightGraphs

g = CompleteBipartiteGraph(5,6)

Out[1]:

{11, 30} undirected simple Int64 graph

In [2]:

# neighbors of the 3rd vertex
neighbors(g, 3)

Out[2]:

6-element Array{Int64,1}:
  6
  7
  8
  9
 10
 11

In [3]:

# Dijkstra's shortest path from vertex 3 to any other
dijkstra_shortest_paths(g,3)

Out[3]:

LightGraphs.DijkstraState{Int64,Int64}([6, 6, 0, 6, 6, 3, 3, 3, 3, 3, 3], [2, 2, 0, 2, 2, 1, 1, 1, 1, 1, 1], Array{Int64,1}[Int64[], Int64[], Int64[], Int64[], Int64[], Int64[], Int64[], Int64[], Int64[], Int64[], Int64[]], [6, 6, 1, 6, 6, 1, 1, 1, 1, 1, 1], Int64[])

In [4]:

# Kruskal min-cost spanning tree
kruskal_mst(g)

Out[4]:

10-element Array{LightGraphs.SimpleGraphs.SimpleEdge,1}:
 Edge 1 => 6 
 Edge 5 => 11
 Edge 5 => 10
 Edge 5 => 9 
 Edge 5 => 8 
 Edge 5 => 7 
 Edge 5 => 6 
 Edge 4 => 11
 Edge 3 => 11
 Edge 2 => 11

In [5]:

pagerank(g)

Out[5]:

11-element Array{Float64,1}:
 0.0992624
 0.0992624
 0.0992624
 0.0992624
 0.0992624
 0.083948 
 0.083948 
 0.083948 
 0.083948 
 0.083948 
 0.083948

Standing on other packages' shoulders¶

In [6]:

using GraphPlot

In [7]:

gplot(g, layout=GraphPlot.circular_layout , nodelabel=1:11)

Out[7]:

Flow algorithms like a charm¶

In [8]:

import LightGraphsFlows
const LGF = LightGraphsFlows;

flow_graph = DiGraph(4)
capacities = zeros(4,4)

add_edge!(flow_graph, 1, 2)
capacities[1,2] = 5.
add_edge!(flow_graph, 2, 4)
capacities[2,4] = 3.
add_edge!(flow_graph, 1, 3)
capacities[1,3] = 2.
add_edge!(flow_graph, 3, 4)
capacities[3,4] = 3.;

In [9]:

gplot(flow_graph, nodelabel = 1:4)

Out[9]:

In [10]:

flow_value, flow_mat = LGF.maximum_flow(flow_graph, 1, 4, capacities)
flow_mat

Out[10]:

4×4 Array{Float64,2}:
  0.0   3.0   2.0  0.0
 -3.0   0.0   0.0  3.0
 -2.0   0.0   0.0  2.0
  0.0  -3.0  -2.0  0.0

In [11]:

# flow in lexicographic order
flow_list = [flow_mat[1,2],flow_mat[1,3],flow_mat[2,4],flow_mat[3,4]]
gplot(flow_graph, nodelabel = 1:4,edgelabel = flow_list)

Out[11]:

A graph type for every occasion¶

What's the simplest way to build a graph?¶

Adjacency matrix $M_{ij}$ $$M_{ij} = \begin{cases} 1, & \mbox{if edge (i $\rightarrow$ j) exists} \\ 0 & \mbox{otherwise}\end{cases}$$

One matrix contains all the information
Undirected graph == symmetric matrix
Accessing, modifying edges is quick

To follow along $\rightarrow$ http://bit.do/graphdocs

Wrap-up¶

Design specialized graph types for your needs, you know best!
Define a couple functions describing behavior
Use the JuliaGraphs ecosystem for free, build on top

React, complain, contribute:

github.com/JuliaGraphs
Discourse
Slack #graphs channel

Bonus¶

One graph type to rule them all

In [24]:

struct GraphMatrix{MT<:AbstractMatrix{Bool}} <: LightGraphs.AbstractGraph{Int64}
    m::MT
    is_directed::Bool
end

# methods on the graph
is_directed(g::GraphMatrix) = g.is_directed
reverse(g::GraphMatrix) = is_directed(g) ? GraphMatrix(m',true) : g
edgetype(::GraphMatrix) = LightGraphs.SimpleGraphs.SimpleEdge{Int64}
ne(g::GraphMatrix) = is_directed(g) ? sum(g.m) : div(sum(g.m),2)
nv(g::GraphMatrix) = size(g.m)[1]

vertices(g::GraphMatrix) = 1:nv(g)

function edges(g::GraphMatrix)
    n = nv(g)
    if g.is_directed
        return (LightGraphs.SimpleGraphs.SimpleEdge(i,j) for i in 1:n for j in 1:n if g.m[i,j])
    else
        return (LightGraphs.SimpleGraphs.SimpleEdge(i,j) for i in 1:n for j in i+1:n if g.m[i,j])
    end
end

Out[24]:

edges (generic function with 4 methods)

  13.047 ns (0 allocations: 0 bytes)
that's better.

Links & sources¶

_{^{Photo by Fancycrave on Unsplash}}
_{^{https://www.pexels.com/photo/close-up-photography-of-yellow-green-red-and-brown-plastic-cones-on-white-lined-surface-163064/}}
_{^{https://www.pexels.com/photo/firework-new-year-s-eve-rocket-3893/}}
_{^{https://www.pexels.com/photo/blue-white-orange-and-brown-container-van-163726/}}