I am having difficulty getting my head around the indexed tree interface. I have a small package RangeTrees.jl that creates interval trees in what I think is the indexed tree form. A RangeTree{T} consists of a Vector{RangeNode{T}} and the index of the root node in that vector. Each RangeNode contains the indexes of its left and right child nodes with the convention that a zero index indicates there is no node on that side.

If someone (@ExpandingMan @ararslan ?) can describe for me what AbstractTrees methods I should implement for RangeTree in my package, I will create a documentation PR for the index tree interface.

I'd like to customize the color of those characters in TreeCharSet with https://github.com/KristofferC/Crayons.jl . But the type is constrained to String currently. (I remember it was not in prior minor versions). Although I can use the transformed string representation, the textwidth would get the wrong number of text width in that case.

E.g. print_tree and printnode do have docstrings, but don't seem to show up anywhere in the manual. I presume they are considered part of the public API?

Hello,

Following JuliaLang/julia#24741 (comment)
maybe AbstractTrees could provide an example to get a tree of type hierarchy.

Kind regards

This issue is used to trigger TagBot; feel free to unsubscribe.

If you haven't already, you should update your TagBot.yml to include issue comment triggers.
Please see this post on Discourse for instructions and more details.

If you'd like for me to do this for you, comment TagBot fix on this issue.
I'll open a PR within a few hours, please be patient!

It looks like this repo hasn't been updated in quite a while. I'd be willing to help out if you're looking for extra maintainers.

There are cases where I want to treat an iterable object as a leaf of a tree for the sake of iteration or printing.

For example, maybe I have a tree like:

julia> using AbstractTrees

julia> tree = [(:a, :b), [(:b, :c), (:c, :d)]]
2-element Vector{Any}:
 (:a, :b)
 [(:b, :c), (:c, :d)]

julia> Tree(tree)
Vector{Any}
├─ (:a, :b)
│  ├─ :a
│  └─ :b
└─ Vector{Tuple{Symbol, Symbol}}
   ├─ (:b, :c)
   │  ├─ :b
   │  └─ :c
   └─ (:c, :d)
      ├─ :c
      └─ :d

but for the sake of iterating I actually want the elements of type Tuple{Vararg{Symbol}} to be treated like leaves.

Is there currently a way to do that? One possibility is defining a special wrapper type like:

struct Leaf{T}
  data::T
end

AbstractTrees.children(::Leaf) = ()

which we use like:

julia> tree = [Leaf((:a, :b)), [Leaf((:b, :c)), Leaf((:c, :d))]]
2-element Vector{Any}:
 Leaf{Tuple{Symbol, Symbol}}((:a, :b))
 Leaf{Tuple{Symbol, Symbol}}[Leaf{Tuple{Symbol, Symbol}}((:b, :c)), Leaf{Tuple{Symbol, Symbol}}((:c, :d))]

julia> Tree(tree)
Vector{Any}
├─ Leaf{Tuple{Symbol, Symbol}}((:a, :b))
└─ Vector{Leaf{Tuple{Symbol, Symbol}}}
   ├─ Leaf{Tuple{Symbol, Symbol}}((:b, :c))
   └─ Leaf{Tuple{Symbol, Symbol}}((:c, :d))

This is easy enough to do externally, but I was wondering if it seems of interest to have a canonical Leaf type in the package.

Alternatively, maybe there could be an interface like Tree(tree; isleaf=[...]) as a way to specify if something should be considered a leaf for the sake of that tree instance. By default it could be x -> children(x) == () or the isleaf function introduced in #79, but it could be extended to something like x -> (children(x) == ()) || (x isa Tuple{Vararg{Symbol}}) for the example above.

Happy to make a PR if any of this is of interest.

Nested trees print forever, which is confirmed by searching for maxdepth in the code and not finding it used!

I haven't had much time to contribute to this package for quite a while, but this was a major issue I identified way back when I was thinking about expanding the interface. After it came up recently in #115 I'm adding this issue just to start the discussion. It is more of a problem for when/if the API gets expanded further and not something that needs to be fixed right now.

Basically, there is a subtle but important difference between a tree and a node. A node is just some type that implements children(), while a tree represents an entire collection of nodes with a single root and all their parent/child relationships. Part of the confusion is because any node implicitly represents a tree with itself as the root. This is just part of a tree's inherently recursive nature - any subtree is itself a tree in its own right. Several functions currently in this package conceptually work on full trees but take as an argument a node which is the root of that tree. However, this isn't necessarily the same as "the tree the node belongs to".

If a node implements parent links there is a well-defined "whole tree" that it belongs to (the root of which can be obtained by moving up the chain of parent links as far as possible). If there aren't explicit parent links then the "true" root could depend on context - e.g. in parsed JSON data made of nested arrays and dictionaries there is a node that corresponds to the root of the document. An API function that is just passed a plain array nested several layers deep in this document has no way of knowing that, and maybe should treat that node as possibly existing within a larger tree rather than assuming it is the root.

Currently there is just one type (IndexedTree) which represents a whole tree without also being a node itself, but I could definitely envision others. It would make sense to have the API be able to deal with these types in general.

Docstring:

julia> print_tree(stdout, Dict("a"=>"b","b"=>['c','d']))
Dict{String,Any}("b"=>['c','d'],"a"=>"b")
├─ b
│  ├─ c
│  └─ d
└─ a
   └─ b

Actual:

julia> print_tree(stdout, Dict("a"=>"b","b"=>['c','d']))
Dict{String,Any}
├─ Array{Char,1}
│  ├─ 'c'
│  └─ 'd'
└─ "b"

Would it be possible to add an implementation of a breadth-first iterator ?
Or is that not possible in a generic way?

Hi there,

I really like this package and see potential in many applications (and finance being the one on my mind at the moment) ❤️

In fact, the following registered packages have a dependency on AbstractTrees.jl:

• BioMedQuery.jl
• BioServices.jl
• Cascadia.jl
• D3Trees.jl
• DataDepsGenerators.jl
• DiffEqBayes.jl
• DiffEqFlux.jl
• DiffEqSensitivity.jl
• ExprOptimization.jl
• ExprRules.jl
• Flux.jl
• Gumbo.jl
• Metalhead.jl
• ONNX.jl
• Omega.jl
• PhysOcean.jl
• ReinforcementLearning.jl
• TextAnalysis.jl
• Turing.jl

Thank you @Nosferican for the list 😊

Looking through a few of these packages, I see most of them just use children and printnode. I'd be curious to find a package that makes deeper use of some of the other functionality of this package. Any suggestions?

The purpose of these notes is to try to help me understand how things work and maybe to suggest some alternate ways forward (and probably learn a lot in the process as I discover my errant ways).

Children or Parents?

I can think of two ways to define a tree structure. It seems the most common way is top down, i.e.

struct TopDownTree
    name::String
    children::Vector{TopDownTree}
end

But, depending on the application, I could see the use for a bottom-up approach, i.e.

struct BottomUpTree
    name::String
    parent::BottomUpTree
end

I think either of the above are sufficient to uniquely define a tree. However, we could be redundant and define something like

struct RedundantTree
    name::String
    parent::RedundantTree
    children::Vector{RedundantTree}
    siblings::Vector{RedundantTree}
end

This is redundant (assuming each node has a single parent which I think is safe for this package) because given only parent info, you can deduce both children and siblings info. Similarly, given only children info, you can deduce both parent and siblings info. Because of this, you'd probably want some consistency checks for a RedundantTree, but no matter.

From what I can tell (and I could always be wrong and this is a caveat for everything I say in these notes 😅), this package seems to favor the TopDownTree approach, but has some types defined to cater for when parent and sibling info is available.

Indexed or Regular?

For my application, I need to keep track of financial accounts for a general ledger. Before looking into tree structures or this package, my initial definition was something along the lines of

struct Account
    name::String
    number::String
    children::Dict{String,Account}
end

As I worked on my package, I started to feel like I was reinventing the wheel, which brought me to AbstractTrees.jl 👍

Digging through the code, I found there is an abstract type TreeKind with two concrete subtypes:

1. RegularTree <: TreeKind
2. IndexedTree <: TreeKind

Since I access children nodes via Account.number from a Dict, I guess you would say this type of tree is an IndexedTree with the index being the account number.

If you don't need to access specific nodes in the tree and just want the ability to quickly iterate over children, then you would use something like TopDownTree above where children is a vector of nodes. This type of tree is a RegularTree.

My first instinct, expressed in issue #23, was to have my Account be a subtype of IndexedTree, i.e. I wanted to write something like

struct Account <: IndexedTree
    name::String
    number::String
    children::Dict{String,Account}
end

This led me to spend some time looking at TreeKind. I spent a good chunk of time today making changes so that IndexedTree and RegularTree are both abstract (which breaks the method treekind).

I didn't understand the purpose of treekind at first, but as I write these notes a 💡 just came on.

I guess the intention of treekind is to specify whether my type is a RegularTree or an IndexedTree like

AbstractTrees.treekind(acct::Account) = IndexedTree()

Hmm 🤔 That is clever 😊

Anyway, since I have a high tolerance for pain (at least for the first two times), I started going through the code and replacing things like

https://github.com/Keno/AbstractTrees.jl/blob/master/src/AbstractTrees.jl#L120

tree != roottree && isa(treekind(roottree), IndexedTree) ?

with

tree != roottree && isa(roottree, IndexedTree) ?

in which case, treekind isn't even needed.

It seemed cleaner to me to have RegularTree and IndexedTree to be abstract, but I am feeling less confident about that the more I write 😅

Full Abstract

