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

On 24 November 2011 20:42, Ivan Lazar Miljenovic wrote:

On 24 November 2011 20:33, Thomas DuBuisson 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.

To be more clear: we wanted superclass constraints because we had the main classes be of kind * with associated-types for the node and edge labels (which could possibly just be `()'); but to be able to do mapping over the nodes and edges we needed to be able to specify a mapping from "(g a b)" to "g a b" (where g is of kind * -> * -> *). -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com IvanMiljenovic.wordpress.com