New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
GenericGraph's documentation, __eq__, and __hash__ out of sync #17086
Comments
Branch: u/emassop/graph_hash |
New commits:
|
Commit: |
comment:3
Hello ! Thank you for this 'Counter' thing, I did not know that it existed
You can have graphs with edge labels for which _weighted is not True
I do not think that this 'weighted' notion makes a lot of sense anyway, perhaps we should remove it. Either way it is probably best to set 'labels' to
Indeed, we cannot assume that sorting a list produces a unique sorted list (because the order is not always a total order) but that list, however, should be sorted. This, because even when the immutable graph is created, the vertices are labelled using the order returned by But indeed, wrapping it with a frozenset if the right thing to do.
This is REALLY bad ! Graphs with different labels should be non-equal !!! But it seems that it has been like that forever... Gosh that's bad Hmmmm.. Now I understand why you added this Nathann |
This comment has been minimized.
This comment has been minimized.
comment:4
Replying to @nathanncohen:
It's shiny new Python 2.7 material :).
Indeed you can set edge labels on unweighted graphs, but the documented behaviour is that they are ignored in
No, I do not have a counter example. I might look into it, or not. Either way, I would like to restrict this ticket to the totally ordered case where the axioms for ordering use When an In the example using
:)
In
According to the documentation the labels are ignored. Let's defer what is right(tm) to a different ticket.
:) |
comment:6
Yoooooooo !
Niiiiiiiiiice
Weird. I had no idea and expected something different. Well. Nothing wrong if it works as claimed, then
Right right. I just did not expect that and I thought it was a bug. I don't mind it if it is not.
Of course, what you do makes sense in that case.
Okay, it took me a while to understand but it seems that to you a 'is-based' ordering when comparison does not yield a total order, and is not necessarily agreeing with '=='. Why not. It has to work in this case too, anyway. Despite that, I call a list L 'sorted' when applying 'sorted' to L does not change L. Even if the ordering only makes sense to Python. And lists returned by
I would not have complained even if you had build a class for which
You were right.
Well, I do not think it needs a different ticket. I was surprised, but that's as bad as it got. If it is documented I don't see anything wrong with it. Especially since The only problem is this 'weighted' keyword. It does not have anything to do with weights, so the keyword is ill-chosen. This can be fixed in another ticket, but there is nothing really urgent to solve either. Nathann New commits:
|
comment:7
Hello again ! I see nothing wrong with your code, but I fear that I may be scared of your big doctest in a couple of years if I am still around. Could you make it more explicit, like
Thanks, Nathann |
comment:8
Replying to @nathanncohen:
I can't understand "to you ... with '=='" here. The problem can occur when an To be precise, the problem occurs when
If sorted only uses
Okay... your punctuation was a bit strange then: "This is REALLY bad ! Graphs with different labels should be non-equal !!!
Agreed. |
comment:9
Okayokay right. So it can happen even when the ordering is total, when
I expect that it only uses
Well, I did freak out. But if it works as intended, no problem Nathann |
Branch pushed to git repo; I updated commit sha1. New commits:
|
Author: Erik Massop |
Reviewer: Nathann Cohen |
comment:12
Thank you very much ! Nathann |
comment:13
At http://build.sagedev.org/trac/builders/trac_builder/builds/1112, there are these failures:
Of these
seem to be numerical noise that I can't reproduce. Moreover
are pbori segfaults, that I also get after reverting my patches for this ticket. The remaining failed doctest is
which is indeed caused by my patches here. Here is the output:
and the failing code:
The problem seems to be that Running |
Dependencies: #17092 |
comment:16
Got these on the buildbot, too. |
comment:18
(does not pass tests in |
comment:19
Replying to @nathanncohen:
With #17092 applied? |
comment:20
I do not know, I just tested it by itself. Anyway Volker does not want to see a patch in Nathann |
comment:21
Its fine to have this as positive review before the dependency is finished, assuming that tests will pass once the dependency is finished. If you have any doubts then you should sort that out, of course. |
comment:22
You set a designs ticket of mine to "needs_work" for that very reason not so long ago. |
comment:23
Which ticket? In general I think it should be avoided to have positively-reviewed tickets hang around for a long time while waiting for a dependency. But I have improved the release management scripts a few months ago to handle this case more easily. |
comment:24
Okay. |
Branch pushed to git repo; I updated commit sha1. New commits:
|
comment:26
IMHO |
comment:27
You need to add |
Branch pushed to git repo; I updated commit sha1. New commits:
|
Changed branch from u/emassop/graph_hash to public/17086 |
comment:29
I am running the doctests again just in case, but the tests pass in quivers/ when #17092 is applied. I change this ticket's branch to include a merge commit with #17092. Thanks ! Nathann New commits:
|
Changed branch from public/17086 to |
The documentation of
GenericGraph.__eq__
contains "For equality, ..., output the same vertex list (in order), ...". However, since b59285e6 (Trac Immutable graph backend #14806: Immutable graph backend), the order of the vertices is no longer checked. So either that check should be reintroduced, or the documentation should be updated.The list returned by
.vertices()
is sorted, so that checking the order only affects the result in rare cases. Hence I think updating the documentation should be okay, even while it is technically backwards incompatible.While
GenericGraph.__eq__
no longer takes the ordering of vertices into account,GenericGraph.__hash__
still does. Consequently graphs that compare equal can have different hashes.For graphs that are not weighted,
GenericGraph.__eq__
ignores the edge labels, whileGenericGraph.__hash__
does not.Item 3 is most easily shown:
For items 2 and 3, here is some contrived but deterministic code showing that the order is not checked in
.__eq__
, while it is in.__hash__
:The trick in the code above is to obtain lists [x1, y1] and [x2, y2] that compare equal but sort differently. In this case we use [C((0,0)), C((0,1))] and [C((1,0)), C((1,1))].
Such lists also occur naturally, as the code below shows. Here the inequality comparison falls back to comparison of ids, so we just generate objects until the ids are in the unlucky order.
The custom class
Foo
above is not necessary:Depends on #17092
CC: @simon-king-jena
Component: graph theory
Author: Erik Massop
Branch/Commit:
dd544a1
Reviewer: Nathann Cohen
Issue created by migration from https://trac.sagemath.org/ticket/17086
The text was updated successfully, but these errors were encountered: