Opened 7 years ago

Closed 7 years ago

#19253 closed enhancement (fixed)

Complete and Random Semi-Complete digraph generators

Reported by: dcoudert Owned by:
Priority: minor Milestone: sage-6.9
Component: graph theory Keywords:
Cc: Merged in:
Authors: David Coudert Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: 0c53068 (Commits, GitHub, GitLab) Commit: 0c5306860ba84ca75b6719988ec961062f39e9be
Dependencies: Stopgaps:

GitHub link to the corresponding issue


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

Change History (11)

comment:1 Changed 7 years ago by dcoudert

Branch: u/dcoudert/semi_complete

comment:2 Changed 7 years ago by dcoudert

Commit: f22a25687eda64adad64f2bc937edd3454414be8
Status: newneeds_review

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:

6bd7563trac #19253: complete digraph generator
3815aactrac #19253: random semi-complete digraph generator
c8c2f45trac #19253: fix doc
f22a256trac #19253: fix doc and doctests

comment:3 Changed 7 years ago by ncohen

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?



comment:4 Changed 7 years ago by git

Commit: f22a25687eda64adad64f2bc937edd3454414be8b64112fa62bf423f5f85cf4ad186d78ea8ebd392

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

7a8a54ctrac #19253: remove DiGraph from methods names
e45b71btrac #19253: add seealso section between complete, randomtournament and randomsemicomplete
61ca216trac #19253: remove case n==0 in randomsemicomplete
b64112ftrac #19253: fix see also, doc, explain randomsemicomplete, etc.

comment:5 Changed 7 years ago by dcoudert

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.

comment:6 Changed 7 years ago by ncohen

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?


comment:7 Changed 7 years ago by git

Commit: b64112fa62bf423f5f85cf4ad186d78ea8ebd3920c5306860ba84ca75b6719988ec961062f39e9be

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

0c53068trac #19253: improve documentation

comment:8 Changed 7 years ago by dcoudert

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

comment:9 Changed 7 years ago by ncohen

Reviewers: Nathann Cohen
Status: needs_reviewpositive_review



comment:10 Changed 7 years ago by dcoudert

Thank you so much Nathann. Best, David.

comment:11 Changed 7 years ago by vbraun

Branch: u/dcoudert/semi_complete0c5306860ba84ca75b6719988ec961062f39e9be
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.