10

我有一条记录，将图形描述为一组节点和边：

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创建集合，而持久等价需要知道值范围。

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

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非常幼稚，应该可以直接从内部数据结构中获取所有等价类。

而且，更重要的是：如何将等价关系存储在我的数据结构中？

4

1 回答 1

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 中被证明是正确的实现。基本上，如果您使用反向差分数组，您将获得具有线性数组性能的持久数组，但可以以对数减慢为代价以持久方式使用它们。因此，它们适用于以纯函数方式实现涉及大量命令式副作用的 union-find 事物。

于 2012-10-12T08:55:51.870 回答