Back

@alter_kaker @UP8 I've had to do with mutable graphs in a different context (code generation from a graph based intermediate representation, matching subgraph patterns and rewriting them in the while, usually emitting instructions as side effect of the match/replace step). I've not seen a special name for the graph data structure.

@alter_kaker @UP8 Though there was a twist because one would not greedily match, replace, emit instructions, but search for a good or optimal sequence. So there was a second graph (DAG) representing the different possible sequences, generated as needed and used to search the optimal or a near optimal solution.

@alter_kaker @UP8 (And the matches were generated from a special description language)

@alter_kaker @project1enigma giving the data structure a name only makes sense once you know what the data structure is, but if it is a graph that gets changed by a program I might say it is a "dynamic graph"; if you can make the program simple and put the complexity into a fixed data structure that would be all the better

@UP8 @alter_kaker If you don't need to explore different possible changes, you can modify things in place. You need more complex things like persistent data structures or purely functional ones or undo stacks or similar only if you do things like the search for an optimum modification sequence I described.

@UP8 @alter_kaker In my case, the actual intermediate representation graph was IIRC never really changed. Just the solution search graph was built and the nodes/edges of that had enough information to know, together with the original IR, how to try potential next matches.

@UP8
For example, finding paths, like what
@project1enigma was describing

@alter_kaker @UP8 I'm still not sure if you need backtracking/undo.

Or if you just have your graph and some "player"/agent/cursor walking through it while each step can possibly enable/disable some edge or node elsewhere (but no undo)?

@alter_kaker @UP8 The latter case should be easier. Like if it's just enabling/disabling edges/nodes I might just add a bool enabled everywhere and respect it in the code that moves the cursor/agent around.

@project1enigma
Right, but I also want my agent to be able to plan, so I need a pathfinding algorithm that takes into account the graph changes
@UP8

@alter_kaker @UP8 Ah yeah. A general term would be persistent data structure, IIRC.

Another thing would be zippers (in the context of pure functional programming though zippers are usually for local modifications).

@alter_kaker @UP8 Alternatively you do modify things in place but have undo information on your stack.