[Haskell-cafe] Operations on functional graphs

[Francesco Mazzoli]

At Wed, 24 Apr 2013 13:02:39 +0100,
Francesco Mazzoli wrote:
> Hi list,
> 
> I’ve been lately thinking about how to implement an algorithm efficiently, and I
> need a directed graph that can perform the following tasks:
> 
>   1. Finding the strongly connected components
>   2. Condensing strongly connected components
>   3. Contract single edges
> 
> The condensing shouldn’t prevent successive operations to work with the
> condensed vertices (treating them all as the same), but should get rid of the
> edges.
> 
> Point one is easy, for example as described in [1].  I’m wondering if a nice way
> to implement the other two with functional structures has been described.  I’d
> guess it would be a mix of a graph and disjoint sets data structure...

In the end I solved point 2 the ‘stupid’ way: I have a ‘representative’ node for
each condensed SCC, and when I condense I chose a new representative for all the
members of the SCC in question and then I traverse the all the successors list
updating and merging stale representatives.  The code is here, in case anyone’s
interested: <https://github.com/bitonic/kant/blob/master/src/Data/LGraph.hs>.

Francesco