Add is_supergreedy() to linear extension

[jm58660]

Add a function to check if a linear extension of a poset is supergreedy. (Compare to #24632.)

Component: combinatorics

Author: Rohan Garg

Reviewer: Jori Mäntysalo

Issue created by migration from https://trac.sagemath.org/ticket/24700

[Sandstorm831]

New commits:

86fc48d

added is_supergreedy() function

[Sandstorm831]

Branch: u/gh-Sandstorm831/24700

[Sandstorm831]

Commit: 86fc48d

[Sandstorm831]

comment:3

I have added the is_supergreedy() function in the linear_extensions.py file, and would be glad for any reviews

[jm58660]

comment:4

This could should have crosslinks is_greedy() <-> is_supergreedy().

Currently documentation for is_greedy has a paragraph "Informally said...". I suggest adding similar to this, like

Informally said a linear extension is supergreedy if it “always goes up when possible and returns down as less as possible”.

[jm58660]

comment:5

Maybe I don't understand this. Example in the code lists all linear extensions of the Pentagon poset. But at least some linear extension must be supergreedy. I think the smallest example of greedy but no supergreedy extension can be found in the 4-element poset "a V letter and a lone element".

But it has been a while from the time I look about posets.

[sagetrac-git]

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

cef5e45

implemented diff algo, for borderline cases

[sagetrac-git]

Changed commit from 86fc48d to cef5e45

[Sandstorm831]

comment:7

I have changed the algorithm, last algorithm was missing some borderline cases, which is now fixed. I had tried to find, but only informal definition I could get is set of supergreedy linear extension is exactly same as that of depth first search set. In pentagon poset, although there are 2 sequences are possible which are supergreedy but those sequences are not linear extensions, so that doesn't appear when is_supergreedy() is called. I don't know about the minimum element poset where is_greedy but not supergreedy case appear, but during testing, there are indeed cases when linear extension is supergreedy and not greedy. Also resources of supergreedy is very much limited, I can find only one paper where I can got the definition, after that 2-3 papers just copied the same definition from the original one, so lack of materials also made things tricky, you can find the original paper https://trotter.math.gatech.edu/papers/66.pdf .please let me know, if there changes to do.

[jm58660]

comment:9

I think one can write an informal description without reference to an article.

The codes seems to get stuck with

for le in Poset({1: [2, 3], 4: []}).linear_extensions(): print (le, le.is_supergreedy())

Please check with something like for P in Posets(): print(len([le for le in P.linear_extension() if le.is_supergreedy()]) or similar.

[sagetrac-git]

Changed commit from cef5e45 to 200441d

[sagetrac-git]

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

200441d

correcting function for disjoint set of points

[Sandstorm831]

comment:11

Thanks for the pointing out the error, My algorithm didn't account for disjointed points altogether, so have to change somethings, and also had to define a helper function named complete_supergreedy() for the original function. Please review and let me know if there is any other changes. As far as I know for some informal definition, then I can't say anything concretely as greedy is different from supergreedy so I am also not sure, And apologies for the delay as the this function is somewhat tricky to implement, so it took some time of me.

[jm58660]

comment:12

Now it does not stuck, but says that every linear extension of Poset({1: [2, 3], 4: []}) is supergreedy, even those that are not greedy. Try

sage: P = Poset({1: [2, 3], 4: []})
sage: for le in P.linear_extensions(): print (le, le.is_greedy(), le.is_supergreedy())

[mantepse]

comment:13

once you are done it would be great if you could compare with the data (not the code!) recorded at http://www.findstat.org/StatisticsDatabase/St001106/

[jm58660]

comment:14

For testing might be easier to first make #34933.

[sagetrac-git]

Changed commit from 200441d to 5cd17f1

[sagetrac-git]

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

5cd17f1

correcting function

[Sandstorm831]

comment:16

Thanks Jori for the help. http://www.findstat.org/StatisticsDatabase/St001106/ helped me a lot to figure out original meaning of supergreedy as mentioned in article. This time I checked my function extensively on this dataset, and glad to tell all of them passed. please look at my code, and would be glad for reviews.

[jm58660]

comment:18

I will read the code later. I guess this works now; FYI here are my test codes:

for i in range(9):
    for P in Posets(i):
        a = sum(1 for le in P.linear_extensions() if le.is_supergreedy())
        b = sum(1 for _ in P._hasse_diagram.supergreedy_linear_extensions_iterator())
        if a != b:
            P.show()
            break
    else:
        print("OK %s" % i)

for i in range(100):
    P = posets.RandomPoset(10, 0.15)
    for le_ in P._hasse_diagram.supergreedy_linear_extensions_iterator():
        le = P.linear_extension([P[e] for e in le_])
        if not le.is_supergreedy():
            P.show()
            print(le)
            break
    else:
        print("OK")

for i in range(100):
    P = posets.RandomPoset(10, 0.15)
    a = sum(1 for le in P.linear_extensions() if le.is_supergreedy())
    b = sum(1 for _ in P._hasse_diagram.supergreedy_linear_extensions_iterator())
    if a != b:
        P.show()
        break
    print(i)

[jm58660]

comment:19

Html documentation does not build nicely. Needs an empty line after EXAMPLES::. And yes, this is irritating.

[sagetrac-git]

Changed commit from 5cd17f1 to 1406cdc

[sagetrac-git]

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

1406cdc

documentation changes

[Sandstorm831]

comment:21

Sorry for the inconvenience caused sir

[jm58660]

comment:22

No more complains.

[jm58660]

Author: Rohan Garg

[jm58660]

Reviewer: Jori Mäntysalo

[jm58660]

comment:23

(To clarify "And yes, this is irritating.": I meant that the docbuild system is irritating, it is very easy to have documentation compiled but with wrong indentation or similar.)

[Sandstorm831]

comment:24

ok, got it. Sir, Can you suggest more few more tickets to work upon. I also have 2 more tickets I am working upon and needs review so it would be great If you can give review on those also. 33548 and 32439.

[jm58660]

comment:25

For 33548 no, I do not know matrices good enough. For 32439 maybe, but I suggest asking for someone else.

[Sandstorm831]

comment:26

Ok, thanks sir

[vbraun]

I'm getting

sage -t --long --warn-long 37.4 --random-seed=123 src/sage/combinat/posets/linear_extensions.py
**********************************************************************
File "src/sage/combinat/posets/linear_extensions.py", line 283, in sage.combinat.posets.linear_extensions.?.is_supergreedy
Failed example:
    for l in Q.linear_extensions():
        if not l.is_supergreedy():
            print(l)
Expected:
    [0, 1, 2, 3, 4]
    [0, 2, 3, 1, 4]
    [0, 2, 1, 3, 4]
Got:
    [0, 2, 1, 3, 4]
**********************************************************************
1 item had failures:
   1 of   9 in sage.combinat.posets.linear_extensions.?.is_supergreedy
    [174 tests, 1 failure, 0.16 s]
----------------------------------------------------------------------
sage -t --long --warn-long 37.4 --random-seed=123 src/sage/combinat/posets/linear_extensions.py  # 1 doctest failed
----------------------------------------------------------------------

Since we just moved to github please create a pull request here to continue working on this ticket

[Sandstorm831]

Yes sir, I have already opened a PR and also corrected the issue. Thankyou for your response.

[mkoeppe]

Removed branch from the issue description; replaced by PR #34970.