sschuldenzucker
Hey all, I’m building my own little app (side project) and I’m looking for a tree data structure. I’m honestly wondering if I’m overlooking something but I couldn’t find a library that’s right for me.
The whole thing should be “generic” (think, like a DOM), i.e., like this:
- Arbitrary number of children per node.
- Children are ordered.
- Easy to traverse. E.g. there should be “get sibling right after this”, “get parent” etc.
- Effiiciently find child by node ID (no zipper; I wanna build a microservice that manages the tree)
I could use a digraph from Erlang but it’s actually too flexible for my use case and would require a wrapper around it to make sure nobody’s creating a loop.
In particular 5. seems hard to satisfy with the libraries I found.
Do you guys agree that there’s currently no library that does this? Any advice on how I would build this without going crazy?
Thanks a lot!
Where Next?
Trending in Questions
Other Trending Topics
Latest on Elixir Forum
Sponsor Spotlight
Error tracking, logs, APM, uptime and cron monitoring in one dev-friendly platform. Find and fix problems before your users notice.
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #deployment
- #library
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #channels
- #elixirconf
- #exunit
- #discussion
- #code-sync
- #javascript
- #podcasts
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ecto-query
- #elixir-ls
- #blog-post
- #phoenix_html
- #iex
- #graphql
- #ai
- #genstage
- #elixirconf-us
- #websockets
- #supervisor
- #advent-of-code
- #distillery
- #processes
- #api
- #forms
- #metaprogramming
- #security
- #hex
Our Sponsors
Build Elixir applications with speed and confidence.
Supporting innovation across the BEAM ecosystem.
We build reliable cloud platforms for business-critical systems.
Catch errors, track performance, monitor hosts and more.
Error tracking, logs, uptime, and Just Enough APM. Built for developers.
Practical resources that improve the lives of professional developers.
Develop your skills with books, videos, and courses.
Enabling companies to succeed by building software people love.
The team behind Membrane, Popcorn, LiveDebugger. Available for hire.
Courses that'll move you from confusion to "Aha, now I get it!"
First 5 of 5 Posts
al2o3cr
Not sure I’m following the problem here - you can pass
:acyclicto:digraph.new/1and the library will handle enforcing that restriction.I only see 4 numbered bullet points, did something get lost in editing?
“Generic” is hard. Different implementations are going to have seriously different performance (both time and space) for specific operations.
For instance, a tree implemented as a closure table can answer queries like “what are all the descendants of this node” very efficiently. But moving a subtree in that implementation is very slow, because it needs to touch many rows for each element of the subtree.
An adjacency-list representation (aka “put a
parent_idcolumn on the record”) has the opposite properties: moving an entire subtree only needs to update theparent_idon the subtree’s root, but checking for descendants requires recursive CTEs or other SQL trickery.sschuldenzucker
Hey, thx for the pointers.
Regarding
:acyclic: This would definitely make it better but acyclic digraphs can still have undirected cycles (two nodes pointing to the same child), so it’s not enough. I guess you can get around that by restricting the access methods a bit more (e.g., don’t allow adding edges, just moving nodes).Oh, and in a digraph, the children of a node (aka. the edges going out of a node) are not ordered, right?
Regarding 5., this should’ve been 4. (no zippers).
Regarding “generic”, of course you’re right. I think for my use case, local operations (what’s the parent / next sibling / children / etc.; move this subtree somewhere else) should be enough. So adjacency lists are probably the way to go.
I suppose all of these things are not fundamentally hard, was just wondering if someone already did it.
petrus-jvrensburg
Would the Postgres Ltree datatype help?
sschuldenzucker
NB I’ve built something based on IDs (essentially doing the usual pointer rotations in a set of maps). Will publish something not too far out.
user20230119
Did you publish something?