Data.Graph (and Data.Tree) improvements

Edward Z. Yang ezyang at
Fri Mar 6 21:38:25 UTC 2015

Data.Graph has always been a bit of an unloved module in containers.
However, at GHC HQ the graph has always been a bit of an important data type,
and we've been maintaining basically another version of the module
under the name Digraph.

I was refactoring this module to use Data.Graph and I noticed that there
were a few functions which were conspicuously missing from the module
proper. So here they are:

For Data.Graph:

    - Generalized reachable :: Graph -> [Vertex] -> [Vertex]
      (compare to reachable :: Graph ->  Vertex  -> [Vertex]

    - Returns an undirected version of a graph which, for any
      edge a -> b, an edge b -> a also exists.

          undirected :: Graph -> Graph

    - Extract a list of groups of elements of a graph such that
      each group has no dependence except on nodes in previous groups
      (i.e. they may not depend on nodes in their own group) such
      that the groups are maximal.  No solution exists for cyclic

        vertexGroups :: Graph -> [[Vertex]]

For Data.Tree

    - preorderF :: Forest a -> [a]
        (or perhaps flattenF, to keep naming consistent with existing
        flatten :: Tree a -> [a] which does a preorder)

Furthermore, we have a few "low level" functions implementing algorithms
for classifying edges, finding connected and biconnected components that
were contributed by Sigbjorn Finne in 1997, although GHC does not use

Finally, I think GHC's node-parametrized variant of graphs (to which
it gives the name 'Graph', as opposed to Data.Graph style graphs which
it calls 'IntGraph'; is far more useful to clients:

    data Graph node = Graph {
        gr_int_graph      :: IntGraph,
        gr_vertex_to_node :: Vertex -> node,
        gr_node_to_vertex :: node -> Maybe Vertex

and I think it is well worth considering implementing this is the standard
library.  If no one else, GHC will happily use such an implementation.


More information about the Libraries mailing list