Skip to content

add the two key graph modules from Martin Erwig's FGL

Norman Ramsey requested to merge wip/fgl-modules into wip/cmm-dominators

Martin Erwig's FGL (Functional Graph Library) provides an "inductive" representation of graphs. A general graph has labeled nodes and labeled edges. The key operation on a graph is to decompose it by removing one node, together with the edges that connect the node to the rest of the graph. There is also an inverse composition operation.

The decomposition and composition operations make this representation of graphs exceptionally well suited to implement graph algorithms in which the graph is continually changing, as alluded to in #21259.

This commit adds GHC.Data.Graph.Inductive.Graph, which defines the interface, and GHC.Data.Graph.Inductive.PatriciaTree, which provides an implementation. Both modules are taken from fgl-5.7.0.3 on Hackage, with these changes:

  • Copyright and license text have been copied into the files themselves, not stored separately.

  • Some calls to error have been replaced with calls to panic.

  • Conditional-compilation support for older versions of GHC, containers, and base has been removed.

Note on dependencies: This merge request sits on top of wip/cmm-dominators, not master. That's because a forthcoming merge request depends on both.

The key part of the patch is likely the interface, GHC.Data.Graph.Inductive.Graph. Only a fraction of this interface is likely to be used inside GHC. But FGL is a popular package, and the principle of least surprise suggested not to remove any exported functions or classes from the interface.

Merge request reports