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? 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?
Hi Evan,
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?
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?
As far as I know, Data.Graph has not been given any attention in quite some time. I do not know whether someone is using it. As one of the maintainers of containers, I can say that no-one is working on it and you are even the first who had any comments about Data.Graph in quite some time. There is widely used library fgl, which is even in Haskell Platform, and that definitely is being used. Maybe we should separate Data.Graph (and probably Data.Tree) into a separate package? Any thoughts? Cheers, Milan
As far as I know, Data.Graph has not been given any attention in quite some time. I do not know whether someone is using it.
Yes, Data.Graph is in use in at least one serious compiler/research project.
Maybe we should separate Data.Graph (and probably Data.Tree) into a separate package? Any thoughts?
I don't see a reason to separate out Data.Graph unless being in containers somehow a) significantly increases the lag time from patch to new release, or b) frequently causes major version bumps to 'containers' that causes headaches non-Data.Graph users.
Cheers, Milan
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
I used to Data.Graph in 'ad', before we hand-rolled an topSort for our particular acyclic case in response to it running out of stack space on large graphs. w.r.t. the original question, I think the behavior of Graph equality is correct given the model used. There are observable differences between the two graphs, even though the strict traditional notion of a graph doesn't distinguish on the ordering of the successors of a field, the structure used by Graph does and cannot sensibly be made not to without sacrificing performance needlessly for the vast majority of users. There are other observable differences, e.g. changing array bounds that can affect equality as well. -Edward On Mon, Sep 3, 2012 at 5:11 AM, Mikhail Glushenkov < the.dead.shall.rise@gmail.com> wrote:
Milan Straka
writes: As far as I know, Data.Graph has not been given any attention in quite some time. I do not know whether someone is using it.
Cabal uses Data.Graph to represent the package dependency graph.
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
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?
participants (7)
-
Christian Maeder -
Edward Kmett -
Evan Laforge -
Mikhail Glushenkov -
Milan Straka -
Nils Anders Danielsson -
Thomas DuBuisson