Add a method to enumerate cographs

[dcoudert]

trafficstars

As suggested in #37964, this PR add a method to enumerate cographs of order n. We add a new file that could collect all methods related to cographs (enumeration, random generator, identification, etc.).

The original implementation is due to Marianna Spyrakou (https://github.com/MariannaSpyrakou/Cograph_generator).

:memo: Checklist

• [x] The title is concise and informative.
• [x] The description explains in detail what this PR is about.
• [x] I have linked a relevant issue or discussion.
• [x] I have created tests covering the changes.
• [x] I have updated the documentation and checked the documentation preview.

:hourglass: Dependencies

[github-actions[bot]]

Documentation preview for this PR (built with commit c8a1949968e557a98919b901cb646a441e33ec23; changes) is ready! :tada: This preview will update shortly after each push to this PR.

[dimpase]

This method implements the generator of all cographs of order proposd in [JPD2018].

proposed - typo

[...] Hence, the overall complexity of the algorithm is

looks like O(n*Mn) but should be $O(n M_n)$

[dcoudert]

Thanks fo pointing these typos.

We could certainly improve the computation time (in future PR).

n	M_n	time
2	2	0.0
3	4	0.0
4	10	0.0
5	24	0.001
6	66	0.002
7	180	0.006
8	522	0.016
9	1532	0.046
10	4624	0.139
11	14136	0.484
12	43930	1.746
13	137908	5.968
14	437502	20.997
15	1399068	73.866

[dimpase]

Have you re-used any code or design from Marianna Spyrakou's work? If so, her name should be in copyright notice.

[dimpase]

Any reason to re-implement next partition? Lexicographically next partition to a given one can be done by Sage already. e.g.

sage: m=Partitions(8)
sage: m.next([8])
[7, 1]
sage: m.next(m.next([8]))
[6, 2]
sage: m.next(m.next(m.next([8])))
[6, 1, 1]

[tscrim]

Any reason to re-implement next partition? Lexicographically next partition to a given one can be done by Sage already. e.g.

sage: m=Partitions(8)
sage: m.next([8])
[7, 1]
sage: m.next(m.next([8]))
[6, 2]
sage: m.next(m.next(m.next([8])))
[6, 1, 1]

Unfortunately that implementation is fairly generic and slow (it goes through the list of all partitions and simply finds the current one and then gets the next). Also, the next partition here is opposite of what Sage does (lex increasing versus decreasing).

[dimpase]

Any reason to re-implement next partition? Lexicographically next partition to a given one can be done by Sage already. e.g.

sage: m=Partitions(8)
sage: m.next([8])
[7, 1]
sage: m.next(m.next([8]))
[6, 2]
sage: m.next(m.next(m.next([8])))
[6, 1, 1]

Unfortunately that implementation is fairly generic and slow (it goes through the list of all partitions and simply finds the current one and then gets the next). Also, the next partition here is opposite of what Sage does (lex increasing versus decreasing).

Well, perhaps it's a good moment to improve Sage's Partitions using David's code here? (we'd have .previous() for what's needed here, and .next() for the opposite direction move) Having multiple implementations of the same thing isn't good design.

[dcoudert]

@dimpase : Yes, I must add Marianna Spyrakou in the copyright

@dimpase, @tscrim: I agree that it's a good idea to improve the code of next and to add method previous.

I cannot work on that yet (broken sage since last beta), but will contribute asap.

[tscrim]

@dimpase I agree it is not good design. What I am saying here is what @dcoudert is providing isn't duplicated. However, moving it to a prev(ious) method of partitions would be good.

[dcoudert]

@dimpase, @tscrim. Concerning the enumeration of partitions, the iterator of Partitions is based on algorithm ZS1 of https://static.aminer.org/pdf/PDF/000/289/332/counting_and_generating_integer_partitions_in_parallel.pdf. It goes in anti-lexicographic.

The paper also proposed an algorithm, ZS2 for enumerating partitions in lexicographic order. We will certainly have to implement it.

[tscrim]

It would be nice to have that, but it doesn't do so well starting from the middle. Well, I guess setting the invariants correctly would work, but that wouldn't necessarily be how I would implement it...

[dcoudert]

@dimpase, @tscrim I have almost all the material ready to push a PR with 4 different algorithms for generating partitions. Some algorithms generate partitions in increasing/decreasing lexicographic order and partitions are represented in ascending/descending orders. On the way I have prepared a next function based on each generator. So users should find the method they need.

I currently need #38020 to get a working sage installation. Can I push a PR based on that or is it better if I wait until the develop branch is fixed on my side ?

[tscrim]

Could you make your build with #38020 and then go back to being based off clean develop to do the development? In particular, without running sage -b and/or make? Does even running sage -b cause problems? I had a similar issue in the past, but it only would have appeared when running make with package building.

[dcoudert]

Could you make your build with #38020 and then go back to being based off clean develop to do the development? In particular, without running sage -b and/or make? Does even running sage -b cause problems? I had a similar issue in the past, but it only would have appeared when running make with package building.

Well, I tried going switching to develop (without any further action), then back to my working branch and run sage -b. It launches a huge compilation. So I will wait for a working develop branch.

[dimpase]

switch to Linux :-)

[dcoudert]

switch to Linux :-)

I was able to push the PR from a lux fedora server. This is #38054.

[dcoudert]

@dimpase @tscrim, I'm now using a next method introduced in #38054.

[dcoudert]

May be I should add a _ to the name of some internal methods to avoid showing them in the documentation. Let me know.

[dcoudert]

Thanks for the suggestion. Let's see if it goes well.

[dcoudert]

You can disregard my additional change if you want. In either case, you can set a positive review afterwards.

This is now going well, so I'm setting this PR to positive review. Thank you for the review.