Look into alternative tree implementations

[clbarnes]

For possible improved performance, memory size, safety, readability.

Some results for "tree" on cargo:

• trees
• id_tree
• outils
• slab_tree

Wants

• Associate arbitrary data with node (something better than a handful of free-floating HashMaps)
• Optionally weighted edges
• Algorithms like DFS, maybe partitioning
• Maybe mutability?

[clbarnes]

Implementation review

rosetree

• based on petgraph
  • probably flexible and robust
  • arbitrary metadata on nodes
  • probably not the fastest
• not popular (1732 downloads)
• sibling, children, rootward path iterators but no algorithms

outils

• Has DynamicGraph with easy insertion/deletion, but this recalculates tree often?
• unpopular (698 downloads)

synctree

• threadsafe (probably not necessary)
• unpopular
• ergonomic creation macro
• built-in children, ancestors, DFS algos

id_tree

• popular
• ancestors, children, sub-tree traversal (pre, post-order)
• "Sadly, Rust's ownership/reference system is sidestepped a bit by this implementation and this can cause issues if the caller doesn't pay attention to what they are doing with NodeIds."

slab_tree

• unpopular
• sibling-based

note also

pathfinding

• Some algorithms
• not great docs

[aschampion]

Very tangentially related thing that might be useful for debugging if you stick with a petgraph-based tree lib: plotting petgraphs in jupyter

[clbarnes]

Ah, yeah, that could be handy.

I'm considering rescoping this attempt to just manage morphology-related stuff for now - dict lookups could be quicker in python, so traversal based on them isn't a great idea, which becomes a problem for looking at large numbers of skeletons. Immutable graph which gets cloned for rerooting, pruning etc. Remains to be seen whether the overhead of converting into a rust data structure would be made back from the algorithm speed, but i suspect it would.

[clbarnes]

Adding to the pile:

ego_tree

• Very popular
• Poorly documented
• "Nodes can be detached (orphaned) but not removed"

trees

• Lots of traversals already implemented
• 3 implementations, could tune for performance

read_tree

• Not very popular
• Read-only

I'm leaning towards slab-tree. It has stable indices through both insertions and deletions (essential for e.g. caching branch points), it's safe, and has good traversal options. However, it's not widely used, and can't store edge weights.

These mainly require knowing the tree structure before you build it (i.e. not from a bag of edges), so I'll probably need to keep some of the hashmap-based algorithms anyway just to build it.

At a minimum, we'd need to store:

• tree object <NodeType=(tnid, location)>
• tnid -> internal index mappings HashMap<usize, tnid>

Then we could additionally cache:

• edge lengths Option<HashMap<(NodeIdx, NodeIdx), float>>
• branches Option<HashSet>
• leaves Option<HashSet>
• depth (hops) Option<HashMap<NodeIdx, usize>>
• depth (distance) Option<HashMap<NodeIdx, f64>>

I think these could all be initialised on construction at little CPU cost if we're willing to spare the memory.

[clbarnes]

indextree

• No removals (see indextree-ng for removals - requires hashmap lookups)
• Popular, stable
• Lots of iterators
• BUT unclear documentation