Graph([('A','B'),(1,2)]).edges() raises weird traceback

[Georgi Guninski]

Graph([('A','B'),(1,2)]).edges()
<repr(<sage.graphs.views.EdgesView at 0x7fe9a43c0a00>) failed:
TypeError: unsupported operand parent(s) for <: 'Integer Ring' and
'<class 'str'>'>

I think this is related to sorting the edges.

The following works:
sage: Graph([("A",1),("B",2)]).edges()
[(1, 'A', None), (2, 'B', None)]

[Vincent Delecroix]

This is a bug in the __repr__ method of EdgesView. Thanks for your report.

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAGUWgD9zHPdu2ifxaMOc%3DEaUN5B9A_v6RmDXMLkFLCvc-Etc0w%40mail.gmail.com.

[Vincent Delecroix]

https://github.com/sagemath/sage/issues/35897

On Tue, 4 Jul 2023 at 16:25, Vincent Delecroix

[David Coudert]

There is an active deprecation warning in method edges(). Parameter sort will be set to False in the future. I'm surprised you don't see it.

sage: Graph([('A','B'),(1,2)]).edges()

<ipython-input-1-266d02e19563>:1: DeprecationWarning: parameter 'sort' will be set to False by default in the future See https://github.com/sagemath/sage/issues/27408 for details.

Graph([('A','B'),(Integer(1),Integer(2))]).edges() <repr(<sage.graphs.views.EdgesView at 0x1511698a0>) failed: TypeError: unsupported operand parent(s) for <: 'Integer Ring' and '<class 'str'>'>

[Vincent Delecroix]

To my mind, this is not the problem. The first command does generate a
warning (fine)

sage: E = Graph([('A','B'),(1,2)]).edges()
<ipython-input-1-28a7859d6cf7>:1: DeprecationWarning: parameter 'sort'

will be set to False by default in the future
See https://github.com/sagemath/sage/issues/27408 for details.

But the EdgesView.__repr__ is buggy (bad)

sage: E
<repr(<sage.graphs.views.EdgesView at 0x7fd82c935720>) failed:

TypeError: unsupported operand parent(s) for <: 'Integer Ring' and
'<class 'str'>'>

I think that either E is broken from start and an error should have
been raised in the first stage or everything is fine and we should
have a proper string representation.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/1ec8c4cf-c0d5-4682-8d10-8e74d0779dfdn%40googlegroups.com.

[David Coudert]

The current design choice in `EdgesView` is to sort only when asking for the list of edges, that is when calling `__repr__` if `sort=True`. 

The alternative is to sort at the initialization of the object and to cache the sorted list of edges in the object.

Should we go for this alternative implementation ?

[Georgi Guninski]

I am not sure I understand correctly, but if you give warning, you
already know with high probability that functionality will be broken
and besides the warning you will get exception.

Is this correct?

[Vincent Delecroix]

I do not like a solution involving a m log(m) cost at initialization.
EdgesView is supposed to be O(1) at construction right?

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/af6e1bb0-9662-4994-ba14-28ffe010e68fn%40googlegroups.com.

[Nils Bruin]

On Wednesday, 5 July 2023 at 21:54:03 UTC-7 David Coudert wrote:

The current design choice in `EdgesView` is to sort only when asking for the list of edges, that is when calling `__repr__` if `sort=True`. 

The alternative is to sort at the initialization of the object and to cache the sorted list of edges in the object.

Should we go for this alternative implementation ?

Perhaps useful in considerations: One contributing factor for the extensive usage of sort in string representations was the desire to have doctests be robust against changes in code, particularly hashes: print order of sets in Py2 was very unpredictable and driven by hash values (especially if those hash values end up being "id", i.e., basically a memory address).

There is the other one that Py2 started out with a tacit assumption that "<" was a total order on all objects, which it of course never was. It did mean that "sort" could often be applied to very diverse lists without error and with results that were relatively consistent between different runs (but not necessarily between different versions).

In Py3, iteration and print order of sets is determined by insertion order. Therefore, the string representation of objects tends to not be dependent on hash values anymore. Furthermore "<" between different types of objects will generally raise an error. Hence, "sort" has become much more problematic to be used by default and one of the motivations to use it by default in sage has become less relevant.

Hence, in my opinion, routines in sage that give access to a set of objects (like edges or vertices) should just return it in the order in which they are encountered, leading to an O(n) algorithm. If the application calls for a sorted version, the O(n*log n) penalty can be incurred by sorting the result. For doctests that need to return the actual result *AS WELL AS* be consistent for checking, wrapping in a sorted(..., key=str) would work just fine. In general it would be better to test some guaranteed invariants of the return value rather than its string representation, though.

 

[David Coudert]

@Vincent: yes, the construction of EdgesView is in O(1) and it's nice. Unfortunately, I don't know how to check that sorting may lead to an error at construction without doing it. At least the current behavior is documented.

@Nils: I fully agree with you and soon the default value of parameter sort will be False. The deprecation warning will be one year old in a month.

We have already drastically reduce the dependency to orderings, vertex label /edge types in the graph module Some remaining issues have been identified, so we have some more work to do (and some open PR to review, help is more than welcome).

Best,

David.