Opened 4 years ago

Closed 4 years ago

#25864 closed enhancement (fixed)

make LinearExtensions an iterator

Reported by: mantepse Owned by:
Priority: major Milestone: sage-8.6
Component: combinatorics Keywords: sagedays@icerm
Cc: tscrim, chapoton, jmantysalo, kdilks, aschilling Merged in:
Authors: Martin Rubey Reviewers: Travis Scrimshaw, Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: c62cd56 (Commits, GitHub, GitLab) Commit: c62cd56d523b93380171659b4a788ecbabc6b8fa
Dependencies: Stopgaps:

Status badges

Description (last modified by mantepse)

Currently, it is returning a (sorted) list. However, this is not good when trying to iterate through the linear extensions of slightly larger posets.

Change History (83)

comment:1 Changed 4 years ago by mantepse

  • Branch set to u/mantepse/make_linearextensions_an_iterator

comment:2 Changed 4 years ago by mantepse

  • Authors set to Martin Rubey
  • Cc tscrim added
  • Commit set to 8050b00052c5aca2d2e8b3b2dd2311d30cb56d53
  • Component changed from PLEASE CHANGE to combinatorics
  • Description modified (diff)
  • Type changed from PLEASE CHANGE to enhancement

New commits:

8050b00create graphs.LinearExtensions.__iter__, adapt a few methods and doctests

comment:3 Changed 4 years ago by git

  • Commit changed from 8050b00052c5aca2d2e8b3b2dd2311d30cb56d53 to f1705d88f7688dac8e84a102e1c2c1fa547f7852

Branch pushed to git repo; I updated commit sha1. New commits:

f1705d8fix mistake in initialisation of LinearExtensions and adapt doctests

comment:4 Changed 4 years ago by git

  • Commit changed from f1705d88f7688dac8e84a102e1c2c1fa547f7852 to c49f132080731f444d8cfb707301c89ebe89b8ba

Branch pushed to git repo; I updated commit sha1. New commits:

c49f132fix doctests and topological_sort_generator

comment:5 Changed 4 years ago by mantepse

  • Status changed from new to needs_review

comment:6 Changed 4 years ago by git

  • Commit changed from c49f132080731f444d8cfb707301c89ebe89b8ba to 6c7d6ec8ce55df936e8d836c930b59f2ad6eb6c2

Branch pushed to git repo; I updated commit sha1. New commits:

6c7d6ecfix another doctest

comment:7 Changed 4 years ago by git

  • Commit changed from 6c7d6ec8ce55df936e8d836c930b59f2ad6eb6c2 to d1ce5e8e3fbb8e97dcccd1b770fadc55075ddf65

Branch pushed to git repo; I updated commit sha1. New commits:

d1ce5e8fix more doctests

comment:8 Changed 4 years ago by git

  • Commit changed from d1ce5e8e3fbb8e97dcccd1b770fadc55075ddf65 to 450ac8c1763a7bc6ef2b3a55c82da9c82363f1f5

Branch pushed to git repo; I updated commit sha1. New commits:

450ac8cfix coverage and pyflakes, slightly simplify logic

comment:9 Changed 4 years ago by mantepse

  • Cc jmantysalo added

comment:10 follow-up: Changed 4 years ago by jmantysalo

I do not understand. "Currently, it is returning a (sorted) list.", but already

_ = posets.BooleanLattice(4).linear_extensions()

takes about zero time, whereas

_ = list(posets.BooleanLattice(4).linear_extensions())

takes at least a minute, and for example

_ = posets.BooleanLattice(4).linear_extensions()[2000]

takes a fraction of a second. So, this seems to already be an iterator.

comment:11 in reply to: ↑ 10 ; follow-up: Changed 4 years ago by mantepse

Currently, P.linear_extensions() returns a class, with some (rather little) initialisations done. This class has a __list__ method, which triggers the actual computation.

In particular:

Replying to jmantysalo:

I do not understand. "Currently, it is returning a (sorted) list.", but already

_ = posets.BooleanLattice(4).linear_extensions()

takes about zero time, whereas

because only the initialisation code is run,

