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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
