AbstractTrees parent child circular reference

New to Julia
1

I’m trying to implement a fairly simple tree.

mutable struct TreeNode
    parent::Union{Nothing,TreeNode}
    name::String
    children::Vector{TreeNode}
    size::Int
end
mutable struct Tree
    nodes::Vector{TreeNode}
end

Tree() = Tree([TreeNode(nothing, "root", Vector{TreeNode}(),0)])

AbstractTrees.nodevalue(n::TreeNode) = n.size
AbstractTrees.children(n::TreeNode) = n.children
AbstractTrees.ParentLinks(::Type{<:TreeNode}) = StoredParents()
AbstractTrees.parent(n::TreeNode) = get_parent(n)

function addchild(tree::Tree, parent::TreeNode, name::String, size::Int64)
    new_node = TreeNode(parent, name, Vector{}(),size)
    push!(parent.children, new_node)
end

But obviously I get a circular reference. What’s the correct way to store both parent and children in a node? I guess I’m mainly lost in understanding how to implement the children function.

Other resources for trees in Julia would be appreciated too!

2

This seems correct. Though I don’t believe get_parent is defined.
You probably want

AbstractTrees.parent(n::TreeNode) = n.parent

Where is the circular reference?

3

I get a circular reference in the children Vector.
When executing this

tr = Tree()
current = tr.nodes[1]
new_node = TreeNode(current, "name", Vector{TreeNode}(),0)
push!(current.children, new_node)

it returns:
1-element Vector{TreeNode}:
TreeNode(TreeNode(nothing, “root”, TreeNode[#= circular reference @-3 =#], 0), “name”, TreeNode, 0)

4

Ah, that is an “artifact” of the way show is implemented. By trying to print the fields of any children, the parent is indeed referenced again, thus the output.

You can overload show(io::IO, n::TreeNode), i.e.

import Base: show

function show(io::IO, n::TreeNode)
   str_parent = isnothing(n.parent) ? "no parent" : "with parent"
   str_children = "$(length(children(n))) children"
   print(io, "TreeNode($str_parent, $(n.name), $(nodevalue(n)), $str_children)")
end

julia> current
TreeNode(no parent, root, 0, 1 children)

julia> tr
Tree(TreeNode[TreeNode(no parent, root, 0, 1 children)])
2 Likes