联合查找图形结构

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) -- ?
}

由于我不会删除边缘,我想使用union-find结构跟踪连接的组件(我可以在添加边缘时轻松更新),因为我想映射连接的组件,因此它将是有用的将它们保存为一组.当然,我想获得一个节点的组件.

我发现了我选择的等价库,因为我无法看到如何使用union-find创建集合,而持久性等价需要知道值范围.

现在我可以创建关系,并使用以下命令返回集合:

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有点烦人，但如果它适合你的目的，那就用它吧。让 union-find 持久化是Conchon探索的一个很棒的想法，其中还包括在 Coq 中被证明是正确的实现。基本上，如果您使用反向差分数组，您将获得持久数组，该数组具有干净的线性数组的性能，但可以以持久方式使用它们，但代价是对数减慢。因此，它们适合以纯函数方式实现涉及许多命令性副作用的联合查找。