When I started writing these notes, I was going to suggest reducing the number of concrete types here and rely more on subtyping abstract types, but that would be a very breaking change and maybe not worth it. Especially now that I understand treekind. It comes down to the choice of either

struct Account <: IndexedTree
    name::String
    number::String
    children::Dict{String,Account}
end

or

struct Account
    name::String
    number::String
    children::Dict{String,Account}
end
AbstractTrees.treekind(acct::Account) = IndexedTree()

The former feels more natural to me, where the latter feels like we are implementing some dispatch functionality in the package itself. Maybe the latter is faster or more efficient somehow?

An illustrative example is nextsibling

https://github.com/Keno/AbstractTrees.jl/blob/master/src/AbstractTrees.jl#L401

nextsibling(node) = nextsibling(node, parentlinks(node), siblinglinks(node), treekind(node))

As mentioned above, TreeKind has two concrete subtypes and to make use of the packages functionality, I would define

AbstractTrees.treekind(acct::Account) = IndexedTree()

Simlarly, the abstract type ParentLinks has two concrete subtypes

1. StoredParents <: ParentLinks
2. ImplicitParents <: ParentLinks

and I would need to define

AbstractTrees.parentlinks(acct::Account) = ImplicitParents()

since Account does not store parent info explicitly.

In the same way, the abstract type SiblingLinks has two concrete subtypes

1. StoredSiblings <: SiblingLinks
2. ImplicitSiblings <: SiblingLinks

and I would need to define

AbstractTrees.siblinglinks(acct::Account) = ImplicitSiblings()

since Account does not store siblings info explicitly.

All together, it would look like

struct Account
    name::String
    number::String
    children::Dict{String,Account}
end
AbstractTrees.treekind(acct::Account) = IndexedTree()
AbstractTrees.parentlinks(acct::Account) = ImplicitParents()
AbstractTrees.siblinglinks(acct::Account) = ImplicitSiblings()

then we can dispatch on the concrete TreeKind, the concrete ParentLinks and the concrete SiblingLinks as in

nextsibling(node) = nextsibling(node, parentlinks(node), siblinglinks(node), treekind(node))

Now that I understand how it works, I think this is cool, but I still have to ask, is this better than defining abstract types instead and having your custom types be subtypes of those?

For example, the most common type of tree, I imagine would be

• RegularTree()
• ImplicitParents()
• ImplicitSiblings()

so why not introduce a top-level abstract AbstractTree and just call this type of tree something like

abstract type RegularTopDownTree <: AbstractTree end

Then instead of

nextsibling(node,ImplicitParent(),ImplicitSibling(),RegularTree())

you could just have

nextsibling(node::RegularTopDownTree)

See what I mean?

Then, instead of

• IndexedTree()
• ImplicitParents()
• ImplicitSiblings()

just call this something like

abstract type IndexedTopDownTree <: AbstractTree end

Then instead of

nextsibling(node,ImplicitParent(),ImplicitSibling(),IndexedTree())

you could just have

nextsibling(node::IndexedTopDownTree)

Then we need names for other combinations, but I don't think that would be too hard, e.g.

nextsibling(node::RegularParentTree) 
= nextsibling(node,StoredParents(),ImplicitSiblings(),RegularTree())

nextsibling(node::IndexedSiblingTree) 
= nextsibling(node,ImpliciyParents(),StoreSiblings(),IndexedTree())

nextsibling(node::RegularRedundantTree) 
= nextsibling(node,StoredParents(),StoredSiblings(),RegularTree())

etc.

Then we wouldn't need the concrete types [Stored|Implicit][Parents|Siblings]() or [Regular|Indexed]Tree() and I'd just need to define my type like

struct Account <: IndexedTopDownTree
    name::String
    number::String
    children::Dict{String,Account}
end

I kind of like this because the abstract type structure itself is a tree 😊

AbstractTree
- RegularTree
  - RegularTopDownTree
  - RegularParentTree
  - RegularSinglingTree
  - RegularRedundantTree
  - RegularBottomUpTree
- IndexedTree
  - IndexedTopDownTree
  - IndexedParentTree
  - IndexedSiblingTree
  - IndexedRedundantTree
  - IndexedBottomUpTree

Granted, this is a lot of abstract trees, but given the name of this package is "AbstractTrees", I'd think that is ok 😅

I'm very curious to hear if anyone has any thoughts on this. I am inclined to go ahead and make these changes, but they would be significant changes and I understand there is a chance it wouldn't get merged here. Obviously, I would be more motivated if I thought there was a chance 😅

Anyway, I accomplished one goal by writing these notes. I learned quite a bit 👍😊

It's probably safe to say that most implementations of children() are "eager" in that they return some kind of explicit collection type like an Array. This has no performance cost when this collection is already stored as one of the node's attributes, but may be non-negligible if this collection has to be constructed with each call. Simpler queries about a node's children that do not require getting the full set, such as just counting their number, will incur a lot of unnecessary overhead in this case if we can only rely on the return value of children() (like length(children(node))).

