Union-find в графовой структуре

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

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 и persistent- эквивалентность должна знать диапазон значений.

Теперь я могу создавать отношения и возвращать набор наборов, используя:

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

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


haskell union-find
person pascal    schedule 11.10.2012    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

person Philip JF    schedule 12.10.2012
comment
Спасибо за бумаги! Забыл упомянуть в своем вопросе: я заранее не знаю размер графика, поэтому persistent-equivalence также не подходит, так как он должен знать диапазон при построении... - person pascal; 12.10.2012