在 Clojure 中遍历一个 DAG-like 结构以产生另一个 DAG-like 结构
Traverse through a DAG-like structure to produce another DAG-like structure in Clojure
我有一个类似于 DAG 的结构，它本质上是一个深层嵌套 map。这个结构中的图可以有共同的值，所以整体结构不是树而是有向无环图。为简洁起见，我将此结构称为 DAG。
此图中的节点属于不同但数量有限的类别。每个类别都可以有自己的 structure/keywords/number-of-children。有一个唯一的节点是这个 DAG 的源，意味着从这个节点我们可以到达 DAG 中的所有节点。
任务是从源节点遍历DAG，将每个节点转换为新构造图中的另一个或多个节点。我举个例子来说明。
上半部分的图是输入图。下半部分是改造后的。为简单起见，仅在节点 A 上进行转换，将其拆分为节点 1 和 A1。节点 A 的子节点也被重新分配。
我尝试过的（或想到的）：
- 编写一个函数将一个对象转换为不同的类型。在此函数内部，递归调用自身以转换其每个子项。这种方法存在数据不可变的问题。变换后的图中的节点不能随机更改以添加子节点。为了克服这个问题，我需要将每个节点包装在 ref/atom/agent.
中
- 对原图进行拓扑排序。然后以相反的顺序转换节点，即自下而上。此方法需要额外遍历图形，但至少数据不需要是可变的。关于拓扑排序算法，我正在考虑 wiki 页面中所述的基于 DFS 的方法，它不需要完整图的知识，也不需要节点的父节点。
我的问题是：
- 您是否可以考虑其他任何方法，可能更多 elegant/efficient/idiomatic？
- 我比较赞同第二种方法，有没有什么缺点或者潜在的问题？
谢谢！
编辑：再想想，拓扑排序是没有必要的。转换已经可以在post阶遍历中完成。
我有一个类似于 DAG 的结构，它本质上是一个深层嵌套 map。这个结构中的图可以有共同的值，所以整体结构不是树而是有向无环图。为简洁起见，我将此结构称为 DAG。
此图中的节点属于不同但数量有限的类别。每个类别都可以有自己的 structure/keywords/number-of-children。有一个唯一的节点是这个 DAG 的源，意味着从这个节点我们可以到达 DAG 中的所有节点。
任务是从源节点遍历DAG，将每个节点转换为新构造图中的另一个或多个节点。我举个例子来说明。
上半部分的图是输入图。下半部分是改造后的。为简单起见，仅在节点 A 上进行转换，将其拆分为节点 1 和 A1。节点 A 的子节点也被重新分配。
我尝试过的（或想到的）：
- 编写一个函数将一个对象转换为不同的类型。在此函数内部，递归调用自身以转换其每个子项。这种方法存在数据不可变的问题。变换后的图中的节点不能随机更改以添加子节点。为了克服这个问题，我需要将每个节点包装在 ref/atom/agent. 中
- 对原图进行拓扑排序。然后以相反的顺序转换节点，即自下而上。此方法需要额外遍历图形，但至少数据不需要是可变的。关于拓扑排序算法，我正在考虑 wiki 页面中所述的基于 DFS 的方法，它不需要完整图的知识，也不需要节点的父节点。
我的问题是：
- 您是否可以考虑其他任何方法，可能更多 elegant/efficient/idiomatic？
- 我比较赞同第二种方法，有没有什么缺点或者潜在的问题？
谢谢！
编辑：再想想，拓扑排序是没有必要的。转换已经可以在post阶遍历中完成。