directed acyclic graphs - Traverse through a DAG-like structure to produce another DAG-like structure in Clojure -

directed acyclic graphs - Traverse through a DAG-like structure to produce another DAG-like structure in Clojure -

i have dag-like construction deeply-nested map. maps in construction can have mutual values, overall construction not tree direct acyclic graph. i'll refer construction dag brevity.

the nodes in graph of different finite number of categories. each category can have own structure/keywords/number-of-children. there 1 unique node source of dag, meaning node can reach nodes in dag.

the task traverse through dag source node, , convert each node 1 or more nodes in new constructed graph. i'll give illustration illustration.

the graph in upper half input one. lower half 1 after transformation. simplicity, transformation done on node split node 1 , a1. children of node reallocated.

what have tried (or in mind):

write function convert 1 object different types. within function, recursively phone call convert each of children. method suffers problem info immutable. nodes in transformed graph cannot changed randomly add together children. overcome this, need wrap every node in ref/atom/agent. do topological sort on original graph. convert nodes in reversed order, i.e., bottom-up. method requires traverse of graph @ to the lowest degree info need not mutable. regarding topological sort algorithm, i'm considering dfs-based method stated in wiki page, not require knowledge of total graph nor node's parents.

my question is:

is there other approaches might consider, perchance more elegant/efficient/idiomatic? i'm more in favour of sec method, there flaws or potential problems?

thanks!

edit: on sec thought, topological sorting not necessary. transformation can done in post-order traversal already.

this looks perfect application of zippers. have capabilities described needed , can produce edited 'new' dag. there number of libraries ease search , replace capability using predicate threads.

i've used zippers when working owl ontologies defined in nested vector or map trees.

another alternative take @ walkers although i've found these bit more tedious use.

clojure directed-acyclic-graphs