Complete and Random Semi-Complete digraph generators

[dcoudert]

A digraph is semi-complete if for any pair of vertices u and v, it has at least one edge of uv and vu. Such digraphs have been used in the study of directed pathwidth and cutwidth [1].

Surprizingly, we had no complete digraph generator. This is now done.

[1] Michal Pilipczuk. Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings. STACS 2013: 197-208

Component: graph theory

Author: David Coudert

Branch/Commit: 0c53068

Reviewer: Nathann Cohen

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

[dcoudert]

Branch: u/dcoudert/semi_complete

[dcoudert]

comment:2

I have named the the comple digraph generator CompleteDiGraph since we have CompleteGraph.
For RandomSemiCompleteDiGraph, we may decide to remove DiGraph. Let me know.
David.

---

New commits:

6bd7563	trac #19253: complete digraph generator
3815aac	trac #19253: random semi-complete digraph generator
c8c2f45	trac #19253: fix doc
f22a256	trac #19253: fix doc and doctests

[dcoudert]

Commit: f22a256

[nathanncohen]

comment:3

Hello David,

Could you add seealso links between your two functions and RandomTournament? I can imagine that somebody who is looking for a random tournament may go straight to either of your two functions (and conversely).

Also, I am surprised that you need to distinguish the case n=0 in RandomSemiCompleteDigraph. Is that really necessary?

About the final *DiGraph: it is really stupid that graphs end in ...Graph and digraphs does not, but until we decide to change that let's stick to the most local standard. Could you remove it please? :-/

Lastly, could you document in RandomSemiCompleteDiGraph how the edges will be distributed, i.e. explicit that you each of uv,vu,(uv+vu) is equally likely?

Thanks,

Nathann

[sagetrac-git]

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

7a8a54c	trac #19253: remove DiGraph from methods names
e45b71b	trac #19253: add seealso section between complete, randomtournament and randomsemicomplete
61ca216	trac #19253: remove case n==0 in randomsemicomplete
b64112f	trac #19253: fix see also, doc, explain randomsemicomplete, etc.

[sagetrac-git]

Changed commit from f22a256 to b64112f

[dcoudert]

comment:5

I have addressed all your comments.
For the edge distribution in RandomSemiComplete, I'm not able to find relevant link on the web. I have put some explanation.
David.

[nathanncohen]

comment:6

Hello again,

It seems that the documentation of RandomSemiComplete is not displayed as intended. Sphinx does not like it when one mixes italic and latex formulas. Also, the seealso section usually appears before the tests.

Could you also move the entry of RandomSemiComplete one line above, i.e. next to the other random graph generators?

Nathann

[sagetrac-git]

Changed commit from b64112f to 0c53068

[sagetrac-git]

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

0c53068

trac #19253: improve documentation

[dcoudert]

comment:8

I have implemented all requested changes. In particular, I have rephrased the documentation to avoid the italic/latex issue.
David.

[nathanncohen]

Reviewer: Nathann Cohen

[nathanncohen]

comment:9

Okayyyyyyyyyy,

Nathann

[dcoudert]

comment:10

Thank you so much Nathann.
Best,
David.

[vbraun]

Changed branch from u/dcoudert/semi_complete to 0c53068