# 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

## 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)

capacities[1,2] = 5.
capacities[2,4] = 3.
capacities[1,3] = 2.
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]:

## 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

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/