19

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

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

但是，这种方法不适用于循环图。我能想到的一种解决方法是对整个图形的所有边进行单独的集合（可能是地图或矢量）。然后，每个节点中的:edges字段将具有进入图形边缘集合的键（或索引）。添加这种额外的间接级别是可行的，因为我可以在它们（将）引用的东西存在之前创建键（或索引），但感觉就像是一个杂物。不仅每次要访问相邻节点时都需要进行额外的查找，而且还必须绕过全局边缘集合，感觉非常笨拙。

我听说有些 Lisps 可以创建循环列表，而无需借助变异函数。有没有办法在 Clojure 中创建不可变的循环数据结构？

4

3 回答 3

7

You can wrap each node in a ref to give it a stable handle to point at (and allow you to modify the reference which can start as nil). It is then possible to possible to build cyclic graphs that way. This does have "extra" indirection of course.

I don't think this is a very good idea though. Your second idea is a more common implementation. We built something like this to hold an RDF graph and it is possible to build it out of the core data structures and layer indices over the top of it without too much effort.

于 2011-01-03T02:30:28.723 回答
6

最近几天我一直在玩这个。

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

然后我尝试了另一种方法，它是其他地方提到的矩阵的变体。该图是一个 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

要访问 node-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 个节点的边。

于 2012-04-20T08:27:23.803 回答
3

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

但是，您可能会发现以下一个或多个选项是可以接受的：

  • 使用带有 ":unsynchronized-mutable" 的 deftype 在每个节点中创建一个可变的 :edges 字段，在构建期间您只更改一次。从那时起，您可以将其视为只读，没有额外的间接开销。这种方法可能会有最好的性能，但有点 hack。
  • 使用原子来实现 :edges。有一点额外的间接性，但我个人发现读取原子非常有效。
于 2011-01-03T18:07:19.917 回答