implement random planar bicubic graphs in a bijective way

[fchapoton]

using an algorithm of Schaeffer (bijection with blossoming trees)

CC: @kevindilks @dimpase @sagetrac-pportilla @dcoudert

Component: graph theory

Author: Frédéric Chapoton

Branch/Commit: e3da5b2

Reviewer: Dima Pasechnik

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

[fchapoton]

Branch: u/chapoton/21951

[fchapoton]

New commits:

5173db4

implement a generator for random bicubic planar graphs (rooted maps)

[fchapoton]

Commit: 5173db4

[fchapoton]

comment:4

looking for a referee...

[fchapoton]

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
-using an algorithm of Schaeffer
+using an algorithm of Schaeffer (bijection with blossoming trees)

[dimpase]

comment:5

Do you have a script to test it? I mean, the total number of such graphs is known for small values of n (cf. https://oeis.org/A007085) and so it's possible to run it many times and see whether you can get anywhere close to a uniform distribution.

By the way, there are few trailing spaces in the branch.

[dcoudert]

comment:6

When looking at the diff of your branch here, it seems that it deletes file graph_generators.py. Please check...

[dimpase]

comment:7

no, it's OK, it's a git viewer bug; I saw this few times. If you fetch the branch it's OK. It adds 2 lines to the file that is shown as deleted.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 5173db4 to e3da5b2

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

900fbe9	Merge branch 'u/chapoton/21951' in 7.5.b6
e3da5b2	trac 21951 remove trailing spaces

[fchapoton]

comment:9

Hmm, this algorithm does not generate only 3-connected graphs.

It seems that the sequence of numbers is not in the OEIS:

sage: resu = {i: set() for i in range(1,6)}
sage: liste = []                           
....: for n in range(1,6):
....:     for k in range(6600):
....:         g = graphs.RandomBicubicPlanar(n)
....:         h = g.copy(immutable=True)
....:         resu[n].add(hash(h))
....:     liste.append(len(resu[n]))
sage: liste
[1, 3, 17, 103, 642]

Probably a better way to check would be to return also the root edge, so that the number of different possible outputs is given by Tutte's formula in A257.

[dimpase]

comment:10

Replying to @fchapoton:

Hmm, this algorithm does not generate only 3-connected graphs.

Right - but you could drop ones that are not 3-connected, and also drop the marked (root) edge and count the results up to an isomorphism, and this would give you the OEIS sequence.

It seems that the sequence of numbers is not in the OEIS:

sage: resu = {i: set() for i in range(1,6)}
sage: liste = []                           
....: for n in range(1,6):
....:     for k in range(6600):
....:         g = graphs.RandomBicubicPlanar(n)
....:         h = g.copy(immutable=True)
....:         resu[n].add(hash(h))
....:     liste.append(len(resu[n]))
sage: liste
[1, 3, 17, 103, 642]

Probably a better way to check would be to return also the root edge, so that the number of different possible outputs is given by Tutte's formula in A257.

[fchapoton]

comment:11

ping ?

[dimpase]

comment:12

OK, can you say anything about the distribution of your random graphs? Asking the user to check the original article for this is a bit too much...

[fchapoton]

comment:13

Here is at least a way to check that it generates A000257: Number of rooted bicubic maps: a(n) = (8n-4)*a(n-1)/(n+2)

A procedure to faithfully encode the rooted map in a digraph:

def bicubic_dual_grand(g):
    G = DiGraph()
    for a, b, c in g.edges():
        ac = a + (c,)
        bc = b + (c,)
        G.add_edge((ac, bc))
        G.add_edge((bc, ac))
    for vert in g:
        if vert[0] == 'i':
            clef = (0, 1, 2)
        else:
            clef = (1, 0, 2)

        A, B, C = [vert + (c,) for c in clef]
        G.add_edge(A, B)
        G.add_edge(B, C)
        G.add_edge(C, A)

    op_root = [u for u in G.outgoing_edge_iterator(('n', -1, 0))
               if u[1][0] == 'i']
    G.delete_edge(op_root[0])
    return G

then

sage: resu = {i: set() for i in range(1,6)}
sage: liste = []                           
....: for n in range(1,6):
....:     for k in range(400*n):
....:         g = bicubic_dual_grand(graphs.RandomBicubicPlanar(n)).canonical_label()
....:         h = g.copy(immutable=True)
....:         resu[n].add(h)
....:     liste.append(len(resu[n]))
sage: liste

Checking uniformity should be doable similarly.

[dimpase]

comment:14

I don't always get all the graphs; in some runs for n=6 I get one graph less, and for n=7 I got only 1230 (instead of 1584, according to OEIS). Here is one more run of your script in the range [1..8]:

sage: liste
[1, 3, 12, 56, 288, 1242, 2418]

I did not check, perhaps the non-uniformity is not in your branch, but somewhere else...

[fchapoton]

comment:15

Well, this is random generation, so probably you just need to run more times. The bound 400*n is quite arbitrary, and likely to be insufficient for n>=7. I do not know how many runs would be sufficient to get all of them with high probability.

[dimpase]

comment:16

Replying to @fchapoton:

Well, this is random generation, so probably you just need to run more times. The bound 400*n is quite arbitrary, and likely to be insufficient for n>=7. I do not know how many runs would be sufficient to get all of them with high probability.

Increasing bound to 4000*n gives

[1, 3, 12, 56, 288, 1584, 8710]

OK, this looks reasonable. If there is anything regarding the distribution in the text you refer to, please add it to the docs. Otherwise it's good to go.

[fchapoton]

comment:17

Thanks for your help.

As I have already explained in the doc, the distribution is uniform.

[dimpase]

Reviewer: Dima Pasechnik

[dimpase]

comment:18

Happy NY!

[vbraun]

Changed branch from u/chapoton/21951 to e3da5b2