Союз-находка в структуре графа

У меня есть запись, описывающая граф как наборы узлов и ребер:

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 (которую я мог бы легко обновить при добавлении ребра), потому что я хочу сопоставить связанные компоненты, поэтому быть полезным, чтобы держать их как набор множеств. И, конечно, я хочу получить компонент для node.

Я нашел библиотеку 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 очень наивно, должно быть возможно получить все классы эквивалентности из внутренней структуры данных напрямую.

И, что еще более важно: как сохранить отношение эквивалентности в моей структуре данных?

Ответы

Ответ 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 persistent является удивительной идеей, рассмотренной Conchon, которая также включает в себя реализацию, доказанную в Coq. В принципе, если вы используете массивы с обратными разностями, вы получаете постоянные массивы, которые имеют производительность линейных массивов aa Clean, но могут использовать их в постоянный путь за счет логарифмического замедления. Таким образом, они подходят для реализации вещей union-find, которые включают множество императивных побочных эффектов в чисто функциональном виде.