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: the PQ-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 with isinstance(x,P) and isinstance(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 ncohen

  • Branch set to u/ncohen/17804
  • Status changed from new to needs_review

comment:2 Changed 5 years ago by git

  • Commit set to 07ca59dfb8deb9553c4ed9e1ea79a6a394026334

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

707124ctrac #17804: Rename .cardinality to .number_of_children
6a1b563trac #17804: Add cardinality function to know the number of orderings
7fa50a0trac #17804: Add orderings() to list all orderings
7f73ceatrac #17804: Remove .is_P and .is_Q
ff247cetrac #17804: Move and rephrase the PQ-trees documentation at module's level
07ca59dtrac #17804: Typos and one-line changes

comment:3 Changed 5 years ago by ncohen

  • Cc dimpase added

comment:4 follow-up: Changed 5 years ago by dcoudert

  • 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 ncohen

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 ncohen

  • Status changed from needs_work to needs_review

comment:7 Changed 5 years ago by dcoudert

  • Status changed from needs_review to positive_review

So let the text as it is. David.

comment:8 Changed 5 years ago by dcoudert

  • Reviewers set to David Coudert

comment:9 Changed 5 years ago by ncohen

Thanks !

comment:10 Changed 5 years ago by vbraun

  • Branch changed from u/ncohen/17804 to 07ca59dfb8deb9553c4ed9e1ea79a6a394026334
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.