_ = list(posets.BooleanLattice(4).linear_extensions())

takes at least a minute, and for example

because the list of all linear extensions is created, and

_ = posets.BooleanLattice(4).linear_extensions()[2000]

takes a fraction of a second.

because this is only accessing an element in a list.

comment:12 in reply to: ↑ 11 ; follow-up: Changed 4 years ago by jmantysalo

Replying to mantepse:

Currently, P.linear_extensions() returns a class, with some (rather little) initialisations done. This class has a __list__ method, which triggers the actual computation.

??? No, it has __iter__ that is an iterator.

comment:13 in reply to: ↑ 12 Changed 4 years ago by mantepse

Replying to jmantysalo:

Replying to mantepse:

Currently, P.linear_extensions() returns a class, with some (rather little) initialisations done. This class has a __list__ method, which triggers the actual computation.

??? No, it has __iter__ that is an iterator.

which calls self._linear_extensions_of_hasse_diagram which is sage.graphs.linearextensions.LinearExtensions(poset._hasse_diagram) which had only a list method before this ticket...

comment:14 follow-up: Changed 4 years ago by jmantysalo

But clearly there is some kind of "iterator" used here, as we can ask for example tenth linear extension without generating the whole list. In a quick look it seems that generate_linear_extensions gives kind of "implicit iterator", as it computes "next" linear extension in some order of extensions.

But is it so that current implementation eats memory, i.e. already "used" extensions are not released from the memory? If so, then I understand this.

comment:15 in reply to: ↑ 14 Changed 4 years ago by mantepse

Replying to jmantysalo:

But clearly there is some kind of "iterator" used here, as we can ask for example tenth linear extension without generating the whole list.

