Francesco Mazzoli | 24 Apr 14:02 2013
Picon

Operations on functional graphs

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

Thanks,
Francesco

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

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Francesco Mazzoli | 27 Apr 22:35 2013
Picon

Re: Operations on functional graphs

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 <at> haskell.org
(Continue reading)


Gmane