[Haskell-cafe] FGL custom node identification (Label -> Node lookup)

[Ivan Lazar Miljenovic]

On 24 November 2011 20:33, Thomas DuBuisson <thomas.dubuisson at gmail.com> wrote:
> All,
>
> 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
>
>
> Cheers,
> Thomas
>
> 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
IvanMiljenovic.wordpress.com