I'd like this package to both include some efficient implementations of generic tree algorithms as well as support the easy creation of new ones, which would require adding some additional functions to the public API to support these cases. There are already a few undocumented examples scattered around the source code:

• has_children(node) - checks whether an object has any children at all, although the implementation is broken (see #56).
• nodetype(::Type) - type trait for expected value of eltype(children(node)).
• getnode(node, ...) - get a specific node based on its index, if applicable? There's some kind of notion of indexed trees which could be useful but isn't really documented.
• childindices(node) - get the node's child indices.
• idxtype(node) - I'm guessing the expected value of eltype(childindices(node)).

In addition to these I think it's important to at least have an nchildren(node) function, although I can envision others.

I'm planning on submitting a PR for this myself but would like to solicit some feedback on the design first. If this extended version of the API gets defined and documented then a lot more useful algorithms and utilities could be added to this package.

Hi,

I installed this package in the new version v0.4.3. It seems that getdescendant function cannot be used. Specifically, in REPL, after using AbstractTrees, this example in the manual won't work:

v = [1, [2, [3, 4]]]

getdescendant(v, (2, 2, 1)) == 3

It will give me

julia> getdescendant(v, (2, 2, 1)) == 3
ERROR: UndefVarError: getdescendant not defined
Stacktrace:
 [1] top-level scope
   @ REPL[17]:1

I have similar issues with treebreadth, treeheight functions in the "additional functions" part of the manual: they will throw out an UndefVarError for these two functions.

Is this an intentional change?

Previously, dots would not appear when the depth landed on a node that was an empty array.

julia> print_tree([[1,2],[]], 2)
Array{Array{Any,1},1}
├─ Array{Any,1}
│  ├─ 1
│  └─ 2
└─ Array{Any,1}

julia> print_tree([[1,2],[]], 1)
Array{Array{Any,1},1}
├─ Array{Any,1}
│  ⋮
│  
└─ Array{Any,1}
   ⋮

@Keno, how would you feel about moving this to JuliaCollections? It might spread the maintenance burden out a bit and make it more "official."

What is the parentind meant to do? I am trying to implement the AbstractTrees interface.

I'm studying this package and have a few questions. Sorry for polluting the issues 😅

Looking at this: https://github.com/Keno/AbstractTrees.jl/blob/master/src/AbstractTrees.jl#L181-L189

function zip_min(c1, c2)
    n1, n2 = length(c1), length(c2)
    if n1 < n2
        c2 = take(c2,n1)
    elseif n2 < n1
        c1 = take(c1,n2)
    end
    zip(c1, c2)
end

I can't find take defined anywhere 🤔

What am I missing?

The tag name "0.1.0" is not of the appropriate SemVer form (vX.Y.Z).
cc: @Keno

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)?

I've read the docs but I haven't been able to find an answer to my question.

I would like to understanding the following. I have a mutable struct and a few functions defined on it that mutate in the same structure of a tree. I.e. I have a "movetoparent!(obj)" function, and a "movetochild!(obj, i)" function. Can I use AbstractTrees.jl to walk a tree in this case?

I've asked this question on discourse, where I go into more details

https://discourse.julialang.org/t/abstracttrees-iterating-without-a-tree/96339

Most docs appear to be broken
https://juliacollections.github.io/AbstractTrees.jl/dev/api/

Per usual Julia convention. These methods do modify fields of the structure.

If we define the simplest possible tree

using AbstractTrees
struct Tree
    child :: Union{Tree, Int}
end
AbstractTrees.children(tree::Tree) = (tree.child, )
function nest(n)
    tree = Tree(1)
    for i in 1:n
        tree = Tree(tree)
    end
    tree
end
function it(x)
    for x in PreOrderDFS(tree)
        x isa Int && return x
    end
end

Then the current definition of PreOrderDFS (and other traversals) recompile for different sized trees.

julia> tree = nest(2);
julia> @time it(tree);
  0.110824 seconds (297.39 k allocations: 19.659 MiB, 11.69% gc time, 99.77% compilation time)

julia> tree = nest(100);
julia> @time it(tree);
 20.828098 seconds (4.94 M allocations: 329.490 MiB, 0.25% gc time, 99.96% compilation time)

Defining AbstractTrees.childtype(::Tree) = Union{Int, Tree} makes it roughly 50x faster, but there still is compile time proportional to the size of tree.

Would it make sense for this package to define filter and/or filter!?

I've looked into the implementation and guess that this issue boils down to: Is there a kind of null element defined for abstract trees? If yes, then a PreOrderDFS could replace elements by null and that should work, I think.

It looks like treemap is broken or at least maybe documentation example is needed?

using AbstractTrees
import AbstractTrees: children

struct Node
    v::Int
    c::Vector{Node}
end

children(n::Node) = n.c

