如何在Clojure中创建循环（且不可变）的数据结构而无需额外的间接引用？

Question

我需要在Clojure中表示有向图。我想将图中的每个节点表示为一个对象（可能是一个记录），其中包括一个名为:edges的字段，它是从当前节点直接可达的节点的集合。希望不用说，但我希望这些图是不可变的。

使用这种方法，我可以构建有向无环图，只要进行拓扑排序并从“叶子向上”构建每个图。

然而，这种方法对于循环图不起作用。我能想到的一个解决方法是，使用一个单独的集合（可能是地图或向量）来保存整个图的所有边缘。每个节点中的:edges字段将具有指向图的边缘集合的键（或索引）。添加这个额外的间接级别是有效的，因为我可以在它们（将）引用之前创建键（或索引），但感觉像是一个临时解决方案。不仅每当我想访问相邻节点时都需要做一次额外的查找，而且我还必须传递全局边缘集合，这感觉非常笨拙。

我听说有些Lisp语言有一种创建循环列表的方法，而不必使用突变函数。在Clojure中有一种创建不可变循环数据结构的方法吗？

- Laurence Gonsalves

---

你需要什么样的不可变性？如果你在函数内构建循环图，那么节点的必要变化是“看不见”的，你会得到一个由函数返回的不可变循环图。请参阅http://clojure.org/transients - Alex Stoddard

@Alex：这听起来是一个非常有趣的方法。如果需要，在构建期间图表可以是可变的，我没问题。我主要想确保它在构建之后是不可变的，这样我就可以毫不担心地将其交给调用者。然而，我还没有找到如何使用transient构建循环数据结构的方法。你有任何示例代码来说明这个想法吗？即使是像向量自身作为元素这样简单的东西？ - Laurence Gonsalves

Answer 1

您可以使用 ref 将每个节点包装起来，以给它一个稳定的句柄指向（并允许您修改最初为空的引用）。这样就可以构建循环图。当然，这确实有“额外”的间接性。

我认为这不是一个非常好的主意。您的第二个想法是更常见的实现方式。我们构建了类似于此的东西来保存 RDF 图，并且可以在不太费力的情况下使用核心数据结构和层索引构建它。

- Alex Miller

Answer 2

最近几天我一直在尝试这个东西。

我首先尝试让每个节点保存对边的引用，每条边保存对节点的引用。我使用 (dosync... (ref-set...)) 这种操作将它们相互设置为相等。但是我不喜欢这个方法，因为更改一个节点需要大量更新，并且打印图形有点棘手。我必须覆盖 print-method 多态方法，以防止repl溢出堆栈。而且，每当我想要向现有节点添加边时，我都必须先从图中提取实际节点，然后进行各种边缘更新和其他事情，以确保每个人都持有另一件事的最新版本。此外，由于事物在引用中，确定某些东西是否连接到其他东西是线性时间操作，这似乎很不优雅。在确定使用此方法执行任何有用的算法之前，我并没有取得很大进展。

然后我尝试了另一种方法，这是矩阵的变体。图是一个Clojure映射，其中键是节点（而不是节点的引用），值是另一个映射，其中键是相邻节点，每个键的单个值是指向该节点的边，表示为指示边强度的数字值或我在其他地方定义的边结构。

对于 1->2, 1->3, 2->5, 5->2，它看起来像这样：

(def graph {node-1 {node-2 edge12, node-3 edge13},
            node-2 {node-5 edge25},
            node-3 nil ;;no edge leaves from node 3
            node-5 {node-2 edge52}) ;; nodes 2 and 5 have an undirected edge

要访问节点1的邻居，您可以使用(keys (graph node-1))或调用在其他地方定义的函数(neighbors graph node-1)，或者您可以使用((graph node-1) node-2)，以获取从1->2的边缘。

几个优点：

1. 在图中查找节点和相邻节点的时间复杂度是常数级别的，如果不存在则返回nil。
2. 简单灵活的边缘定义。当您将相邻节点添加到映射中的节点条目时，有向边缘隐式存在，并且其值（或结构体以提供更多信息）显式提供或为nil。
3. 您不必查找现有的节点才能对其进行任何操作。它是不可变的，因此您可以在将其添加到图形中之前仅定义一次，然后在更改事物时不必追赶最新版本。如果图表中的连接发生更改，则更改图表结构，而不是节点/边缘本身。
4. 这将矩阵表示的最佳特性（图形拓扑结构在图形映射本身中而不是编码在节点和边缘中、常数时间查找和非突变节点和边缘）与邻接表相结合（每个节点“有”其相邻节点的列表、空间效率高，因为没有类似于规范稀疏矩阵的“空白”）。
5. 您可以在节点之间有多个边缘，并且如果意外定义了已经存在的边缘，则映射结构会确保您不重复它们。
6. 节点和边缘标识由Clojure保留。我不必想出任何索引方案或通用参考点。地图的键和值是它们所代表的东西，而不是在其他地方查找的内容或引用。您的节点结构可以全部为nil，只要它是唯一的，就可以在图形中表示它。

我看到的唯一一个大问题是对于任何给定操作（添加、删除、任何算法），您不能只传递起始节点。您必须传递整个图形映射和一个起始节点，这可能是为整个流程提供简单性所需付出的合理代价。另一个小缺点（或者说也许不是）是对于无向边，您必须在每个方向上定义边。实际上，这是可以接受的，因为有时边对于每个方向具有不同的值，而这种方案允许您这样做。

我在这里看到的唯一其他事情是，因为边缘在映射中的键值对存在中是隐含的，所以您不能定义超边缘（即连接多于2个节点的边）。我不认为这一定是大问题，因为我遇到的大多数（全部？）图算法只处理连接2个节点的边。

- Sonicsmooth

---

这是一个非常棒的解决方案。我喜欢它。简单而优雅。 不过有一个小挑战： 假设节点本身是不可变结构，如果您想要更新一个节点，您可能需要使用 dissoc 去除旧节点，并使用旧节点的值将新节点与旧节点进行关联。很容易。但是您还需要在所有引用新节点作为邻居的节点映射中执行相同的操作。 不过这并不难解决。谢谢。 - Terje Dahl

它确实具有额外的间接性。 - Erik Kaplun

Answer 3

我之前遇到过这个问题，并得出结论，在Clojure中使用真正的不可变数据结构目前是不可能的。

然而，您可能会发现以下一个或多个选项可接受：

• 使用带有“:unsynchronized-mutable”参数的deftype，在每个节点中创建一个可变的：edges字段，在构建期间仅更改一次。从那时起，你可以将它视为只读，没有额外的间接开销。这种方法可能会具有最佳性能，但有点像黑客。
• 使用原子(atom)实现：edges。有一点额外的间接性，但我个人发现读取atom非常高效。

- mikera