如何在没有额外间接的情况下在Clojure中创建循环(和不可变)数据结构？

Question

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

只要我进行拓扑排序并"从叶子上"构建每个图形,我就可以用这种方法构造有向无环图.

但是,这种方法不适用于循环图.我能想到的一个解决方法是为整个图形设置一个单独的集合(可能是地图或矢量).然后:edges,每个节点中的字段将具有键(或索引)到图的边集合中.添加这种额外的间接级别是有效的,因为我可以在他们(将)引用的东西之前创建密钥(或索引),但它感觉就像一个kludge.每当我想要访问一个相邻节点时,我不仅需要进行额外的查找,而且还必须传递全局边缘集合,这感觉非常笨拙.

我听说有些Lisps有办法创建循环列表而不需要使用变异函数.有没有办法在Clojure中创建不可变的循环数据结构？

Answer 1

您可以将每个节点包装在ref中,以便为其指定一个稳定的句柄(并允许您修改可以以nil开头的引用).然后可以以这种方式构建循环图.当然,这确实有"额外"的间接性.

我不认为这是一个非常好的主意.你的第二个想法是更常见的实现.我们构建了这样的东西来保存RDF图,并且可以在核心数据结构和层顶部索引的基础上构建它而不需要太多努力.

Answer 2

过去几天我一直在玩这个游戏.

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

然后我尝试了另一种方法,这是其他地方提到的矩阵的变体.该图是一个clojure映射,其中键是节点(不是节点的refs),值是另一个映射,其中键是相邻节点,每个键的单个值是该节点的边缘,表示为表示边缘强度的数值,或我在别处定义的边缘结构.

看起来像这样,有点像 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保存.我不必提出任何索引方案或公​​共参考点.地图的键和值是它们代表的东西,而不是其他地方的查找或参考.您的节点结构可以是所有nils,只要它是唯一的,它就可以在图中表示.

我看到的唯一不利的缺点是,对于任何给定的操作(添加,删除,任何算法),您不能只是将它作为起始节点传递.你必须传递整个图形图和一个起始节点,这可能是一个公平的代价,以支付整个事物的简单性.另一个小缺点(或者可能不是)对于无向边缘,您必须在每个方向上定义边缘.这实际上没问题,因为有时边缘对每个方向都有不同的值,这个方案允许你这样做.

我在这里看到的唯一另一件事是因为边缘隐含在地图中键值对的存在中,所以无法定义超边界(即连接超过2个节点的超边界).我不认为这是一个大问题,因为我遇到的大多数图算法(全部？)只处理连接2个节点的边缘.