stevensonmt

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?

Most Liked

LostKobrakai

LostKobrakai

You could create a :digraph graph and use :digraph_utils.is_acyclic/1.

mpope

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

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.

Where Next?

Popular in Questions Top

itssasanka
Hi all, Trying to get some more clarity over utc_datetime and naive_datetime for Ecto: https://hexdocs.pm/ecto/Ecto.Schema.html#module-...
New
tduccuong
Hi, is there any work on GUI with Elixir, that is similar to Electron/Javascript? My idea is to bundle Phoenix and BEAM into a single se...
New
lk-geimfari
What is most correct way to open, read and parse JSON file with poison? For example if we have example.json file in root of some projec...
New
vac
Hi, I'm quite new in Elixir and I'm trying to format a string to a PEM format. I have the certificate value like MIIDBTCCAe2...... and ...
New
minhajuddin
I have seen a lot of code which picks the first element from a list using Enum.at(0) instead of List.first. Is there a reason why people ...
New
ashish173
I am using Ecto timestamps with postgres, I can see the timestamps() use the :naive_dateime but for my use case I wanted to store the ti...
New
qwerescape
Is there a way to get the call stack or stack trace at any point in the code? Not from exceptions, but an expression that returns how the...
New
Fl4m3Ph03n1x
Background Let’s assume I have a typical GenServer that receives messages as requests, does some operation in a DB and returns responses....
New
shahryarjb
Hello, I have map which I want to convert it to string like this: the map: %{last_name: "tavakkoli", name: "shahryar"} the string I ne...
New
chewm
Hi guys, nice to meet you to the whole forum, I’m new here, I’m trying to configure visual studio code for elixir, right now the intellis...
New

Other popular topics Top

dotdotdotPaul
Okay, I'm having a heck of a time trying to figure out how to best handle the validation of belongs_to associations in Ecto. I'm sure I'...
New
JorisKok
I have a server on AWS, and was running a load test using artillery. When looking at the Phoenix dashboard I see the Ports going to 100% ...
New
sergio
I couldn’t find any guides that worked well with Phoenix 1.6.0 and esbuild. I hope this helps people test the waters and eases you into t...
New
Jim
As a follow up to my earlier question: I have the code compiling and running but not getting a successful login from the rest server. ...
New
lk-geimfari
What is most correct way to open, read and parse JSON file with poison? For example if we have example.json file in root of some projec...
New
stefanchrobot
What’s the safe way to decode a JSON string into a struct? I want to avoid calling String.to_atom. Jason.decode can give me a map with st...
New
vac
Hi, I'm quite new in Elixir and I'm trying to format a string to a PEM format. I have the certificate value like MIIDBTCCAe2...... and ...
New
aadeshere1
I have a another noob question about loop. Since elixir is immutable, while loop is not directly possible. total = 10 while total != 0 ...
New
fayddelight
I tried installing elixir 1.11.2 erlang 23.3.4 via asdf in my zsh shell. Enabled the versions locally and globally. When I list them ...
New
stefanluptak
Hello everybody, usually, I use a 29" ultra-wide monitor for VSCode which can easily accomodate explorer (files panel) + file with code ...
New

We're in Beta

About us Mission Statement