Data.Graph nitpicks

Milan Straka fox at
Tue Feb 10 06:37:49 UTC 2015

Hi all,

> -----Original message-----
> From: Andreas Voellmy <andreas.voellmy at>
> Sent: 9 Feb 2015, 18:15
> Hi folks,
> I was just using the stronglyConnComp function in Data.Graph and found some
> minor annoying things:
> 1. stronglyConnComp takes an out-list as input. On the other hand, none of
> the other graph algorithms, like dfs, etc do this. stronglyConnComp seems
> to basically be an algorithm on graphs, so why doesn't it take the graph as
> input? Can we change stronglyConnComp to take a graph as input? That would
> make the interface more uniform.

the reasons for that are probably historical. The stronglyConnComp[R],
SCC type and flattenSCC[s] are an completely independent part of
Data.Graph which I suspect was there first and was kept after the rest
of Graph algorithm arrived.

As David wrote, it is probably not worth it changing stronglyConnComp
(there is some code using it and I see no benefit in breaking it for
aesthetic reasons).

If you want strongly connected components on Graph, you can use `scc`
method. It does return Forest and not SCC, but it is quite trivial to
convert the result.

> 2. Why is stronglyConnComp in a special haddock section whereas all the
> other algorithms are in the "Algorithms" section? How about we group it
> with all the other algorithms?

This is because the stronglyConnComp is an independent part of Graph, so
it is documented independently. I think we should leave it that way.

> 3. Why are there are so few instances of SCC? In particular, why not derive
> Show and Eq?

Probably no one needed them :-)

If you want to work with strongly connected components, you can also use
the `scc`, where the resulting `Forest` has a reasonable set of

We can also add the instances to SCC. However note that it is
questionable how the Eq instance should look like.


More information about the Libraries mailing list