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 構造 (エッジを追加するときに簡単に更新できます) を使用して接続されたコンポーネントを追跡したいと思います。それらもセットのセットとして保管してください。そしてもちろん、ノードのコンポーネントを取得したいと考えています。

等価ライブラリを見つけました。これを選択したのは、 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は非常に単純です。内部データ構造からすべての等価クラスを直接取得できるはずです。

さらに重要なことは、データ構造に同値関係を格納するにはどうすればよいかということです。

4

1 に答える 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 で正しいことが証明された実装も含まれています。基本的に、逆差分配列を使用すると、クリーンな線形配列のパフォーマンスを持つ永続的な配列が得られますが、対数的な速度低下を犠牲にして、永続的な方法でそれらを使用できます。したがって、それらは、純粋に機能的な方法で多くの命令的な副作用を伴う共用体検索を実装するのに適しています。

于 2012-10-12T08:55:51.870 に答える