stevensonmt
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?
Where Next?
Trending in Questions
Other Trending Topics
Latest on Elixir Forum
Sponsor Spotlight
Deploy Phoenix to your own VPS with PaaS ease: push-to-deploy, zero downtime, auto SSL, managed Postgres. 14-day free trial at potions.io
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #library
- #deployment
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #elixirconf
- #channels
- #exunit
- #discussion
- #code-sync
- #podcasts
- #javascript
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ai
- #ecto-query
- #elixirconf-us
- #blog-post
- #elixir-ls
- #phoenix_html
- #iex
- #graphql
- #genstage
- #websockets
- #supervisor
- #advent-of-code
- #distillery
- #processes
- #elixirconf-eu
- #api
- #forms
- #metaprogramming
- #hex
Our Sponsors
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.
Elixir, Erlang & BEAM conferences from Code Sync - join us in 2026!
Practical resources that improve the lives of professional developers.
Bringing learning, work and compliance together since 1987.
Producing high quality Elixir screencasts since 2017.
The team behind Membrane, Popcorn, LiveDebugger. Available for hire.
Courses that'll move you from confusion to "Aha, now I get it!"
Showing Posts 1 to 4- Show Best Posts
- Show All (oldest first)
- Show All (newest first)
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.