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
You could create a :digraph graph and use :digraph_utils.is_acyclic/1.
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.







