Union-find in a graph structure

Question

I have a record describing a graph as sets of nodes and edges:

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

Since I won't ever remove edges, I want to track the connected components using a union-find structure (which I could easily update when adding an edge), because I want to map over the connected components, so it would be useful to keep them as a set of sets, too. And of course I want to get the component for a node.

I found the equivalence library, which I chose because I can't see how I would create sets with union-find and persistent-equivalence needs to know the value range.

Now I can create relations, and return the set of sets using:

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"]]

But: using fromList is very naive, it should be possible to get all equivalence classes from the internal data structure directly.

And, more importantly: how can I store the equivalence relation in my data structure?

Answer 1

One option would be to use 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)
}

I find the use of Ix a little annoying here, but if it works for your purposes then go with it. Making union-find persistent is an awesome idea explored by Conchon which also includes an implementation proven correct in Coq. Basically, if you use reverse difference arrays, you get persistent arrays that have the performance of linear arrays a la Clean but can use them in a persistent way at the cost of logarithmic slow down. Thus, they are suitable for implementing things union-find that involve lots of imperative side effects in a pure functional way.