Node with stored parents

[arzwa]

Hi, if I have a tree node that explicitly stores parents, but not siblings, and I define the parentlinks trait, it seems the tree iterators defined in AbstractTrees are not working. Is this expected behavior? I am a bit confused by this. For instance (example largely based on the bInary tree example in the repo)

using AbstractTrees

mutable struct Node{T}
    data    ::T
    parent  ::Node{T}
    children::Vector{Node{T}}

    Node(data::T) where T = new{T}(data)

    function Node(data::T, p) where T
        n = new{T}(data, p)
        isdefined(p, :children) ? push!(p.children, n) : p.children = [n]
        return n
    end
end

Base.show(io::IO, n::Node) = write(io, "Node($(n.data))")
Base.parent(n::Node) = isdefined(n, :parent) ? n.parent : nothing
Base.parent(root, n::Node) = isdefined(n, :parent) ? n.parent : nothing
Base.eltype(::Type{Node{T}}) where T = Node{T}
Base.eltype(::Type{<:TreeIterator{Node{T}}}) where T = Node{T}
Base.IteratorEltype(::Type{<:TreeIterator{Node{T}}}) where T = Base.HasEltype()

AbstractTrees.children(n::Node) = isdefined(n, :children) ? n.children : typeof(n)[]
AbstractTrees.parentlinks(::Type{Node{T}}) where T = AbstractTrees.StoredParents()
AbstractTrees.nodetype(::Type{Node{T}}) where T = Node{T}

Example tree:

n = Node(1)
m = Node(2, n)
Node(3, n)
Node(4, m)
Node(5, m)

julia> print_tree(n)
Node(1)
├─ Node(2)
│  ├─ Node(4)
│  └─ Node(5)
└─ Node(3)

julia> collect(PostOrderDFS(n))
ERROR: MethodError: no method matching relative_state(::Node{Int64}, ::Node{Int64}, ::Node{Int64})
Closest candidates are:
  relative_state(::Any, ::Any, ::AbstractTrees.ImplicitIndexStack) at /home/arzwa/.julia/packages/AbstractTrees/vOsoQ/src/AbstractTrees.jl:429
  relative_state(::Any, ::Any, ::AbstractTrees.ImplicitNodeStack) at /home/arzwa/.julia/packages/AbstractTrees/vOsoQ/src/AbstractTrees.jl:431
Stacktrace:
 [1] nextsibling(::Node{Int64}, ::Node{Int64}) at /home/arzwa/.julia/packages/AbstractTrees/vOsoQ/src/AbstractTrees.jl:438
 [2] stepstate at /home/arzwa/.julia/packages/AbstractTrees/vOsoQ/src/AbstractTrees.jl:505 [inlined]
 [3] iterate at /home/arzwa/.julia/packages/AbstractTrees/vOsoQ/src/AbstractTrees.jl:527 [inlined]
 [4] _collect(::UnitRange{Int64}, ::PostOrderDFS{Node{Int64}}, ::Base.HasEltype, ::Base.SizeUnknown) at ./array.jl:572
 [5] collect(::PostOrderDFS{Node{Int64}}) at ./array.jl:560
 [6] top-level scope at none:0

I expected that the parent information would be taken into account, without breaking the iterators. Is my expectation confused? And if this is expected behavior, what would be an efficient way to implement the nextsibling function for such a kind of tree (where the children are vectors)?

[hlin863]

I'm currently learning about how to implement the library for determining the ancestors of a set of nodes in a graph. I wonder if there's any more additional examples on how to find the parent nodes for a specific node?