Cleanup of sage.graphs.pq_trees

[nathanncohen]

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

CC: @dcoudert @dimpase

Component: graph theory

Author: Nathann Cohen

Branch/Commit: 07ca59d

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/17804

[nathanncohen]

Branch: u/ncohen/17804

[sagetrac-git]

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

707124c	trac #17804: Rename .cardinality to .number_of_children
6a1b563	trac #17804: Add cardinality function to know the number of orderings
7fa50a0	trac #17804: Add orderings() to list all orderings
7f73cea	trac #17804: Remove .is_P and .is_Q
ff247ce	trac #17804: Move and rephrase the PQ-trees documentation at module's level
07ca59d	trac #17804: Typos and one-line changes

[sagetrac-git]

Commit: 07ca59d

[dcoudert]

comment:4

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.

[nathanncohen]

comment:5

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

[dcoudert]

comment:7

So let the text as it is.
David.

[dcoudert]

Reviewer: David Coudert

[nathanncohen]

comment:9

Thanks !

[vbraun]

Changed branch from u/ncohen/17804 to 07ca59d