# LightGraphs vs. SimpleGraphs

**URL:** <https://discourse.julialang.org/t/lightgraphs-vs-simplegraphs/14643>\
**Category:** General Usage\
**Tags:** package\
**Created:** [September 6, 2018, 9:30pm UTC](https://discourse.julialang.org/t/lightgraphs-vs-simplegraphs/14643 "2018-09-06T21:30:51Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![mstobb](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mstobb/32/1671_2.png) [@mstobb](https://discourse.julialang.org/u/mstobb)\
**Post date:** [September 6, 2018, 9:30pm UTC](https://discourse.julialang.org/t/lightgraphs-vs-simplegraphs/14643/1 "2018-09-06T21:30:51Z")

</div>

I wanted to play with some graphs (as in graph theory) and noticed two prominent Julia packages: [LightGraphs](http://juliagraphs.github.io) (and the whole JuliaGraphs ecosystem) and [SimpleGraphs](http://github.com/scheinerman/SimpleGraphs.jl). 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!

---

<div class="post-metadata">

**Author:** ![anon94023334](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@anon94023334](https://discourse.julialang.org/u/anon94023334)\
**Post date:** [September 6, 2018, 11:10pm UTC](https://discourse.julialang.org/t/lightgraphs-vs-simplegraphs/14643/2 "2018-09-06T23:10:22Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![mstobb](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mstobb/32/1671_2.png) [@mstobb](https://discourse.julialang.org/u/mstobb)\
**Post date:** [September 7, 2018, 1:13am UTC](https://discourse.julialang.org/t/lightgraphs-vs-simplegraphs/14643/3 "2018-09-07T01:13:06Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![anon94023334](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@anon94023334](https://discourse.julialang.org/u/anon94023334)\
**Post date:** [September 7, 2018, 6:16pm UTC](https://discourse.julialang.org/t/lightgraphs-vs-simplegraphs/14643/4 "2018-09-07T18:16:00Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![cscherrer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cscherrer/32/7631_2.png) [@cscherrer](https://discourse.julialang.org/u/cscherrer)\
**Post date:** [September 7, 2018, 6:32pm UTC](https://discourse.julialang.org/t/lightgraphs-vs-simplegraphs/14643/5 "2018-09-07T18:32:48Z")

</div>

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 `Symbol`s and `Int`s. 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!

---

<div class="post-metadata">

**Author:** ![anon94023334](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@anon94023334](https://discourse.julialang.org/u/anon94023334)\
**Post date:** [September 7, 2018, 7:19pm UTC](https://discourse.julialang.org/t/lightgraphs-vs-simplegraphs/14643/6 "2018-09-07T19:19:10Z")

</div>

> [@cscherrer](#):
>
> I’d have to worry about tracking the bijective map between `Symbol` s and `Int` s.

Not to say that it’s a better solution to your specific problem, but that’s what MetaGraphs is designed (in part) to do.

---

<div class="post-metadata">

**Author:** ![cscherrer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cscherrer/32/7631_2.png) [@cscherrer](https://discourse.julialang.org/u/cscherrer)\
**Post date:** [September 8, 2018, 1:37am UTC](https://discourse.julialang.org/t/lightgraphs-vs-simplegraphs/14643/7 "2018-09-08T01:37:11Z")

</div>

> [@anon94023334](#):
>
> 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?

---

<div class="post-metadata">

**Author:** ![anon94023334](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@anon94023334](https://discourse.julialang.org/u/anon94023334)\
**Post date:** [September 8, 2018, 1:56am UTC](https://discourse.julialang.org/t/lightgraphs-vs-simplegraphs/14643/8 "2018-09-08T01:56:02Z")

</div>

> [@cscherrer](#):
>
> 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
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

```

---

<div class="post-metadata">

**Author:** ![cscherrer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cscherrer/32/7631_2.png) [@cscherrer](https://discourse.julialang.org/u/cscherrer)\
**Post date:** [September 8, 2018, 2:08am UTC](https://discourse.julialang.org/t/lightgraphs-vs-simplegraphs/14643/9 "2018-09-08T02:08:30Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![anon94023334](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@anon94023334](https://discourse.julialang.org/u/anon94023334)\
**Post date:** [September 8, 2018, 2:43am UTC](https://discourse.julialang.org/t/lightgraphs-vs-simplegraphs/14643/10 "2018-09-08T02:43:47Z")

</div>

You can do half of this\*, and it’s particularly fast if the labels are indexed properties:

```julia
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.

---

<div class="post-metadata">

**Author:** ![cscherrer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cscherrer/32/7631_2.png) [@cscherrer](https://discourse.julialang.org/u/cscherrer)\
**Post date:** [September 13, 2018, 2:05am UTC](https://discourse.julialang.org/t/lightgraphs-vs-simplegraphs/14643/11 "2018-09-13T02:05:06Z")

</div>

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

```julia
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
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

```