Data.Graph

Christian Maeder Christian.Maeder at dfki.de
Fri Aug 31 09:35:58 CEST 2012


Am 30.08.2012 21:01, schrieb Evan Laforge:
> I just fixed a bug in my program that came about because the same
> graph constructed in different orders compared inequal.  E.g.:
>
> buildG (0, 2) [(0, 1), (0, 2)] /= buildG (0, 2) [(0, 2), (0, 1)]
>
> It seems to me that these should compare equal.  This was easy for me
> to do since I wrap Graph in a newtype, but it's hard to do for Graph
> itself, since it's defined as a type synonym over Data.Array.
>
> Do people agree that (==) is incorrect for Data.Graph, or is there a
> legitimate difference between the two graphs?  If people agree, what
> can be done to fix Data.Graph?  Should be add Data.Graph2 that is
> defined as a real type and start anew from there?

Is the difference caused by using a list of successors [Vertex] instead?
If so, I think, Data.Graph is correct! fgl uses a list, too.

Cheers C.

>
> In general, it seems to me Data.Graph is very basic and has not
> received any love for a long time.  It's a thin wrapper over
> Data.Array, which is one of the more error-prone ornery APIs out
> there.  To use it I wound up writing lots of little utility functions
> to do things like add or remove edges which were fiddly and error
> prone.  I just noticed a package graph-wrapper, with the description
> "A wrapper around the standard Data.Graph with a less awkward
> interface", so I guess I'm not the only person to have felt that way.
>
> Wouldn't it be nice to start taking steps toward having a graph
> library in the stdlib that people actually like?
>



More information about the Libraries mailing list