implement random triangulations in a bijective way

[fchapoton]

This will provide a fast uniform (almost) random generator for triangulations.

This uses the algorithm via a bijection with blossoming trees due to Schaeffer and Poulalhon.

CC: @nathanncohen

Component: graph theory

Keywords: random graph

Author: Frédéric Chapoton

Branch/Commit: 82289ac

Reviewer: Nathann Cohen

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

[fchapoton]

Commit: 226cef6

[fchapoton]

New commits:

226cef6

implement the bijective random generation of triangulations

[fchapoton]

Branch: u/chapoton/19520

[nathanncohen]

comment:2

Hello,

If you add this then I do not think that we need our former 'randomtriangulation' anymore.

Nathann

P.S.: The difference between listA += listB and listA.extend(listB) is that the first one creates a copy og listA first.

[fchapoton]

comment:3

Well, this is a different "random triangulation", not the same distribution at all. Mine is better because it's almost uniform, but nevertheless one could keep the other.

Should I use .append and .extend everywhere possible ?

[sagetrac-git]

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

10677c9

trac #19520 using append and extend

[sagetrac-git]

Changed commit from 226cef6 to 10677c9

[nathanncohen]

comment:5

Hello Frédéric,

Yours is clearly better, and unless there is a specific reason why we should
keep the old one (please enlighten me) I do not see the point to have it around.

First, because 'graphs.RandomTriangulation' should preferably be what you
implement now: at least the notion of 'random' is clear (and what one would expect).

If you insist on keeping the other, then perhaps it could be a (non-default)
option of RandomTriangulation? Let us not kee code just for the sake of not
throwing anything away. What you did is what RandomTriangulation should be. If
it had been like this from the start, we certainly wouldn't have added the other
function later.

Should I use .append and .extend everywhere possible ?

Yes, please. Let us not waste ressources when we can easily avoid it.

Nathann

[sagetrac-git]

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

d5ce368

trac #19520 remove old RandomTriangulation function

[sagetrac-git]

Changed commit from 10677c9 to d5ce368

[sagetrac-git]

Changed commit from d5ce368 to 9a98a9e

[sagetrac-git]

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

9a98a9e

trac #19520 one more extend

[fchapoton]

comment:8

ok, done. So this ticket now replaces the old implementation of RandomTriangulation by a new one.

[sagetrac-git]

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

2d3020a

trac #19520 removing a call to set_planar_position (which is almost deprecated)

[sagetrac-git]

Changed commit from 9a98a9e to 2d3020a

[nathanncohen]

comment:10

Hello Frédéric,

I only read the content of auxiliary_random_word so far (one cannot say that the construction appears very explicitly in the paper :-/) and added a small commit at public/19520, mainly to point to where the constraints on the binary word are provided in the paper.

Is there any reason why you add +3n and -n in to 'height', instead of compution '3*number_of_1 - number_of_zeroes' like in Proposition 4.2?

Nathann

[fchapoton]

comment:11

Hello,

yes, this part is indeed already not clear. I am not sure to be convinced myself
that the algorithm that I wrote to conjugate the binary word is correct. But it works..

The idea is (like for usual conjugation into Dyck words) to assign a height at every step of the path, and to cut where the height is minimal or almost minimal here...

[nathanncohen]

comment:12

yes, this part is indeed already not clear. I am not sure to be convinced myself
that the algorithm that I wrote to conjugate the binary word is correct.

I'm sorry but I will not accept a code without being convinced that it is correct. Please make sure that this part does what it should, and then set this ticket to needs_review.

Nathann

[sagetrac-git]

Changed commit from 2d3020a to fb300e3

[sagetrac-git]

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

fb300e3

trac #19520 fixing a mistake

[sagetrac-git]

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

315fa4b	trac #19520: Doc work
59c4982	Merge branch 'public/19520' into u/chapoton/19520

[sagetrac-git]

Changed commit from fb300e3 to 59c4982

[sagetrac-git]

Changed commit from eab762d to da83f96

[fchapoton]

comment:51

ok, it suits me. As far as I can tell, this is good to go

The resulting graphs can be nicely displayed by Ivan Kuckir graph viewer.

[nathanncohen]

comment:52

ok, it suits me. As far as I can tell, this is good to go

Okay. I'll do a final check once at home and it will probably be reviewed tonight.

The resulting graphs can be nicely displayed by Ivan Kuckir graph viewer.

What is that?

Nathann

[fchapoton]

comment:53

The resulting graphs can be nicely displayed by Ivan Kuckir graph viewer.

What is that?

#13418

[nathanncohen]

comment:54

Don't you want to help me improve 'g.show(method='js')' instead? I am tring to add a zooming feature right now. It already works in d3.js but I'm not exactly a js expert.

Nathann

[nathanncohen]

comment:55

Errrrrrr... Don't know if it is my fault, but I just noticed that :-P

sage: print graphs.RandomTriangulation(7).vertices()
[0, 1, 2, 3, 4, 'a', 'b', ('in', 0), ('in', 1), ('in', 2), ('in', 3), ('in', 4)]

Nathann

[sagetrac-git]

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

c40e235

trac #19520 fixing the edges

[sagetrac-git]

Changed commit from da83f96 to c40e235

[nathanncohen]

comment:57

Arg... Sorry sorry, I was about to push it but I am currently experimenting with the distribution, to check if everything is 'uniform as expected'. It was my fault, and I did not expect you to fix it for me ^^;

[nathanncohen]

comment:58

Hmmmmmmm... Okay okay. From looking at the distribution I can't say that I quite like it, but then I forgot too much about statistics to prove it in any way :-/

Nathann

[fchapoton]

comment:59

The distribution is not exactly uniform, because it is uniform for "rooted" triangulations, and the presence of automorphisms breaks the uniformity. But in the large size limit, only a negligible number of triangulations do have automorphisms, so this becomes a better and better approx to uniform distribution.

[sagetrac-git]

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

8dc5d13

trac #19520: Last-minute comments

[sagetrac-git]

Changed commit from c40e235 to 8dc5d13

[nathanncohen]

comment:61

If you don't see anything wrong in this last commit, you can set the ticket to positive_review. Thanks!

Nathann

[sagetrac-git]

Changed commit from 8dc5d13 to 703d5af

[sagetrac-git]

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

703d5af

trac #19520 a typo

[fchapoton]

comment:63

ok, let it be. Thanks a lot for your collaboration.

[vbraun]

comment:64

Merge conflict, try again with the next beta

[sagetrac-git]

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

82289ac

Merge branch 'public/19520' into 6.10.b5

[sagetrac-git]

Changed commit from 703d5af to 82289ac

[vbraun]

Changed branch from public/19520 to 82289ac