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