On 24 November 2011 20:33, Thomas DuBuisson <[email protected]> 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 [email protected] IvanMiljenovic.wordpress.com _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
