[Haskell-cafe] Operations on functional graphs

Francesco Mazzoli f at mazzo.li
Wed Apr 24 14:02:39 CEST 2013

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

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


[1]: Structuring Depth-First Search Algorithms in Haskell, by David King and
John Launchbury.

More information about the Haskell-Cafe mailing list