Opened 6 years ago
Closed 6 years ago
#21442 closed enhancement (fixed)
Add a function to check if a given subset is convex in a poset
Reported by:  Jori Mäntysalo  Owned by:  

Priority:  major  Milestone:  sage7.4 
Component:  combinatorics  Keywords:  
Cc:  Travis Scrimshaw  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 6 years ago by
Branch:  → u/jmantysalo/is_convex 

comment:2 Changed 6 years ago by
Cc:  Travis Scrimshaw added 

Commit:  → 027a455dd2cf816427c490f5cf82a034b502239e 
Status:  new → needs_review 
comment:3 followup: 5 Changed 6 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 6 years ago by
Commit:  027a455dd2cf816427c490f5cf82a034b502239e → a471f630ffeaa229bc395fe27f7e321711c87459 

Branch pushed to git repo; I updated commit sha1. New commits:
a471f63  Strange error in variable name.

comment:5 Changed 6 years ago by
Status:  needs_review → 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 6 years ago by
Reviewers:  → 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 6 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 6 years ago by
Commit:  a471f630ffeaa229bc395fe27f7e321711c87459 → faa722a673f77b15e2744be9d5b8fab3bf20e5ef 

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

comment:9 Changed 6 years ago by
Status:  needs_work → needs_review 

Now at last. Coded when sick, hope that works still...
comment:11 Changed 6 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 6 years ago by
Commit:  faa722a673f77b15e2744be9d5b8fab3bf20e5ef → 52dc3e125ecb0ca55419b6cd63edaed0e20622b9 

Branch pushed to git repo; I updated commit sha1. New commits:
52dc3e1  Reviewer comments.

comment:13 Changed 6 years ago by
Status:  needs_review → positive_review 

Suggested minor changes done.
comment:14 Changed 6 years ago by
Branch:  u/jmantysalo/is_convex → 52dc3e125ecb0ca55419b6cd63edaed0e20622b9 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
Add is_convex_subset().