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:  sage7.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: 
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
 Branch set to u/jmantysalo/is_convex
comment:2 Changed 5 years ago by
 Cc tscrim added
 Commit set to 027a455dd2cf816427c490f5cf82a034b502239e
 Status changed from new to needs_review
comment:3 followup: ↓ 5 Changed 5 years ago by
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
 Commit changed from 027a455dd2cf816427c490f5cf82a034b502239e to a471f630ffeaa229bc395fe27f7e321711c87459
Branch pushed to git repo; I updated commit sha1. New commits:
a471f63  Strange error in variable name.

comment:5 in reply to: ↑ 3 Changed 5 years ago by
 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 rechecking.
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
 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): 2100 2100 if b >= s_max or b in S: 2101 2101 continue 2102 2102 # 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): 2104 2106 if c in S: # Now c in S, b not in S, a in S, a < b < c. 2105 2107 return False 2106 2108 ok.add(c) # Do not recheck this for being our b.
Then if all tests pass, positive review.
comment:7 Changed 5 years ago by
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 recheck my code and make a doctest that will catch error like this one.
comment:8 Changed 5 years ago by
 Commit changed from a471f630ffeaa229bc395fe27f7e321711c87459 to faa722a673f77b15e2744be9d5b8fab3bf20e5ef
Branch pushed to git repo; I updated commit sha1. New commits:
faa722a  Fixes.

comment:9 Changed 5 years ago by
 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
Just pinging.
comment:11 Changed 5 years ago by
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
 Commit changed from faa722a673f77b15e2744be9d5b8fab3bf20e5ef to 52dc3e125ecb0ca55419b6cd63edaed0e20622b9
Branch pushed to git repo; I updated commit sha1. New commits:
52dc3e1  Reviewer comments.

comment:13 Changed 5 years ago by
 Status changed from needs_review to positive_review
Suggested minor changes done.
comment:14 Changed 5 years ago by
 Branch changed from u/jmantysalo/is_convex to 52dc3e125ecb0ca55419b6cd63edaed0e20622b9
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Add is_convex_subset().