add the two key graph modules from Martin Erwig's FGL
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 topanic
. -
Conditional-compilation support for older versions of GHC,
containers
, andbase
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.