Opened 5 years ago

Closed 5 years ago

#21442 closed enhancement (fixed)

Add a function to check if a given subset is convex in a poset

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-7.4
Component: combinatorics Keywords:
Cc: tscrim Merged in:
Authors: Jori Mäntysalo Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 52dc3e1 (Commits, GitHub, GitLab) Commit: 52dc3e125ecb0ca55419b6cd63edaed0e20622b9
Dependencies: Stopgaps:

Status badges

Description

This patch will add a helper function to hasse_diagram.py to check that a subset of elements is convex in a poset.

Will be needed to check user input for Alan Day's doubling construction.

Change History (14)

comment:1 Changed 5 years ago by jmantysalo

  • Branch set to u/jmantysalo/is_convex

comment:2 Changed 5 years ago by jmantysalo

  • Cc tscrim added
  • Commit set to 027a455dd2cf816427c490f5cf82a034b502239e
  • Status changed from new to needs_review

New commits:

027a455Add is_convex_subset().

comment:3 follow-up: Changed 5 years ago by tscrim

What is x here:

lambda v: [v for v in self.neighbor_out_iterator(x) if v < s_max and s not in ok]

I don't see it in the code. Also, at present it seems like that function could be pulled out of the for loop.

comment:4 Changed 5 years ago by git

  • Commit changed from 027a455dd2cf816427c490f5cf82a034b502239e to a471f630ffeaa229bc395fe27f7e321711c87459

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

a471f63Strange error in variable name.

comment:5 in reply to: ↑ 3 Changed 5 years ago by jmantysalo

  • Status changed from needs_review to needs_work

Replying to tscrim:

What is x here:

lambda v: [v for v in self.neighbor_out_iterator(x) if v < s_max and s not in ok]

What the hell I did? Should be b, but I do not know how this happened and was not catch by doctest. Now compiling and re-checking.

I don't see it in the code. Also, at present it seems like that function could be pulled out of the for loop.

I don't understand. The idea is to (try to) found an element a in S covered by element b not in S and then check if some directed path from b goes to some element c in S.

comment:6 Changed 5 years ago by tscrim

  • Reviewers set to Travis Scrimshaw

Well, since there is a dependence on b, my second sentence is moot/invalid. I would just like to see the following to get it ~80 chars per line:

  • src/sage/combinat/posets/hasse_diagram.py

    a b class HasseDiagram(DiGraph): 
    21002100                if b >= s_max or b in S:
    21012101                    continue
    21022102                # Now b not in S, b > a and a in S.
    2103                 for c in self.depth_first_search(a, neighbors=lambda v: [v for v in self.neighbor_out_iterator(b) if v < s_max and s not in ok]):
     2103                neighbors = lambda v: [v for v in self.neighbor_out_iterator(b)
     2104                                       if v < s_max and s not in ok]
     2105                for c in self.depth_first_search(a, neighbors=neighbors):
    21042106                    if c in S:  # Now c in S, b not in S, a in S, a < b < c.
    21052107                        return False
    21062108                    ok.add(c)  # Do not re-check this for being our b.

Then if all tests pass, positive review.

comment:7 Changed 5 years ago by jmantysalo

This was an interesting case. Basic "bug" is just a feature, and can be seen with

sage: g = Graph(42) sage: for x in g.depth_first_search(0, neighbors=lambda v: junk(v)): ....: print(x)

which will output 0 and only after that gives error message. So I really must re-check my code and make a doctest that will catch error like this one.

Version 0, edited 5 years ago by jmantysalo (next)

comment:8 Changed 5 years ago by git

  • Commit changed from a471f630ffeaa229bc395fe27f7e321711c87459 to faa722a673f77b15e2744be9d5b8fab3bf20e5ef

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

faa722aFixes.

comment:9 Changed 5 years ago by jmantysalo

  • Status changed from needs_work to needs_review

Now at last. Coded when sick, hope that works still...

comment:10 Changed 5 years ago by jmantysalo

Just pinging.

comment:11 Changed 5 years ago by tscrim

Looks good. Two trivial things:

  • I'm paranoid, but anytime there is latex, I like to use raw strings: r"""
  • Could you break this line:
    -neighbors = lambda v_: [v for v in self.neighbor_out_iterator(v_) if v <= s_max and v not in ok]
    +neighbors = lambda v_: [v for v in self.neighbor_out_iterator(v_)
    +if v <= s_max and v not in ok]
    

You can set a positive review on my behalf.

comment:12 Changed 5 years ago by git

  • Commit changed from faa722a673f77b15e2744be9d5b8fab3bf20e5ef to 52dc3e125ecb0ca55419b6cd63edaed0e20622b9

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

52dc3e1Reviewer comments.

comment:13 Changed 5 years ago by jmantysalo

  • Status changed from needs_review to positive_review

Suggested minor changes done.

comment:14 Changed 5 years ago by vbraun

  • Branch changed from u/jmantysalo/is_convex to 52dc3e125ecb0ca55419b6cd63edaed0e20622b9
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.