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

Thomas DuBuisson thomas.dubuisson at gmail.com
Thu Nov 24 19:13:20 CET 2011


My thinking on this was that something akin to NodeMap should be
_part_ of the graph structure.  This would be more convenient and
allow the graph and nodemap operations to apply to a single data
structure.

Instead of:

    insMapNode_ :: (Ord a, DynGraph g) => NodeMap a -> a -> g a b -> g a b

You could have:

    insMapNode_ :: (Ord a, DynGraph g) => a -> g a b -> g a b

The only think stopping us from making a product data type like this
is the inflexibility of the type classes, right?  Were we able to
define (&) to update the nodemap too then we could keep these to
structures in sync automatically instead of expecting the programmer
to keep them paired correctly.

Cheers,
Thomas

On Thu, Nov 24, 2011 at 1:42 AM, Ivan Lazar Miljenovic
<ivan.miljenovic at gmail.com> wrote:
> 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
>



More information about the Haskell-Cafe mailing list