Opened 5 years ago

Closed 5 years ago

#17004 closed enhancement (fixed)

Adding height() function to Poset

Reported by: jmantysalo Owned by:
Priority: minor Milestone: sage-6.4
Component: combinatorics Keywords:
Cc: Merged in:
Authors: Jori Mäntysalo Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: b6f9766 (Commits) Commit: b6f976600a1880f5b4f371bf02b0a4c501c09f32
Dependencies: Stopgaps:

Description (last modified by tscrim)

The height of a poset is the cardinality of the longest chain and can be computed by the rank of a poset (the length of the longest chain) plus 1.

Change History (27)

comment:1 Changed 5 years ago by jmantysalo

  • Description modified (diff)

comment:2 Changed 5 years ago by jmantysalo

  • Description modified (diff)

comment:3 Changed 5 years ago by jmantysalo

This was trivial, thanks to (again) ncohen: height of poset P is just P.rank()+1.

comment:4 Changed 5 years ago by jmantysalo

  • Description modified (diff)
  • Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

comment:5 Changed 5 years ago by ncohen

  • Status changed from needs_review to positive_review

When a ticket is in wontfix, set it to positive review.

Nathann

comment:6 Changed 5 years ago by tscrim

  • Milestone changed from sage-duplicate/invalid/wontfix to sage-6.4
  • Status changed from positive_review to needs_work

I believe this is useful to have because I wouldn't think of using rank for a non-ranked poset (although it might be somewhat naive of me) and height is common terminology.

In your code for optimization purposes, you would be better served by plugging in P.rank() + 1, but from a user-interface/teaching perpective, it would be good to have a height method.

comment:7 Changed 5 years ago by tscrim

  • Description modified (diff)

comment:8 Changed 5 years ago by jmantysalo

At least Sage documentation should contain a phrase "height of poset" somewhere. It can be added to docs of .rank(), or made as new function. I'll start discussion on devel-list.

comment:9 Changed 5 years ago by tscrim

This isn't a controversial issue (at this point), so a sage-devel discussion is overkill IMO.

comment:10 Changed 5 years ago by jmantysalo

  • Branch set to u/jmantysalo/adding_height___function_to_poset

comment:11 Changed 5 years ago by jmantysalo

  • Commit set to 55738f43a661ea4da60a737d31c94509a1da5de6
  • Status changed from needs_work to needs_review

Here it is. Haven't been any discussion on devel-list yet.


New commits:

55738f4Added a function height() := rank()+1.

comment:12 Changed 5 years ago by tscrim

  • Authors set to Jori Mäntysalo
  • Reviewers set to Travis Scrimshaw

Two typos, you're missing a "the" in front of height and lenght. Although I'd format the one-liner as you did in the header:

Return the height (the length of longest chain) of the poset.

but I don't really care that much. Once the typos are fixed or the formatting change is made, you can set this to positive review.

comment:13 Changed 5 years ago by git

  • Commit changed from 55738f43a661ea4da60a737d31c94509a1da5de6 to a367c4904a680edd46f72afd7ce20a95dc9d54d2

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

a367c49Typo correction & change of wording.

comment:14 Changed 5 years ago by jmantysalo

Corrected. Still thinking: should we say "number of elements in the longest chain" to be exact?

comment:15 Changed 5 years ago by tscrim

Ack, you're right. The length is the rank, the number of elements is the height. *facepalm*

comment:16 Changed 5 years ago by git

  • Commit changed from a367c4904a680edd46f72afd7ce20a95dc9d54d2 to 1372d5c5de99df1dd2a82ddf7ceed83f3873e84f

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

1372d5cBetter phrasing for function description.

comment:17 Changed 5 years ago by jmantysalo

Now I guess this is done. Left for checking. (I'm always unsure about a/an vs. the -thing; finnish differs quite a much from english.)

comment:18 Changed 5 years ago by tscrim

  • Status changed from needs_review to positive_review

I don't know any Finnish whatsoever, so you have me beat.

comment:19 Changed 5 years ago by vbraun

Conflicts with #17013

comment:20 Changed 5 years ago by vbraun

  • Status changed from positive_review to needs_work

comment:21 Changed 5 years ago by tscrim

Are you sure about that Volker? #17013 doesn't modify the same files and is about a different part of Sage.

comment:22 Changed 5 years ago by vbraun

Sorry, meant #16892

comment:23 Changed 5 years ago by tscrim

Jori, will you handle the merge or do you want me to do it?

comment:24 follow-up: Changed 5 years ago by jmantysalo

Travis, I guess you can do it much faster. So go ahead.

Does this mean that adding, for example, wrapper function .is_connected() will also conflict?

comment:25 in reply to: ↑ 24 Changed 5 years ago by tscrim

Replying to jmantysalo:

Travis, I guess you can do it much faster. So go ahead.

I'll do it tomorrow (it's 11 PM in California right now).

Does this mean that adding, for example, wrapper function .is_connected() will also conflict?

Not necessarily (chances are probably not), although if you want to be absolutely sure you can base that off this branch.

comment:26 Changed 5 years ago by tscrim

  • Branch changed from u/jmantysalo/adding_height___function_to_poset to u/tscrim/poset_height-17004
  • Commit changed from 1372d5c5de99df1dd2a82ddf7ceed83f3873e84f to b6f976600a1880f5b4f371bf02b0a4c501c09f32
  • Status changed from needs_work to positive_review

New commits:

f13f238Added a (wrapper) function to posets.
160d8a5Added two simple wrapper functions.
d4c0285Version with both isomorphic_subposets() and isomorphic_subposets_iterator().
87b5852Better documentation.
f1d0174Moved import statement to function; corrections to docs.
ad47132trac #16909: transitive_closure() and mutable graphs
346ef0eMerge branch 't/16909/public/16909' into t/16892/function_to_check_if_a_poset_containt_a_subposet_isomorphic_to_another_poset
7394736Merge branch 'u/jmantysalo/function_to_check_if_a_poset_containt_a_subposet_isomorphic_to_another_poset' of trac.sagemath.org:sage into u/tscrim/poset_height-17004
b6f9766Merge branch 'u/jmantysalo/adding_height___function_to_poset' of trac.sagemath.org:sage into u/tscrim/poset_height-17004

comment:27 Changed 5 years ago by vbraun

  • Branch changed from u/tscrim/poset_height-17004 to b6f976600a1880f5b4f371bf02b0a4c501c09f32
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.