Opened 5 years ago
Closed 5 years ago
#17804 closed enhancement (fixed)
Cleanup of sage.graphs.pq_trees
Reported by: | ncohen | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.6 |
Component: | graph theory | Keywords: | |
Cc: | dcoudert, dimpase | Merged in: | |
Authors: | Nathann Cohen | Reviewers: | David Coudert |
Report Upstream: | N/A | Work issues: | |
Branch: | 07ca59d (Commits) | Commit: | 07ca59dfb8deb9553c4ed9e1ea79a6a394026334 |
Dependencies: | Stopgaps: |
Description
While fixing the bug reported at #17787, I noticed several things in sage.graphs.pq_trees
that should be cleaned. Some misnamed functions, hard-to-read documentation, and also a couple of simple but useful missing features that can be very helpful when debugging code.
This branch consists of several commits which do the following:
- Rename
.cardinality
to.number_of_children
: thePQ
-trees encode a set of permutations, and the 'cardinality' function should represent that, instead of what it represents now.
- Add a real
.cardinality
function, which can be used to compute the number of different representations of an interval graph
- Add a
.orderings
function, which lists all possibles representations of an interval graph
- remove
.is_P
and.is_Q
. These functions were barely used in the code itself, and can be replaced withisinstance(x,P)
andisinstance(x,Q)
.
- Move the documentation of class PQ-tree, which actually explains how the main algorithm works, into the module's doc. It is also rewritten, and hopefully easier to understand.
- Some one-line changes that improve readability or add links.
Nathann
Change History (10)
comment:1 Changed 5 years ago by
- Branch set to u/ncohen/17804
- Status changed from new to needs_review
comment:2 Changed 5 years ago by
- Commit set to 07ca59dfb8deb9553c4ed9e1ea79a6a394026334
comment:3 Changed 5 years ago by
- Cc dimpase added
comment:4 follow-up: ↓ 5 Changed 5 years ago by
- Status changed from needs_review to needs_work
Hello,
the patch is good (install, docbuild html and pdf, tests).
Before the 4th item (One at a time, we update the data structure...), it would be nice to have some space. I don't know how to force it (I tried).
Also, if you want to play more with your new PLOT command, you could add an example of PQ-tree ;)
David.
comment:5 in reply to: ↑ 4 Changed 5 years ago by
Hellooooooooooooooo,
Before the 4th item (One at a time, we update the data structure...), it would be nice to have some space. I don't know how to force it (I tried).
I do not know either. That is because Sphinx does not like it when a list ends with a sublist. I met this bug several times but I do not know any clean workaround :-/
Also, if you want to play more with your new PLOT command, you could add an example of PQ-tree ;)
I did try, but decided against it because all the pictures I was able to produce took the whole screen vertically, and really 'broke the flow' of the explanations. So I decided against it. This is the kind of options of "plot" that we will need very soon :-P
Nathann
comment:6 Changed 5 years ago by
- Status changed from needs_work to needs_review
comment:7 Changed 5 years ago by
- Status changed from needs_review to positive_review
So let the text as it is. David.
comment:8 Changed 5 years ago by
- Reviewers set to David Coudert
comment:9 Changed 5 years ago by
Thanks !
comment:10 Changed 5 years ago by
- Branch changed from u/ncohen/17804 to 07ca59dfb8deb9553c4ed9e1ea79a6a394026334
- Resolution set to fixed
- Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
trac #17804: Rename .cardinality to .number_of_children
trac #17804: Add cardinality function to know the number of orderings
trac #17804: Add orderings() to list all orderings
trac #17804: Remove .is_P and .is_Q
trac #17804: Move and rephrase the PQ-trees documentation at module's level
trac #17804: Typos and one-line changes