haskell - 图结构中的并查找

Question

我有一条记录将图描述为节点和边的集合:

data MyGraph a = MyGraph {
  nodes :: Set a,
  edges :: Set (a,a),
  components :: UnionFindM a -- ?
}
emptyGraph = MyGraph{
  nodes = empty, edges = empty,
  components = emptyUnionFind singleton union --?
}
addEdge g (a,b) = g{
  edges = (a,b) `insert` (edges g),
  components = (components g) >>= (equate a b) -- ?
}

由于我永远不会删除边缘，所以我想使用联合查找结构来跟踪连接的组件(在添加边缘时我可以轻松更新该结构)，因为我想映射连接的组件，所以它会将它们保留为一组也很有用。当然，我想获取节点的组件。

我找到了equivalence库，我选择它是因为我看不到如何使用 union-find 创建集合和 persistent-equivalence需要知道值范围。

现在我可以创建关系，并使用以下方法返回集合:

import Control.Monad(liftM)
import Data.Equivalence.Monad
import Data.Set(singleton, union, fromList)
f = runEquivM singleton union $ do
  equate "foo" "bar"
  equate "bar" "baz"
  (liftM fromList) $ mapM classDesc ["foo","bar","baz","one","two"]

>>> f
fromList [fromList ["bar","baz","foo"],fromList ["one"],fromList ["two"]]

但是:使用fromList非常幼稚，应该可以直接从内部数据结构中获取所有等价类。

更重要的是:如何在数据结构中存储等价关系？

Answer 1

一种选择是使用Data.Equivalence.Persistent

data MyGraph a = MyGraph {
  nodes :: Set a,
  edges :: Set (a,a),
  components :: Equivalence a
}
emptyGraph :: Ix a => (a, a) -> MyGraph a
emptyGraph range = MyGraph{
  nodes = empty, edges = empty,
  components = emptyEquivalence range
}
addEdge :: Ix a => MyGraph a -> (a, a) -> MyGraph a
addEdge g (a,b) = g{
  edges = (a,b) `insert` (edges g),
  components = equate a b (components g)
}

我发现这里使用 Ix 有点烦人，但如果它适合您的目的，那么就使用它。使并查找持久化是一个很棒的想法，由 Conchon 探索过。其中还包括在 Coq 中被证明正确的实现。基本上，如果您使用反向差分数组，您将获得具有线性数组性能的持久数组 Clean但可以以持久的方式使用它们，但代价是对数减慢。因此，它们适合以纯函数方式实现 union-find 涉及大量命令式副作用的事物。