# How to retrieve the edge list from a Dict reprepresenting a tree data structure

**URL:** <https://discourse.julialang.org/t/how-to-retrieve-the-edge-list-from-a-dict-reprepresenting-a-tree-data-structure/68802>\
**Category:** General Usage\
**Tags:** dictionary, tree, edge-vector\
**Created:** [September 27, 2021, 10:00am UTC](https://discourse.julialang.org/t/how-to-retrieve-the-edge-list-from-a-dict-reprepresenting-a-tree-data-structure/68802 "2021-09-27T10:00:40Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![empet](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/empet/32/221303_2.png) [@empet](https://discourse.julialang.org/u/empet)\
**Post date:** [September 27, 2021, 10:00am UTC](https://discourse.julialang.org/t/how-to-retrieve-the-edge-list-from-a-dict-reprepresenting-a-tree-data-structure/68802/1 "2021-09-27T10:00:40Z")

</div>

I’m reading a tree data structure fron a json file, and I need to retrieve the vector of  
edge tuples, (parent, child), to define a `LightGraphs.SimpleDiGraph` and get the node positions via `NetworkLayout.Buchheim` layout

An old Python function, that still works and I’d like to convert to a Julia one, is defined by:

```julia
import itertools
def edgelist(d, counter = next(itertools.count())):
    #d is the dictionary read from the jsonfile
   
    d["name"] = counter() if d["name"] is None else d["name"]
   
    if "children" in d:
        for child in d["children"]:      
            if child:
                child["name"] = counter() if child["name"] is None else child["name"]
                yield (d["name"], child["name"])
                
        for child in d["children"]:
            if child:
                for node in edgelist(child, counter):
                    yield node 

```

Since there isn’t an equivalent for `next` to get the next element in Julia `Iterators.countfrom()`, only using `for...`, as well as no `yield` correspondent, I cannot figure out how could I get the tree edges in a Julian way.

LE. An example of tree\_dict:

```julia
dtree = Dict("name"=> "A",
        "children"=>[Dict("name"=>"B",
                     "children"=> [Dict("name"=>"B1", 
                                   "children"=>[Dict("name"=> "B11",
                                                "children"=> [Dict("name"=> "B111")]),
                                               Dict("name"=>"B12"), 
                                               Dict("name"=>"B13")]),
                                  Dict("name"=> "B2",
                                   "children"=> [Dict("name"=>"B21"),
                                                Dict("name"=>"B22")])]
                    ),
                    Dict("name"=>"C",
                     "children"=> [Dict("name"=>"C1", 
                                   "children"=>[Dict("name"=> "C11"), 
                                               Dict("name"=>"C12", "children"=> [Dict("name"=> "C121")]), 
                                               Dict("name"=>"C13")]),
                                  Dict("name"=> "C2",
                                   "children"=> [Dict("name"=>"C21"),
                                                Dict("name"=>"C22")])]
                    )
                 ]);

```

---

<div class="post-metadata">

**Author:** ![Vasily\_Pisarev](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/vasily_pisarev/32/7929_2.png) [@Vasily\_Pisarev](https://discourse.julialang.org/u/Vasily_Pisarev)\
**Post date:** [September 27, 2021, 1:08pm UTC](https://discourse.julialang.org/t/how-to-retrieve-the-edge-list-from-a-dict-reprepresenting-a-tree-data-structure/68802/2 "2021-09-27T13:08:21Z")

</div>

As far as I understand, the Python version in essence defines the iteration over the edges.  
If you’re OK with eager evaluation, just define `edges = []` at the top of the function and replace `yield x` by `push!(edges, x)`.

For a replacement of `itertools.count`, you may create a custom callable struct:

```julia
mutable struct Counter{T<:Integer}
    start::T
end

Counter() = Counter(0)

function (cnt::Counter)()
    current = cnt.start
    cnt.start += 1
    return current
end

```

---

<div class="post-metadata">

**Author:** ![sijo](https://avatars.discourse-cdn.com/v4/letter/s/da6949/32.png) [@sijo](https://discourse.julialang.org/u/sijo)\
**Post date:** [September 27, 2021, 1:08pm UTC](https://discourse.julialang.org/t/how-to-retrieve-the-edge-list-from-a-dict-reprepresenting-a-tree-data-structure/68802/3 "2021-09-27T13:08:24Z")

</div>

An unreadable one-liner:

```julia
edgelist(d) = vcat(([(d["name"], child["name"]); edgelist(child)...] for child in get(d, "children", ()))...)

```

More readable:

```julia
function edgelist(d; list=NTuple{2,String}[])
    for child in get(d, "children", ())
        push!(list, (d["name"], child["name"]))
        edgelist(child; list)
    end
    return list
end

```

(you might want to add checks for edge cases as in the Python version)

---

<div class="post-metadata">

**Author:** ![empet](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/empet/32/221303_2.png) [@empet](https://discourse.julialang.org/u/empet)\
**Post date:** [September 27, 2021, 1:30pm UTC](https://discourse.julialang.org/t/how-to-retrieve-the-edge-list-from-a-dict-reprepresenting-a-tree-data-structure/68802/4 "2021-09-27T13:30:52Z")

</div>

@sudete Thank you very much!! I like this one 🙂

```julia
edgelist(d) = vcat(([(d["name"], child["name"]); edgelist(child)...] for child in get(d, "children", ()))...)

```

---

<div class="post-metadata">

**Author:** ![sijo](https://avatars.discourse-cdn.com/v4/letter/s/da6949/32.png) [@sijo](https://discourse.julialang.org/u/sijo)\
**Post date:** [September 27, 2021, 2:44pm UTC](https://discourse.julialang.org/t/how-to-retrieve-the-edge-list-from-a-dict-reprepresenting-a-tree-data-structure/68802/5 "2021-09-27T14:44:28Z")

</div>

Here are some nicer ones I think 🙂

An iterator over the edges (call `collect` on the result to get a vector):

```julia
using .Iterators: flatten

edges(d) = flatten(flatten([((d["name"], c["name"]),), edges(c)]) for c in get(d, "children", ()))

```

Splitting the problem in independent parts:

```julia
children(n) = get(n, "children", Dict{String,Any}())

# An iterator over the nodes (each node is a Dict)
nodes(d) = flatten([(d,), flatten(nodes(c) for c in children(d))])

# Get the edges of each node and concatenate them
mapreduce(n->[(n["name"], c["name"]) for c in children(n)], vcat, nodes(dtree))

```

---

<div class="post-metadata">

**Author:** ![empet](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/empet/32/221303_2.png) [@empet](https://discourse.julialang.org/u/empet)\
**Post date:** [September 27, 2021, 4:29pm UTC](https://discourse.julialang.org/t/how-to-retrieve-the-edge-list-from-a-dict-reprepresenting-a-tree-data-structure/68802/6 "2021-09-27T16:29:59Z")

</div>

I really appreciated your first solution and smiled because I was excited it was a Julian one. So there was no need for a detailed version. But thank you for it.

---

<div class="post-metadata">

**Author:** ![sijo](https://avatars.discourse-cdn.com/v4/letter/s/da6949/32.png) [@sijo](https://discourse.julialang.org/u/sijo)\
**Post date:** [September 27, 2021, 5:56pm UTC](https://discourse.julialang.org/t/how-to-retrieve-the-edge-list-from-a-dict-reprepresenting-a-tree-data-structure/68802/7 "2021-09-27T17:56:29Z")

</div>

Ah note that the detailed solution was not meant as an explanation, I wanted to show it because I think it’s the best solution: more readable, and more useful since the `children` and `nodes` functions can also be used to solve other tasks.