No, the problem is precisely that the whole list is always generated. This is slightly obscured by the fact that posets are UniqueRepresentation. But to see it, you can insert a line

  • src/sage/graphs/linearextensions.py

    diff --git a/src/sage/graphs/linearextensions.py b/src/sage/graphs/linearextensions.py
    index 113a2cd..f899dfc 100644
    a b class LinearExtensions(CombinatorialClass): 
    347347             [0, 2, 1, 4, 3],
    348348             [0, 2, 4, 1, 3]]
    349349        """
     350        print("computing")
    350351        if self.linear_extensions is not None:
    351352            return self.linear_extensions[:]

rebuild sage, and then verify the following:

sage: P = posets.AntichainPoset(9); L = P.linear_extensions()._linear_extensions_of_hasse_diagram
sage: type(L.linear_extensions)
<type 'NoneType'>
sage: L[0]
computing
[0, 1, 2, 3, 4, 5, 6, 7, 8]
sage: type(L.linear_extensions)
<type 'list'>
sage: L.linear_extensions[0]
[0, 1, 2, 3, 4, 5, 6, 7, 8]
sage: L.linear_extensions[-1]
[8, 7, 6, 5, 4, 3, 2, 1, 0]

As you can see, the list of linear extensions is computed although only the first element is requested.

comment:16 follow-up: Changed 4 years ago by jmantysalo

  • Cc chapoton added

This is very interesting. Maybe Travis or Frédéric can tell what happens here... I start Sage and say

sage: for x in posets.AntichainPoset(10).linear_extensions():
....:     print x
....:     break

No output, system seems to be stalled. I press Ctrl+C and get back to command line. I give the same command again, and now I got

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

So, it seems that this kind of is an iterator, but not exactly.

comment:17 in reply to: ↑ 16 Changed 4 years ago by mantepse

Replying to jmantysalo:

This is very interesting. Maybe Travis or Frédéric can tell what happens here... I start Sage and say

sage: for x in posets.AntichainPoset(10).linear_extensions():
....:     print x
....:     break

No output, system seems to be stalled. I press Ctrl+C and get back to command line. I give the same command again, and now I got

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

So, it seems that this kind of is an iterator, but not exactly.

You are simply interrupting the computation in posets.AntichainPoset(10).linear_extensions()._linear_extensions_of_hasse_diagram.list().

You can see this as follows: in a fresh session (!!!) do the same as before, that is, interrupt

sage: P = posets.AntichainPoset(10)
sage: for x in P.linear_extensions():
....:     print x
....:     break

then again

sage: for x in P.linear_extensions():
....:     print x
....:     break

which will yield

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

Then check that

sage: P.linear_extensions().cardinality()
3628800

Finally:

sage: len(P.linear_extensions()._linear_extensions_of_hasse_diagram.linear_extensions)

which will tell you a smaller number. And indeed

sage: P.linear_extensions()[3628800-1]

will give an error (after a while, because lists are copied all the time).

comment:18 Changed 4 years ago by kdilks

  • Cc kdilks added

comment:19 Changed 4 years ago by kdilks

In the process of reading the code in graphs/linearextensions.py, and trying to figure out how it needs to be modified to become an iterator. I may need to read a bit more of the paper to understand what the individual helper methods are doing and how they tie together. I'm hoping it will eventually be as easy as changing the end of the move() and switch() methods to be yield statements, and make the list() method an _iter_() method.

One potential problem that could arise by changing things is if any other code relies on linear extensions of a poset being generated in lexicographic order. The algorithm itself does not generate them in lexicographic order, but the current implementation makes it appear that way to the user since the entire list is generated and then sorted before being iterated over.

comment:20 Changed 4 years ago by mantepse

@kdilks: I modified the code already so that it is a true iterator!

It only needs review, there is no coding to be done!

comment:21 Changed 4 years ago by kdilks

Much easier!

Still building Sage to run some tests. Only extremely minor thing I see from looking at the diff is that the docstring for the _iter_ method still says 'Returns a list of ...' from when it was the list method.

comment:22 Changed 4 years ago by git

  • Commit changed from 450ac8c1763a7bc6ef2b3a55c82da9c82363f1f5 to e70ba7c721a0a9ffcdb3db51edb56dff652ddad0

Branch pushed to git repo; I updated commit sha1. New commits:

e70ba7cfix docstring

comment:23 Changed 4 years ago by tscrim

Some things:

  • It is better practice to copy the dag on input rather than at _prepare as it is possible to pass the dag in, modify the dag, and then run _prepare. It also means that it will never have an inconsistent state by having linear extensions for a dag that is not its self.dag.
  • Errors are not full sentences by Python conventions:
    -ValueError("The digraph must be acyclic to have linear extensions.")
    +ValueError("the digraph must be acyclic to have linear extensions")
    
  • The result is no longer cached. So if this is called repeatedly for the same dag, this could be slower. I think your change is okay, but it might have unintended consequences in terms of speed. Did you check this?

comment:24 Changed 4 years ago by mantepse

The first item is a bit more work, because I will have to copy the graph twice or prepare a matrix of incomparable elements. Not sure yet what's better.

comment:25 Changed 4 years ago by git

  • Commit changed from e70ba7c721a0a9ffcdb3db51edb56dff652ddad0 to 80a5766d6d2c288d003ab520b45ddcd147ff8fad

Branch pushed to git repo; I updated commit sha1. New commits:

80a5766remove CombinatorialClass, prepend underscores to internal methods and variables, etc.

comment:26 Changed 4 years ago by mantepse

I now get

            sage: l == loads(dumps(l))
            False

no idea why (I don't even know what this does...)

comment:27 Changed 4 years ago by kdilks

Google is telling me that this error can occur when you have a dictionary with non-string keys (dumps converts a dictionary to a json file which only has string keys, and then loads recreates the dictionary). How/why that's coming up...I've got nothing.

comment:28 Changed 4 years ago by chapoton

The loads/dumps problem is a "pickling issue" : dumps somehow saves a compressed copy of the object (pickle) and loads restores back something from that. This kind of error is usually triggered by wrong behaviour of the comparison methods __eq__ or __richcmp__. You should try to understand why l and loads(dumps(l)) do not compare equal, and who is in charge of the comparison.

comment:29 Changed 4 years ago by mantepse

It appears to me now that this class actually shouldn't be a parent, because that's what LinearExtensionsOfPoset does, except that the latter is specialised to posets, not arbitrary DAGs.

Apart from there, this class is only used once in library code, in Permutation.

Alternatively, blow it up similarly to LinearExtensionsOfPoset, but I'm a bit afraid that this is really only bloat.

comment:30 Changed 4 years ago by tscrim

  • Keywords sagedays@icerm added
  • Reviewers set to Travis Scrimshaw

I at least agree that it probably should not be a non-façade Parent as its "elements" are lists. In fact, this is probably something we should consider cythonizing since this is also used by DiGraph.topological_sort_generator (which sounds like it should return an iterator, not a list, but that is a separate issue). Granted, since this is more of an internal class, you are probably right in that it should not be a subclass of Parent, but it might mean a finer check.

comment:31 Changed 4 years ago by mantepse

Could you say (or give me a reference to) what a non-facade parent is? Or, maybe easier, what LinearExtensions should inherit from.

(I have already adapted the code from LinearExtensionsOfPoset, making it a real parent with a new element class LinearExtension - its easy to do, I just don't know whether it is what should be done.)

comment:32 Changed 4 years ago by tscrim

A façade parent is a parent that does not have elements but functionally behaves like a parent. IIRC, see the doc of Parent. As I said in comment:30, it probably should not inherit from Parent, and so probably should be a subclass of object. However, there might be some things from the category that do get utilized (such as in the top sort method).

comment:33 Changed 4 years ago by mantepse

I decided to give it a try and cythonized the iterator. I currently have a speedup of a factor 2. I am still polishing.

comment:34 Changed 4 years ago by git

  • Commit changed from 80a5766d6d2c288d003ab520b45ddcd147ff8fad to cf582a35ca96b80cbf977b3cea10cc8eeb25d53a

Branch pushed to git repo; I updated commit sha1. New commits:

015a14eMerge branch 'develop' of git://trac.sagemath.org/sage into t/25864/make_linearextensions_an_iterator
88fdef6Merge branch 'develop' of git://trac.sagemath.org/sage into t/25864/make_linearextensions_an_iterator
cf582a3cythonize iterator

comment:35 Changed 4 years ago by mantepse

new:

sage: from sage.combinat.combinat_cython import linear_extension_iterator
sage: D = posets.BooleanLattice(4)
sage: %time for e in linear_extension_iterator(D._hasse_diagram): pass
CPU times: user 23.5 s, sys: 47.7 ms, total: 23.5 s
Wall time: 23.5 s
sage: from sage.graphs.linearextensions import LinearExtensions
sage: %time for e in LinearExtensions(D): pass
CPU times: user 25.1 s, sys: 0 ns, total: 25.1 s
Wall time: 25 s

old:

sage: D = posets.BooleanLattice(4)
sage: from sage.graphs.linearextensions import LinearExtensions
sage: %time for e in LinearExtensions(D.hasse_diagram()): pass
CPU times: user 2min 49s, sys: 692 ms, total: 2min 49s
Wall time: 2min 51s

comment:36 Changed 4 years ago by mantepse

  • Status changed from needs_review to needs_work

comment:37 Changed 4 years ago by git

  • Commit changed from cf582a35ca96b80cbf977b3cea10cc8eeb25d53a to 4de624fb8b3f183563bb161468c1985f823a0e09

Branch pushed to git repo; I updated commit sha1. New commits:

4de624fpartially fix relabelling issue

comment:38 Changed 4 years ago by git

  • Commit changed from 4de624fb8b3f183563bb161468c1985f823a0e09 to 04459fa5110226c2d8bdc3615478ce5e86ebc86b

Branch pushed to git repo; I updated commit sha1. New commits:

04459fasimplify logic and fix issue with ordering

comment:39 Changed 4 years ago by git

  • Commit changed from 04459fa5110226c2d8bdc3615478ce5e86ebc86b to 79e9579343f712a4d63b4f4e48fb3df1dd18a770

Branch pushed to git repo; I updated commit sha1. New commits:

79e9579Merge branch 'develop' of git://trac.sagemath.org/sage into t/25864/make_linearextensions_an_iterator

comment:40 Changed 4 years ago by mantepse

  • Status changed from needs_work to needs_info

comment:41 follow-up: Changed 4 years ago by mantepse

I don't know what to do with

            sage: from sage.graphs.linearextensions import LinearExtensions
            sage: D = DiGraph({ 0:[1,2], 1:[3], 2:[3,4] })
            sage: l = LinearExtensions(D)
            sage: l == loads(dumps(l))
            True

(because this now gives False)

Also, maybe it would be better to deprecate the class LinearExtensions completely, the class LinearExtensionsOfPoset should be a good replacement (and might be renamed LinearExtensions).

comment:42 Changed 4 years ago by git

  • Commit changed from 79e9579343f712a4d63b4f4e48fb3df1dd18a770 to f9a7227fdb5ba3e6e3b6a161421edb3d4911f686

Branch pushed to git repo; I updated commit sha1. New commits:

f9a7227fix pyflakes import statements

comment:43 Changed 4 years ago by mantepse

  • Cc aschilling added

Anne, I'm guessing that this might affect (positively, I hope) a lot of your code...

comment:44 in reply to: ↑ 41 Changed 4 years ago by tscrim

Replying to mantepse:

I don't know what to do with

            sage: from sage.graphs.linearextensions import LinearExtensions
            sage: D = DiGraph({ 0:[1,2], 1:[3], 2:[3,4] })
            sage: l = LinearExtensions(D)
            sage: l == loads(dumps(l))
            True

(because this now gives False)

Because Parent does not have an __eq__ method (so it defaults to compare by id, which is obviously false).

Also, maybe it would be better to deprecate the class LinearExtensions completely, the class LinearExtensionsOfPoset should be a good replacement (and might be renamed LinearExtensions).

LinearExtensions was serving as an iterator object that yielded low level objects. Now this is done by your cython iterator. So +1 for deprecating it, -1 from saying LinearExtensionsOfPoset is a replacement.

Also, I have a general -1 on all of those sorted. They should not be necessary, and within code, they can be (relatively) expensive when not needed.

comment:45 Changed 4 years ago by git

  • Commit changed from f9a7227fdb5ba3e6e3b6a161421edb3d4911f686 to 84aad72318baa661734246ba47d6e3889adb3eb7

Branch pushed to git repo; I updated commit sha1. New commits:

84aad72deprecate LinearExtensions

comment:46 follow-up: Changed 4 years ago by mantepse

Travis, I need some help with the deprecation message and the sorted issue.

  • I think the deprecation is mainly (but not exclusively) to direct the user to alternatives. Thus I'd say it's DiGraph.topological_sort_generator and LinearExtensionsOfPoset. You wrote that you disagree with LinearExtensionsOfPoset, could you please expand why?
  • LinearExtensions sorted it's result, and I think it's fine to leave it that way in the deprecated class. However, in LinearExtensionsOfPoset I certainly do not want to sort. Should I remove the sorting from the doctests too?
  • topological_sort_generator returns a sorted list. Should I create a new method topological_sort_iterator, which is an iterator, and deprecate the old method, or should I silently modify the old method?
  • I would actually like to advertise LinearExtensionsOfPoset as main entry point, and I think this should also be a method of Poset. What do you think?

comment:47 in reply to: ↑ 46 Changed 4 years ago by tscrim

Replying to mantepse:

  • I think the deprecation is mainly (but not exclusively) to direct the user to alternatives. Thus I'd say it's DiGraph.topological_sort_generator and LinearExtensionsOfPoset. You wrote that you disagree with LinearExtensionsOfPoset, could you please expand why?

As per comment:44, LinearExtensionsOfPoset does not return a low-level object (in this case, a list). It is not equivalent or an alternative as a DAG is not a poset.

  • LinearExtensions sorted it's result, and I think it's fine to leave it that way in the deprecated class. However, in LinearExtensionsOfPoset I certainly do not want to sort. Should I remove the sorting from the doctests too?

Yes. It is not machine dependent, right? There is no point in adding useless things (e.g. sorting) to doctests or code.

  • topological_sort_generator returns a sorted list. Should I create a new method topological_sort_iterator, which is an iterator, and deprecate the old method, or should I silently modify the old method?

That it was sorting things is an implementation detail. There is nothing in the documentation about guaranteeing that the linear extensions returned are in a particular order.

  • I would actually like to advertise LinearExtensionsOfPoset as main entry point, and I think this should also be a method of Poset. What do you think?

Strong -1 on having LinearExtensionsOfPoset as a global entry point and suggesting it in any documentation. You should always go through Poset(foo).linear_extensions(). This is natural and helps keeps the global namespace clean.

comment:48 Changed 4 years ago by mantepse

Oh, I didn't realize that Poset has a method returning LinearExtensionsOfPoset...

comment:49 Changed 4 years ago by mantepse

I am now removing the sorted from the doctests, but I must say that I think this is wrong, for the following reasons:

  • it saves no time (because sorting a list of 4 elements is not very costly)
  • it makes the doctests less expressive: adding the sorted also tells the user not to rely on the order
  • it creates a lot of work and larger diffs.

I am totally with you to remove the sorted from the methods, however.

comment:50 Changed 4 years ago by git

  • Commit changed from 84aad72318baa661734246ba47d6e3889adb3eb7 to d8795fb2cb3aa8897196bdba51e294b6a2ee52c5

Branch pushed to git repo; I updated commit sha1. New commits:

d8795fbdo not sort in methods

comment:51 Changed 4 years ago by mantepse

I won't be able to unsort soon, sorry.

comment:52 Changed 4 years ago by git

  • Commit changed from d8795fb2cb3aa8897196bdba51e294b6a2ee52c5 to dcb8fe3cd7dc554892cdcc7773911768383adb80

Branch pushed to git repo; I updated commit sha1. New commits:

dcb8fe3Merge branch 'develop' of git://trac.sagemath.org/sage into t/25864/make_linearextensions_an_iterator

comment:53 Changed 4 years ago by git

  • Commit changed from dcb8fe3cd7dc554892cdcc7773911768383adb80 to 8512ff7459cb49d95a69175490fb90e0e2159fd8

Branch pushed to git repo; I updated commit sha1. New commits:

8512ff7Merge branch 'develop' of git://trac.sagemath.org/sage into t/25864/make_linearextensions_an_iterator

comment:54 Changed 4 years ago by git

  • Commit changed from 8512ff7459cb49d95a69175490fb90e0e2159fd8 to 9ec826f79a54f826f44d7b35f92786f5e58667ca

Branch pushed to git repo; I updated commit sha1. New commits:

9ec826ffix doctests

comment:55 Changed 4 years ago by mantepse

I am now going to remove the sorting from the doctests.

comment:56 Changed 4 years ago by git

  • Commit changed from 9ec826f79a54f826f44d7b35f92786f5e58667ca to 4ec19005cec766c9d2cc4e198dd163002561a19c

Branch pushed to git repo; I updated commit sha1. New commits:

4ec1900remove sorting in doctests by reviewer's request

comment:57 follow-up: Changed 4 years ago by chapoton

Please check that this "unsorting" also works with python3. Yes, I know that this is a burden..

comment:58 Changed 4 years ago by mantepse

  • Status changed from needs_info to needs_review

The calls to sorted are now also removed in doctests. Please review!

comment:59 in reply to: ↑ 57 Changed 4 years ago by mantepse

Replying to chapoton:

Please check that this "unsorting" also works with python3. Yes, I know that this is a burden..

It was not my idea not to sort, and I explained well why I think that sorting shoult be done, to no avail. I just spent more than an hour to remove all the sorts, and I have no idea how to do this with python3.

Excuse me, it's absolutely not your fault, but if this was wasted time, I'm really pissed off.

comment:60 follow-up: Changed 4 years ago by chapoton

I am sorry, because I could in fact have told you a bit earlier. I did not want to interfere, but then I feeled obliged to do so.

The point is: are we sure that the order in which the linear extensions are produced is deterministic ?

You need to check that the doctests that you take great care to modify will not break on a python3-build sage. I have no available time to do that for you. This means building another copy of sage, and running the doctests..

comment:61 Changed 4 years ago by chapoton

I am right now trying your branch on a python3-sage..

comment:62 Changed 4 years ago by chapoton

ok, this seems to work smoothly on python3. So let the review process go on.

comment:63 Changed 4 years ago by mantepse

OK, now building with python3.

comment:64 in reply to: ↑ 60 Changed 4 years ago by mantepse

Replying to chapoton:

I am sorry, because I could in fact have told you a bit earlier. I did not want to interfere, but then I feeled obliged to do so.

No problem, I very much value your work, and I overreacted, because I did not and do not see any sense in removing the sorting, as I explained above. (In fact, putting in the sorting also took some time.)

I hope that this can be merged soon, so #25865 can be merged, too.

comment:65 Changed 4 years ago by tscrim

Thank you for removing the unnecessary sorting.

The patchbot is getting one failure:

File "src/sage/combinat/posets/poset_examples.py", line 1400, in sage.combinat.posets.poset_examples.Posets.YoungDiagramPoset
Failed example:
    P.cover_relations()
Expected:
    [[(0, 0), (1, 0)], [(0, 0), (0, 1)], [(1, 0), (1, 1)],
     [(0, 1), (1, 1)]]
Got:
    [[(0, 0), (0, 1)], [(0, 0), (1, 0)], [(0, 1), (1, 1)], [(1, 0), (1, 1)]]

Also, before you whine about this, this was not affected by the sorting changes.

comment:66 Changed 4 years ago by mantepse

This is. #26586

comment:67 Changed 4 years ago by tscrim

  • Milestone changed from sage-8.4 to sage-8.5
  • Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Frédéric Chapoton
  • Status changed from needs_review to positive_review

Okay, then positive review.

comment:68 Changed 4 years ago by mantepse

Thank you!

comment:69 Changed 4 years ago by vbraun

  • Dependencies set to 26586
  • Status changed from positive_review to needs_work

comment:70 Changed 4 years ago by vbraun

  • Dependencies changed from 26586 to #26586
  • Status changed from needs_work to positive_review

comment:71 Changed 4 years ago by tscrim

  • Dependencies #26586 deleted

#26586 is not a dependency of this ticket as that problem already exists and is independent of this ticket.

comment:72 Changed 4 years ago by tscrim

I wasn't aware of the #26586 issue before this. Or does this ticket make #26586 now appear without running the doctests with --gc=never?

comment:73 Changed 4 years ago by mantepse

No, it is not really a dependency. What happens is that I was not using --long on my laptop, but the patchbot is.

The problem exists with and without this branch, but this branch modifies the output.

comment:74 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work

For whatever reason this ticket excascerbates the problem; I'm not going to merge it if it makes half of the buildbots fail.

comment:75 Changed 4 years ago by git

  • Commit changed from 4ec19005cec766c9d2cc4e198dd163002561a19c to cca16168918bf62dc04e2b84c5dca69d6517c68b

Branch pushed to git repo; I updated commit sha1. New commits:

cca1616Merge branch 'develop' of git://trac.sagemath.org/sage into t/25864/make_linearextensions_an_iterator

comment:76 Changed 4 years ago by mantepse

  • Status changed from needs_work to needs_review

comment:77 Changed 4 years ago by tscrim

  • Status changed from needs_review to positive_review

comment:78 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work

Merge conflict

comment:79 Changed 4 years ago by git

  • Commit changed from cca16168918bf62dc04e2b84c5dca69d6517c68b to c62cd56d523b93380171659b4a788ecbabc6b8fa

Branch pushed to git repo; I updated commit sha1. New commits:

79c034eMerge branch 'develop' of git://trac.sagemath.org/sage into t/25864/make_linearextensions_an_iterator
c62cd56remove "# known bug" because it now works as expected

comment:80 Changed 4 years ago by mantepse

Essentially trivial merge.

comment:81 Changed 4 years ago by mantepse

  • Status changed from needs_work to needs_review

comment:82 Changed 4 years ago by tscrim

  • Milestone changed from sage-8.5 to sage-8.6
  • Status changed from needs_review to positive_review

comment:83 Changed 4 years ago by vbraun

  • Branch changed from u/mantepse/make_linearextensions_an_iterator to c62cd56d523b93380171659b4a788ecbabc6b8fa
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.