@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. On Thursday, July 6, 2023 at 6:01:23 PM UTC+2 Nils Bruin wrote: > 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. > > -- 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+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/bb3d9d94-a55b-4992-a7e2-452d5d9f1130n%40googlegroups.com.
