Graph interfaces, bespoke graphs for every occasion

Mathieu Besançon, James Fairbanks

Outline

  1. Why LightGraphs?
  2. LightGraphs scope
  3. Live code!
  4. 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]:
1 2 3 4 5 6 7 8 9 10 11

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]:
1 2 3 4
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]:
3.0 2.0 3.0 2.0 1 2 3 4

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.

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/