I wanted to play with some graphs (as in graph theory) and noticed two prominent Julia packages: LightGraphs (and the whole JuliaGraphs ecosystem) and SimpleGraphs. The latter only being available via cloning the github repository, but has been updated for Julia 1.0.
Just wondered if people had thoughts on which is better to use for a short-term project.
Thanks!
I’m pretty biased, but I think you might find that LightGraphs has more functionality built in. 
Compare the docs / features and see which one meets your needs better.
Thanks! I just didn’t know if there was a solid reason for preferring SimpleGraphs over the more developed LightGraphs. A doc comparison is sound advice.
One big difference is that SimpleGraphs apparently allows you to index vertices with any type. (I say “apparently” because I haven’t actually tried it.) LightGraphs uses integers for vertex indices. Not only that, but the indices in LightGraphs must be one-based and contiguous.
The benefit of that apparent (in theory, but not generally in practice) drawback is that LightGraphs is significantly faster than other graph packages out there and can scale to very large graphs. We haven’t done explicit testing against SimpleGraphs, but just looking at the data structures that are being used I can tell we scale to larger graphs (since it takes us at most 40 8 bytes to store up to 2^64 vertices, where SimpleGraphs records each vertex in a set) (edit: it’s a bit more complicated than this, and so not accurate - the real space savings comes in when you start adding edges), and when the SimpleGraphs neighborhood optimizations are disabled, our neighbors checks (which are important for things that rely on BFS) are faster (O(deg(v)) vs O(|V|)).
I say “in practice” because there are few applications that can’t actually limit themselves to 1:n vertices; and with MetaGraphs, most of this problem is mooted (at the expense of some more time and space complexity).
Still, it may be that your specific problem requires the combination of advantages that SimpleGraphs provides over LightGraphs. If that turns out to be the case, I’d love to hear about it (via GitHub issue over in LightGraphs) so we can explore how to make LG even better.
Oh wow, I hadn’t seen SimpleGraphs. I had been looking for something compiler-like dependencies. I could use LightGraphs, but then I’d have to worry about tracking the bijective map between Symbols and Ints. There’s no “bimap” package I can find, so this was going to be a big distraction from my main goal.
Thank you for the pointer!
Not to say that it’s a better solution to your specific problem, but that’s what MetaGraphs is designed (in part) to do.
It still seemed pretty manual though, is there a way to have it abstract away the underlying Int representation?
Depends on what, specifically, you need to do with the metadata. You can filter the graph by any of the vertex properties, for example, and need not concern yourself with the underlying int representation. Here’s a small example:
julia> g = PathDiGraph(5)
{5, 4} directed simple Int64 graph
julia> m = MetaDiGraph(g)
{5, 4} directed Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)
julia> vnames = ["red", "red", "red", "blue", "blue"];
julia> for (i, v) in enumerate(vertices(m)) # technically not needed, but we're trying to avoid using vertices as ints
set_prop!(m, v, :name, vnames[i])
end
julia> redverts = filter_vertices(m, :name, "red");
julia> m2 = m[redverts] # induce the subgraph of only red vertices
{3, 2} directed Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)
julia> for v in vertices(m2)
println(get_prop(m2, v, :name))
end
red
red
red
Biggest thing I need is to “postwalk” a program and add a directed edge when I see an assignment. Something like
addedge!(g, :a, :b)
without specifying the number of vertices in advance would be really great.
You can do half of this*, and it’s particularly fast if the labels are indexed properties:
julia> g = Graph(5) # no edges
{5, 0} undirected simple Int64 graph
julia> mg = MetaGraph(g)
{5, 0} undirected Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)
julia> for v in vertices(mg)
set_prop!(mg, v, :name, 'a' + v - 1)
end
julia> set_indexing_prop!(mg, :name)
Set(Symbol[:name])
julia> add_edge!(mg, mg['a',:name], mg['b',:name]) # add an edge between vertex 'a' and vertex 'b'
true
julia> mg
{5, 1} undirected Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)
julia> has_edge(mg, mg['a',:name], mg['b',:name])
true
julia> has_edge(mg, mg['a',:name], mg['c',:name])
false
*if you really don’t know the number of vertices beforehand, you can always use add_vertex! / add_vertices!, but you’ll have a performance hit.
@anon94023334 Thank you for your help with this! I think I kind of have it working. I need to find dependencies in a model like this:
julia> lda
@model (α, N, K, V, η) begin
M = length(N)
β ~ Dirichlet(repeat([η], V)) |> iid(K)
θ ~ Dirichlet(repeat([α], K)) |> iid(M)
z ~ For(1:M) do m
Categorical(θ[m]) |> iid(N[m])
end
w â©Ş For(1:M) do m
For(1:N[m]) do n
Categorical(β[(z[m])[n]])
end
end
end
Using your example as a template, I can define
using LightGraphs
using MetaGraphs
function graph(m::Model)
vars = variables(m)
g = MetaDiGraph(length(vars))
for (n,v) in enumerate(vars)
set_prop!(g, n, :name, v)
end
set_indexing_prop!(g, :name)
postwalk(m.body) do x
if @capture(x,v_~d_) || @capture(x,v_â©Şd_) || @capture(x,v_=d_)
for rhs in findsubexprs(d,vars)
add_edge!(g,(g[v,:name],g[rhs,:name]))
end
else x
end
end
g
end
Then to find dependencies…
julia> g = graph(lda)
{10, 14} directed Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)
julia> [(g[e.src,:name] => g[e.dst,:name]) for e in edges(g)]
14-element Array{Pair{Symbol,Symbol},1}:
:w => :N
:w => :M
:w => :z
:w => :β
:M => :N
:z => :N
:z => :M
:z => :θ
:β => :K
:β => :V
:β => :η
:θ => :α
:θ => :M
:θ => :K