Opened 7 years ago
Closed 7 years ago
#19253 closed enhancement (fixed)
Complete and Random SemiComplete digraph generators
Reported by:  dcoudert  Owned by:  

Priority:  minor  Milestone:  sage6.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: 
Description
A digraph is semicomplete 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 semicomplete digraphs via degree orderings. STACS 2013: 197208
Change History (11)
comment:1 Changed 7 years ago by
Branch:  → u/dcoudert/semi_complete 

comment:2 Changed 7 years ago by
Commit:  → f22a25687eda64adad64f2bc937edd3454414be8 

Status:  new → needs_review 
comment:3 Changed 7 years ago by
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
comment:4 Changed 7 years ago by
Commit:  f22a25687eda64adad64f2bc937edd3454414be8 → b64112fa62bf423f5f85cf4ad186d78ea8ebd392 

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.

comment:5 Changed 7 years ago by
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
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
comment:7 Changed 7 years ago by
Commit:  b64112fa62bf423f5f85cf4ad186d78ea8ebd392 → 0c5306860ba84ca75b6719988ec961062f39e9be 

Branch pushed to git repo; I updated commit sha1. New commits:
0c53068  trac #19253: improve documentation

comment:8 Changed 7 years ago by
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
Reviewers:  → Nathann Cohen 

Status:  needs_review → positive_review 
Okayyyyyyyyyy,
Nathann
comment:11 Changed 7 years ago by
Branch:  u/dcoudert/semi_complete → 0c5306860ba84ca75b6719988ec961062f39e9be 

Resolution:  → fixed 
Status:  positive_review → closed 
I have named the the comple digraph generator
CompleteDiGraph
since we haveCompleteGraph
. ForRandomSemiCompleteDiGraph
, we may decide to removeDiGraph
. Let me know. David.New commits:
trac #19253: complete digraph generator
trac #19253: random semicomplete digraph generator
trac #19253: fix doc
trac #19253: fix doc and doctests