Data.Graph (and Data.Tree) improvements
Edward Z. Yang
ezyang at mit.edu
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
graphs
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
them.
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.
Thanks,
Edward
More information about the Libraries
mailing list