Evan Laforge | 30 Aug 21:01 2012
Picon

Data.Graph

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?
Milan Straka | 30 Aug 21:45 2012
Picon

Re: Data.Graph

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
(Continue reading)

Thomas DuBuisson | 30 Aug 22:23 2012
Picon

Re: Data.Graph

> 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 <at> haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
Nils Anders Danielsson | 31 Aug 13:57 2012
Picon
Picon

Re: Data.Graph

On 2012-08-30 21:45, Milan Straka wrote:
> 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.

Agda uses Data.Graph to compute strongly connected components.

--

-- 
/NAD
Mikhail Glushenkov | 3 Sep 11:11 2012
Picon

Re: Data.Graph

Milan Straka <fox <at> ucw.cz> 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.
Edward Kmett | 3 Sep 11:50 2012
Picon

Re: Data.Graph

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 <at> gmail.com> wrote:
Milan Straka <fox <at> ucw.cz> 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 <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Christian Maeder | 31 Aug 09:35 2012
Picon

Re: Data.Graph

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?
>

Gmane