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: <>.


Haskell-Cafe mailing list

Reply via email to