tree = Node(1,
            [Node(2,
                  [Node(3, []),
                   Node(4, [])]),
             Node(5, [])])

With this setup, I wasn't able to run treemap in any configuration. FIrst of all, it accepts only PostOrderDFS types. Why can't I just pass tree and it internally call PostOrderDFS on it?

Secondly, call like this

treemap(x -> x.v, PostOrderDFS(tree))

return error

ERROR: MethodError: no method matching keys(::PostOrderDFS{Node})
Closest candidates are:
  keys(::Core.SimpleVector) at essentials.jl:605
  keys(::Cmd) at process.jl:639
  keys(::LibGit2.GitTree) at /home/skoffer/.julia/packages/Revise/XFtoQ/src/git.jl:52
  ...
Stacktrace:
 [1] pairs(::PostOrderDFS{Node}) at ./abstractdict.jl:134
 [2] treemap(::var"#19#20", ::PostOrderDFS{Node}) at /home/skoffer/.julia/packages/AbstractTrees/VQ0nX/src/iteration.jl:349

I can pirate it to ( I am completely at loss, what I am doing at this moment, actually)

Base.:pairs(x::PostOrderDFS) = enumerate(x)

This helps to go through this error, but it looks like function require more than one argument, so I change call to

treemap((i, x, c) -> x.v, PostOrderDFS(tree))

And then I get into error

ERROR: MethodError: no method matching copy!(::Array{Int64,1}, ::Int64, ::Array{Union{},1}, ::Int64, ::Int64)
Closest candidates are:
  copy!(::AbstractArray{T,1} where T, ::AbstractArray{T,1} where T) at abstractarray.jl:708
  copy!(::AbstractArray, ::AbstractArray) at abstractarray.jl:711
Stacktrace:
 [1] treemap(::var"#23#24", ::PostOrderDFS{Node}) at /home/skoffer/.julia/packages/AbstractTrees/VQ0nX/src/iteration.jl:369

Help shows that it is true, there is no copy! with 5 arguments in Base.

So, how this function is supposed to be used? Is it working at all?

I have just come to fully understand a problem that I was struggling with a bit when I wrote my 0.4 PR: current master on this package still conflates "keys" with "nodes".

