[Haskell-cafe] FGL custom node identification (Label -> Node lookup)
Ivan Lazar Miljenovic
ivan.miljenovic at gmail.com
Thu Nov 24 10:42:33 CET 2011
On 24 November 2011 20:33, Thomas DuBuisson <thomas.dubuisson at gmail.com> wrote:
> The containers library has a somewhat primitive but certainly useful
> Data.Graph library. Building a graph with this library simultaneously
> results in the lookup functions:
> m1 :: Vertex -> (node, key, [key])
> m2 :: key -> Maybe Vertex
> (where 'key' is like FGL's 'label' but is assumed to be unique)
> This is exactly what I wanted when building and analyzing a call graph
> in FGL. To that end, I started making a graph type that tracked label
> to Node mappings, wrapping Data.Graph.Inductive.Gr, and assuming the
> labels are all unique.
> The classes for such a graph actually aren't possible. The ability to
> build a mapping from a node's 'label' to the 'Node' requires extra
> context (ex: Hashable, Ord, or at least Eq), but such context can not
> be provided due to the typeclass construction.
> Is there any chance we can change the Graph and DiaGraph classes to
> expose the type variables 'a' and 'b'?
> class Graph gr a b where ...
> class (Graph gr) => DynGraph gr a b where ...
> This would allow instances to provide the needed context:
> instance (Hashable a, Hashable b) => Graph UniqueLabel a b where
> buildGraph = ... some use of containers libraries that
> require context ...
> lookupNode :: Hashable a => UniqueLabel a b -> a -> Node
> -- etc
> P.S. Please do educate me if I simply missed or misunderstood some
> feature of FGL.
Well, there *is* the NodeMap module, but I haven't really used it so
I'm not sure if it does what you want.
We did start upon a version of FGL which had these type variables in
the class, but it got a little fiddly; the ability to have superclass
constraints should solve this but I haven't touched FGL for a while,
as I've been working on some other graph library code for planar
graphs, with the plan to take my experience from writing this library
into a "successor" to FGL.
However, my experience with designing this planar graph library has
led me to using abstract (i.e. non-exported constructor) ID types for
nodes and edges and finding them rather useful, but then I'm more
concerned about the _structure_ of the graph rather than the items
stored within it. As such, I'd appreciate you explaining to me
(off-list is OK) why you want/need such a label -> node mapping so
that I can try and work out a way to incorporate such functionality.
Ivan Lazar Miljenovic
Ivan.Miljenovic at gmail.com
More information about the Haskell-Cafe