# How to represent a DAG?

**URL:** <https://discourse.julialang.org/t/how-to-represent-a-dag/10025>\
**Category:** General Usage\
**Tags:** data\_structures\
**Created:** [March 28, 2018, 4:11am UTC](https://discourse.julialang.org/t/how-to-represent-a-dag/10025 "2018-03-28T04:11:28Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 28, 2018, 4:11am UTC](https://discourse.julialang.org/t/how-to-represent-a-dag/10025/1 "2018-03-28T04:11:28Z")

</div>

What is the best way to represent a [DAG (Directed Acyclic Graph)](https://en.wikipedia.org/wiki/Directed_acyclic_graph) in Julia?

I need to have mutable nodes that know who their children and their parents are, so that I can propagate information up and down them. The use case is [constraint propagation](https://github.com/JuliaIntervals/IntervalConstraintProgramming.jl), which has the same basic structure as reverse-mode automatic differentiation.

What is the best structure for this? The calculations should be as fast as possible.

So far I have something like

```julia
mutable struct Node
    value
    left::Union{Void, Node}
    right::Union{Void, Node}
    parent
end

```

Nodes can have values which are operations like `+`, variables like `x` or constants like `2`.

Obviously I would like to concretely type the nodes, but I don’t see a way to do that.

Probably the answer is “use Cassette.jl”, but I would like to try doing it by hand…

---

<div class="post-metadata">

**Author:** ![tkoolen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkoolen/32/1603_2.png) [@tkoolen](https://discourse.julialang.org/u/tkoolen)\
**Post date:** [March 28, 2018, 5:14am UTC](https://discourse.julialang.org/t/how-to-represent-a-dag/10025/2 "2018-03-28T05:14:46Z")

</div>

If you want it to be fast, definitely don’t do the recursive thing. Lay out the `value`s in a flat vector (probably toposorted in the case of a DAG). I’d recommend storing the vertex/edge relationships separately as integer indices, again in vectors.

The real experts are probably the LightGraphs people; I’m sure they can help you out with this. In fact you could just use LightGraphs straight up (perhaps with MetaGraphs to store associated data).

Personally, I rolled my own in an effort to keep dependencies for my package to a minimum (which was more of an issue in the past, when LightGraphs was anything but light in terms of dependencies) and because of some missing features at the time. See [https://github.com/JuliaRobotics/RigidBodyDynamics.jl/blob/master/src/graphs/directed\_graph.jl](https://github.com/JuliaRobotics/RigidBodyDynamics.jl/blob/master/src/graphs/directed_graph.jl) and [https://github.com/JuliaRobotics/RigidBodyDynamics.jl/blob/master/test/test\_graph.jl](https://github.com/JuliaRobotics/RigidBodyDynamics.jl/blob/master/test/test_graph.jl). It’s reasonably fast, but I actually stopped using it in performance-sensitive code, partly to improve performance.

If I were to reimplement it right now, I’d do things slightly differently. I thought it would be nice to be able to really treat the data associated with vertices and edges as being identical to the vertices and edges, but that convenience has a performance cost associated with it. In my design for `DirectedGraph{V, E}`, the vertex type `V` and edge type `E` each store an integer index along with the data (your `value`). Relationships between edges and vertices are stored in types like `Vector{V}` and `Vector{Vector{E}}`, which are indexed by these integer vertex and edge indices. This makes it so that graph traversal requires doing a lot of lookups of the integer indices in the (in my case big, heap-allocated) `V`’s and `E`’s, which is terrible for cache locality. So I’d store the vertex/edge relationships using integer vertex indices and edge indices if I were to do a second pass. This would make it closer to [`MetaGraphs.MetaDiGraph`](https://github.com/JuliaGraphs/MetaGraphs.jl/blob/d706aa948beb50a3610d01e56aafe19faf20df61/src/metadigraph.jl#L1-L10), but instead of storing the data associated with edges and vertices in `Dict`s, I’d still use flat `Vector`s indexed by integer vertex index and edge index.

Sorry about the wall of text, I hope that made some sense.

---

<div class="post-metadata">

**Author:** ![mauro3](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mauro3/32/292_2.png) [@mauro3](https://discourse.julialang.org/u/mauro3)\
**Post date:** [March 28, 2018, 5:15am UTC](https://discourse.julialang.org/t/how-to-represent-a-dag/10025/3 "2018-03-28T05:15:09Z")

</div>

If I remember correctly [https://github.com/mlubin/ReverseDiffSparse.jl](https://github.com/mlubin/ReverseDiffSparse.jl) uses DAGs.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 28, 2018, 6:41am UTC](https://discourse.julialang.org/t/how-to-represent-a-dag/10025/4 "2018-03-28T06:41:51Z")

</div>

Thanks, that will take a while to process!

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 28, 2018, 3:22pm UTC](https://discourse.julialang.org/t/how-to-represent-a-dag/10025/5 "2018-03-28T15:22:46Z")

</div>

I forgot to ask the related question: how to extract the DAG form using Dataflow.jl:

ps://github.com/MikeInnes/DataFlow.jl/issues/14

---

<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:** [March 29, 2018, 5:13pm UTC](https://discourse.julialang.org/t/how-to-represent-a-dag/10025/6 "2018-03-29T17:13:33Z")

</div>

I’d second the suggestion to see whether LightGraphs could help you here. The advantage is that if you have to _do_ anything graph-like with the DAG, it’s probably already in the package, and (reasonably) optimized.

If you have one value you need to store per node (or edge), then you might just use a `SimpleGraph` with an external vector mapping vertex to value (and the reverse as a `Dict` if you need it); otherwise, check out `MetaGraphs.jl`.

---

<div class="post-metadata">

**Author:** ![smldis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/smldis/32/1735_2.png) [@smldis](https://discourse.julialang.org/u/smldis)\
**Post date:** [March 29, 2018, 9:35pm UTC](https://discourse.julialang.org/t/how-to-represent-a-dag/10025/7 "2018-03-29T21:35:31Z")

</div>

I am interested too. I am unable to get where the trade off is about this (I am not a CS guy). Why it would be better to have data related to nodes far away in memory from the nodes themselves? Let’s assume I access all the data of a node at each node selection and then i pick another one, isn’t it going to always happen more cache misses, by having the data at another address?  
Is the trade off behind how cache is associative and how addresses are virtualized?

Is this related to the current julia status about supporting mutation of immutable types in mutable containers?

---

<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:** [March 29, 2018, 10:54pm UTC](https://discourse.julialang.org/t/how-to-represent-a-dag/10025/8 "2018-03-29T22:54:26Z")

</div>

> Why it would be better to have data related to nodes far away in memory from the nodes themselves?

There are really two primary reasons for this:

If you’re not using the “data related to nodes” (let’s call this _metadata_ for now) as part of your graph operations, then yes - as you suggest, cache locality can be improved in many cases by simplifying the data passed around within the operation. As an example, consider an algorithm that processes outneighbors of a given vertex. For `LightGraphs.SimpleGraph`, this is simply a (sorted) vector of `Int` (by default; the eltype can be as small as `UInt8`) which can fit into cache in all but the largest / most pathological cases, so when you’re accessing the elements in the vector it’s very quick. If you’re using a larger data structure that can’t fit into cache, you will take a performance hit.

The other reason is historical: that is, `LightGraphs` started with only one graph type, a `SimpleGraph` that could not store any metadata for nodes or edges at all. This approach results in very fast memory-efficient graph operations at the expense of flexibility. We justified this for the performance gains and the facts that 1) it’s fairly easy to create external data structures to hold the metadata you need, and 2) metadata generally plays no part in the graph operations folks tend to use most often. With `MetaGraphs.jl`, we’ve created a generic way to associate metadata with graphs while keeping the graph performance of `SimpleGraphs`. The current significant drawbacks are 1) increased complexity, 2) type instability in the metadata dictionaries, 3) increased memory usage, and 4) the likelihood of bugs due to 1). There’s also been an attempt to interface with `JuliaDB` which may be of interest.

> Is this related to the current julia status about supporting mutation of immutable types in mutable containers?

Not directly, as far as I’m aware. At least we haven’t consciously worried about this issue when designing the graph structures.

---

<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:** [March 29, 2018, 11:50pm UTC](https://discourse.julialang.org/t/how-to-represent-a-dag/10025/9 "2018-03-29T23:50:22Z")

</div>

OH, one other thing I forgot to mention (and I think it deserves its own post which is why I didn’t edit my previous one): given how easy it is to construct your own graph types now in LightGraphs, you might consider doing just that if `MetaGraphs` is too unwieldy for you.