To see what I mean by this, consider a Dict. Currently we define children(dict::AbstractDict) = pairs(dict) and some methods for Pair so that Pairs are by themselves nodes each with a single child (i.e. they are tree-equivalent to [p.second]. The problem with this is that p.first is supposed to play the role of an index, not a node. This matters because, for example, getdescendant (used to be called childindex but I changed it after a helpful suggestion by @jlumpe) cannot work with dictionaries, even though it has every reason to.

It's mostly clear to me now that the "right" thing to do is to deprecate the old behavior so that e.g. children(dict::AbstractDict) = values(dict) and delete all of the pair methods. However, this is making me a little nervous. My PR doesn't break very much in part because the tree structure of everything in Base is preserved. Making alterations to this tree structure is much more likely to be breaking. One place this would be manifest within AbstractTrees itself is print_tree, which would need to be altered.

In summary, the benefit of making this change would be consistent indexing behavior, with the cost of making what is probably a more significant change than any that were in my original PR. On the other hand, it probably won't break all that many packages.

Opinions on this?

There's a trait for ParentLinks and SiblingLinks, it would be great if there was a ChildrenLinks trait too. Of course, a tree needs at least one of {link to children, link to parent}.

I think the recent release broke something in ASTInterpreter on 0.5:

$ julia
               _
   _       _ _(_)_     |  A fresh approach to technical computing
  (_)     | (_) (_)    |  Documentation: http://docs.julialang.org
   _ _   _| |_  __ _   |  Type "?help" for help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 0.5.0 (2016-09-19 18:14 UTC)
 _/ |\__'_|_|_|\__'_|  |  Official http://julialang.org/ release
|__/                   |  x86_64-pc-linux-gnu

julia> using ASTInterpreter
INFO: Precompiling module ASTInterpreter.
ERROR: LoadError: BoundsError: attempt to access ()
  at index [11]
 in getindex(::Tuple{}, ::Int64) at ./tuple.jl:8
 in getnode(::Expr, ::AbstractTrees.ImplicitNodeStack{Any,Int64}) at /home/sabae/.julia/v0.5/AbstractTrees/src/implicitstacks.jl:21
 in next(::AbstractTrees.PostOrderDFS, ::Nullable{AbstractTrees.ImplicitNodeStack{Any,Int64}}) at /home/sabae/.julia/v0.5/AbstractTrees/src/AbstractTrees.jl:457
 in next(::AbstractTrees.IndEnumerate{AbstractTrees.PostOrderDFS}, ::Nullable{AbstractTrees.ImplicitNodeStack{Any,Int64}}) at /home/sabae/.julia/v0.5/AbstractTrees/src/AbstractTrees.jl:261
 in goto!(::ASTInterpreter.Interpreter, ::Int64) at /home/sabae/.julia/v0.5/ASTInterpreter/src/ASTInterpreter.jl:548
 in _step_expr(::ASTInterpreter.Interpreter) at /home/sabae/.julia/v0.5/ASTInterpreter/src/ASTInterpreter.jl:609
 in step_expr at /home/sabae/.julia/v0.5/ASTInterpreter/src/ASTInterpreter.jl:666 [inlined]
 in #finish!#81(::Bool, ::Bool, ::Function, ::ASTInterpreter.Interpreter) at /home/sabae/.julia/v0.5/ASTInterpreter/src/ASTInterpreter.jl:1720
 in (::ASTInterpreter.#kw##finish!)(::Array{Any,1}, ::ASTInterpreter.#finish!, ::ASTInterpreter.Interpreter) at ./<missing>:0
 in _precompile_() at /home/sabae/.julia/v0.5/ASTInterpreter/src/precompile.jl:5
 in include_from_node1(::String) at ./loading.jl:488
 in macro expansion; at ./none:2 [inlined]
 in anonymous at ./<missing>:?
 in eval(::Module, ::Any) at ./boot.jl:234
 in process_options(::Base.JLOptions) at ./client.jl:239
 in _start() at ./client.jl:318
while loading /home/sabae/.julia/v0.5/ASTInterpreter/src/ASTInterpreter.jl, in expression starting on line 1742
ERROR: Failed to precompile ASTInterpreter to /home/sabae/.julia/lib/v0.5/ASTInterpreter.ji.
 in compilecache(::String) at ./loading.jl:593
 in require(::Symbol) at ./loading.jl:422

@Keno @yuyichao

v0.4 Eco Checks

I have run unit tests for all direct dependents against v0.4 as of the latest commit on my latest PR.

As you can see, most packages nearly require a compat bound bump. A few are using the deprecated
function parentlinks and likely require only a simple change.

At the moment it seems there are only two non-trivial cases:

• BehaviorTree: this uses ShadowTree, a data structure which I did not understand the reason for
  in the first place. I expect that whatever it was doing can be easily replaced, but I'll have
  to take a look at this package to see what the v0.4 equivalent will be.
• Convex: this uses treekind which suggests that it is one of the only packages using indexed
  trees, and therefore is likely to require a non-trivial update.

✅ AutocorrelationShell

✅ BasisFunctions

factorial(::Float64) method error that happens even for v0.3

❌ BehaviorTree

uses ShadowTree

✅ Casciadia

✅ CombinedParsers

✅ ConstituencyTrees

✅ ConstructiveGeometry

Unrelated error, same thing happens on v0.3

❌ Convex

treekind not defined

✅ D3Trees

✅ DataDepsGenerators

unrelated error, same thing on v0.3

✅ DataSets

✅ DecisionTree

✅ DocumentationGenerator

unrelated error, same thing on v0.3

✅ DocumenterTools

unrelated error, same thing on v0.3

✅ ExprOptimization

✅ ExprRules

✅ ExtendableGrids

unrelated error, same thing on v0.3

✅ Eyeball

✅ FeynmanDiagram

I'm getting a parquet-related test error, but exactly same error on v0.3.

✅ FileTreees

❌ FlameGraphs

parentlinks not defined

✅ FoldingTrees

✅ Flux

✅ GenericTensorNetworks

unrelated error, same thing on v0.3, lots of passing tests

✅ GraphRecipes

✅ Gridap

✅ GridapEmbedded

✅ Gumbo

✅ HMatrices

✅ HalfEdges

unrelated error, same thing on v0.3

✅ HssMatrices

✅ ITensors

❌ ImageComponentAnalysis

expects parentlinks

❌ InfiniteOpt

expects parentlinks

✅ InteractiveErrors

✅ JSServe

Seems to have unrelated errors, but testing is a dependency mess, not completely sure.

✅ JunctionTrees

✅ KeywordSearch

❌ LeftChildRightSiblingTrees

expects parentlinks

✅ MathML

✅ MathTexEngine

✅ MetaUtils

✅ MethodAnalysis

❌ ModelingToolkit

depends on LeftChildRightSiblingTrees

✅ MultiScaleTreeGraph

expects parentlinks

❌ NewickTree

expects Tree

✅ OMEinsum

✅ OnlineStats

✅ OnlineStatsBase

✅ PDFIO

❌ PProf

depends on LeftChildRightSiblingTrees

✅ PSID

unrelated error, trying to fetch remote stuff

✅ Parquet2

✅ PatchMixtureKriging

✅ PhysOcean

❌ PlutoProfile

depends on LeftChildRightSiblingTrees

✅ ProjectEulerUtil

✅ QXContexts

seems to have packaging issues

✅ QXTools

✅ ReinforcementLearningBase

✅ ReinforcementLearningCore

✅ ReinforcementLearningExperiments

✅ ReinforcementLearningZoo

✅ Remarkable

requires 3rd party remote service to test

✅ RewriteTools

❌ SIIPExamples

depends on LeftChildRightSiblingTrees

✅ Scruff

✅ Skans

✅ SymbolicUtils

depends on LeftChildRightSiblingTrees but still passes

✅ TSML

✅ Taxonomy

✅ TimeDag

unrelated error, same thing on v0.3, passes lots of tests

✅ Transformers

❌ TreesHeaps

expects parentlinks

✅ Tries

✅ UnROOT

❌ WRDSMerger

expcts parentlinks

✅ WavePropBase

✅ Wordlegames

✅ XML

Iterating over StatelessBFS calls getindex on the object returned by children():

julia> collect(StatelessBFS(n))
ERROR: MethodError: no method matching getindex(::VectorTreeChildren, ::Int64)
Stacktrace:
 [1] getdescendant
   @ ~/.julia/packages/AbstractTrees/kBTzE/src/indexing.jl:29 [inlined]
 [2] iterate(ti::StatelessBFS{VectorTreeNode}, ind::Vector{Any})
   @ AbstractTrees ~/.julia/packages/AbstractTrees/kBTzE/src/iteration.jl:418

As far as I understand, the default for ChildIndexing is NonIndexedChildren, which should imply that it shouldn't be necessary to implement indexing for children? The other iterators (*OrderDFS, Leaves) work fine with my type.

This should work as an MWE:

struct VectorTreeNode
    children :: Vector{Any}
    VectorTreeNode(cs) = (cs isa Vector) ? new(cs) : new([])
end
struct VectorTreeChildren
    node :: VectorTreeNode
end
Base.IteratorSize(::Type{VectorTreeChildren}) = Base.SizeUnknown()
function Base.iterate(it::VectorTreeChildren, state = 1)
    if state <= length(it.node.children)
        (VectorTreeNode(it.node.children[state]), state + 1)
    else
        nothing
    end
end
using AbstractTrees
AbstractTrees.children(n::VectorTreeNode) = VectorTreeChildren(n)
n = VectorTreeNode([1,[2,3],4])
collect(StatelessBFS(n))

Note: there is also #15 which seems to be a similar issue, but is quite outdated I think -- Leaves works and the indexability trait (ChildIndexing) exists now.

One of the main uses of trees is to maintain sorted invariants. As such, I think we should have a way of supporting the find* methods on trees that are O(depth) . I'm unsure of the best interface for this, so I would appreciate comments before I make a PR.
I think the best way to support this is with a trait

abstract type TreeOrdering end
struct NonOrderedTree<:TreeOrdering end
struct OrderedTree<:TreeOrdering end
TreeOrdering(::Type) = NonOrderedTree()
TreeOrdering(node) = TreeOrdering(typeof(node))

where OrderedTrees must implement Base.isless between any two nodes of the tree, and this order should respect the tree structure (i.e. the the children of a node are sorted, and the parent is less than all children) .

This should be enough to implement efficient methods for findfirst and the other find methods.

Hello everyone,

I'm the developer of Term.jl. Recently I've developed a Tree type to create data structures very much like those supported by AbstractTrees and to print tree structures to the terminal like:

Unfortunately I didn't know about AbstractTrees when I did that or I would've been using it from the beginning, now I've found I've replicated some of the work you've put into this beautiful package.

As stated in FedeClaudi/Term.jl#70, I'd like to bridge Term and AbstractTrees. I just thought I'd give you a heads up in case you were interested in working together on this.

Cheers,
Fede

The definition doesn't seem to be used, and I'm not sure what it illustrates. In any case, this seems to be a pun on Base.parent:

help?> parent
[...]
  parent(A)

  Return the underlying "parent array”. This parent array of objects of types SubArray, ReshapedArray or LinearAlgebra.Transpose is what was passed as an argument to view, reshape,
  transpose, etc. during object creation. If the input is not a wrapped object, return the input itself.

Most recent build failing on Julia nightly.

Unrelated, but I noticed a potential issue in the following line:

printnode(io::IO, t::Core.Compiler.Timings.Timing) = print(io, t.time/10^6, "ms: ", t.mi_info)

I'm assuming t.time is in seconds, so it should either be /10^3 and "ms" or /10^6 and "ns".

https://github.com/JuliaAI/DecisionTree.jl/runs/6823455543?check_suite_focus=true

Hi,

I am studying this package (looks awesome 🙌) and might like to use it in some financial applications. From what I can tell so far, I think my data, i.e. accounts and subaccounts in a general ledger, would be considered an IndexedTree indexed by account number, but I'd like to use my own type, e.g. Ledger.

It might be nice to be able to do something like

struct Ledger <: IndexedTree
...
end

Would you be open to a PR along these lines? No worries if not 😊

I'm currently implementing a plot recipe for decision trees in order to be able to visualize all decision trees within the MLJ-package.

The goal is a plot recipe that

1. has no dependency on Plots.jl
2. is independent of any specific decision tree implementation

Goal 1 is an inherent characteristic of plot recipes. So we have reached it just by using plot recipes. Goal 2 is realised by requiring each decision tree implementation which wants its trees to be visualized to implement a narrow part of the AbstractTrees-interface (namely children and printnode).

I have already done such an implementation for DecisionTree.jl (see https://github.com/JuliaAI/DecisionTree.jl/blob/dev/src/abstract_trees.jl). The plot recipe itself exists also (see JuliaAI/DecisionTree.jl#147; the recipe is btw so general that it can be applied to each tree implementing the above mentioned interface, it isn't restricted to decision trees).

The only missing part to make all that work, is a type for dispatch. If we have a tree which we would like to plot (e.g. an instance of DecisionTree) then we want to be able to call plot(tree). In order for plot to chose the correct plot recipe, tree must be of the type that is associated with the plot recipe.

As we want a recipe that is independent of any specific decision tree implementation, this type has to be independent of all these implementations. Therefore I have defined a new abstract type AbstractNode.

The question is now, where this new type should be placed. A very natural place would be AbstractTrees.jl (as the AbstractTrees-interface is already used as a common denominator).
Therefore the question: Could such an abstract type be added to AbstractTrees.jl?

BTW: If AbstractTrees.jl wouldn't be "just" an interface but define also a type (like AbstractTree), the whole problem wouldn't exist at all).

@ablaom: Do you want to add some remarks?

I tried to model my own tree upon the concepts introduced in this package by simply defining children as a function that returns an iterator over the children of a given node. This immediately enabled print_tree. I was not able to use e.g. 'Leaves'. The problem seems to be that the children collection should be indexable as opposed to be merely iterable. Also the supplied example demonstrating directory traversal suffers from this:

include("examples/fstree.jl")
ns = collect(Leaves(Directory(pwd())))

MethodError: no method matching getindex(::DirectoryListing, ::Int64)
in collect at base\array.jl:431
in _collect at base\array.jl:442
in start at AbstractTrees\src\AbstractTrees.jl:494 
in firststate at AbstractTrees\src\AbstractTrees.jl:398
in isempty at base\essentials.jl:358 
in childstates at AbstractTrees\src\implicitstacks.jl:41
in getnode at AbstractTrees\src\implicitstacks.jl:2

I was able to fix this by defining

Base.getindex(dl::DirectoryListing, i::Int) = dl.names[i]
AbstractTrees.nextind(dl::DirectoryListing, i::Int) = i+1

This fix, however is does not work as in my implementation there is no easy way to predict the location of the i-th sibling in the underlying buffer.

What are the ambitions of this package? Does it aspire to define the vocabulary and interface for all tree implementations (as AbstractArrays tries to accomplish for Indexables)? Or would you advise to start a separate package. I would like to avoid proliferation of the package ecosystem with similar but different concepts if possible...

Is this framework written for convenience or is it also suitable for high performance large scale trees? If all nodes are of the same type, will the framework take advantage of this?

In the not too distant future I'll publish a blog post that requires #65. It would be good to get a new release before then. However, I've not paid close attention to developments here so I'll defer to @jlumpe about where we stand on that score.

dfeault should be default.

Hello,

maybe tests should not simply call print_tree but also assert that it's correctly printing.

Kind regards

I noticed the following docstring was incomplete:

OPTIONAL: Type inference is used to attempt to

Ok, I have started digging into Keno's overhaul of this package.

So far the only major problem (at least according to me, we'll have to debate this) that I have noticed is that the fallback of children is the identity if the object is iterable.

One of the side effects of this was already causing problems: the package had to explicitly "opt out" for objects such as String which are iterable but not trees. That means the package has been "opt out" instead of "opt in" which seems pretty scary.

Anyway, I'm working through changing this now, I'll have more to say on what the implications of this are after I've gotten a bit further.

Hi,

I'm looking at these lines:

https://github.com/Keno/AbstractTrees.jl/blob/master/src/traits.jl#L34-L35

treekind(tree::Type) = RegularTree()
treekind(tree) = treekind(typeof(tree))

Maybe I am missing something, but it looks like

treekind(tree)

will always return RegularTree().

I'm in the process of making RegularTree and IndexTree abstract types (see #24) and it is more work that I expected 😅 (see also #23)

If RegularTree and IndexedTree are abstract types, it seems some of the code becomes simpler because you can do things like isa(tree,IndexedTree) and don't need treekind.

The example in the StableNode documentation here does not run.

t = [1, [2,3]]

node = StableNode(Union{Int,Nothing}, t) do n
    n isa Integer ? convert(Int, n) : nothing
end

ERROR: MethodError: no method matching StableNode(::var"#7#8", ::Type{Union{Nothing, Int64}}, ::Vector{Any})