stevensonmt
B-tree like structure for paths through grid
I’m trying to reason through a problem that requires tracing a path between two points with any number of detours possible as long as the endpoints are met. What I thought would be reasonable would be something like %MyTreeThing{coord: {int, int}, val: bool, children: [%MyTreeThing{}]} where the val determines whether a given coordinate allows the path to continue. The children should be restricted to coordinates N, S, E, W, NW, NE, SW, SE from the current coordinate. This is all doable (enforceable via constructor functions if not type limitations) but I don’t know an efficient way to prevent the formation of infinite loops. You could check all parent nodes to the root for every insertion but that seems inefficient. Any suggestions on how to do this or is this just an entirely wrong approach?
Trending in Questions
Other Trending Topics
Latest on Elixir Forum
Sponsor Spotlight
Catch errors, track performance, monitor hosts and more.
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
- #phoenix_html
- #iex
- #blog-post
- #graphql
- #genstage
- #ai
- #websockets
- #elixirconf-us
- #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.
Producing high quality Elixir screencasts since 2017.
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 4 of 4 Posts!
LostKobrakai
You could create a
:digraphgraph and use:digraph_utils.is_acyclic/1.stevensonmt
Thanks! I was actually just reading through the source for libgraph and it looks like it basically does check for inclusion of a vertex in the “out neighbors” to ensure a path is acyclic. I’ll try to look into
:digraphas well.mpope
If by infinite loop, do you mean this should be specifically a DAG, with no child node referencing a node above it? If so, you could use a MapSet to verify that the current node that you’re adding hasn’t already been added to the graph. Its a pretty blunt approach, because it sounds like not all nodes will have all coordinates filled and loops could be prevented in a more sophisticated way, but maybe you could come up with a series of sets to check.
stevensonmt
I like that idea. I was thinking about having a map of neighbors for each vertex and a map of parents for each path. As a path gets constructed it would check the parents map to ensure no cyclical paths are allowed.