Opened 6 years ago

Closed 6 years ago

#21951 closed enhancement (fixed)

implement random planar bicubic graphs in a bijective way

Reported by: Frédéric Chapoton Owned by:
Priority: major Milestone: sage-7.5
Component: graph theory Keywords:
Cc: Kevin Dilks, Dima Pasechnik, Pablo Portilla , David Coudert Merged in:
Authors: Frédéric Chapoton Reviewers: Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: e3da5b2 (Commits, GitHub, GitLab) Commit: e3da5b2a6996fb16143002e8053ff205cc0fd81e
Dependencies: Stopgaps:

Status badges

Description (last modified by Frédéric Chapoton)

using an algorithm of Schaeffer (bijection with blossoming trees)

Change History (19)

comment:1 Changed 6 years ago by Frédéric Chapoton

Branch: u/chapoton/21951
Commit: 5173db430c60de75758f55efab1c6d21ba2a9135

New commits:

5173db4implement a generator for random bicubic planar graphs (rooted maps)

comment:2 Changed 6 years ago by Frédéric Chapoton

Status: newneeds_review

comment:3 Changed 6 years ago by Kevin Dilks

Cc: Kevin Dilks added

comment:4 Changed 6 years ago by Frédéric Chapoton

Cc: Dima Pasechnik Pablo Portilla David Coudert added
Description: modified (diff)

looking for a referee...

comment:5 Changed 6 years ago by Dima Pasechnik

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.

comment:6 Changed 6 years ago by David Coudert

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

comment:7 Changed 6 years ago by Dima Pasechnik

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.

comment:8 Changed 6 years ago by git

Commit: 5173db430c60de75758f55efab1c6d21ba2a9135e3da5b2a6996fb16143002e8053ff205cc0fd81e

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

900fbe9Merge branch 'u/chapoton/21951' in 7.5.b6
e3da5b2trac 21951 remove trailing spaces

comment:9 Changed 6 years ago by Frédéric Chapoton

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.

Last edited 6 years ago by Frédéric Chapoton (previous) (diff)

comment:10 in reply to:  9 Changed 6 years ago by Dima Pasechnik

Replying to chapoton:

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.

comment:11 Changed 6 years ago by Frédéric Chapoton

ping ?

comment:12 Changed 6 years ago by Dima Pasechnik

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...

comment:13 Changed 6 years ago by Frédéric Chapoton

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.

comment:14 Changed 6 years ago by Dima Pasechnik

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...

Last edited 6 years ago by Dima Pasechnik (previous) (diff)

comment:15 Changed 6 years ago by Frédéric Chapoton

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.

comment:16 in reply to:  15 Changed 6 years ago by Dima Pasechnik

Replying to chapoton:

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.

comment:17 Changed 6 years ago by Frédéric Chapoton

Thanks for your help.

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

Last edited 6 years ago by Frédéric Chapoton (previous) (diff)

comment:18 Changed 6 years ago by Dima Pasechnik

Reviewers: Dima Pasechnik
Status: needs_reviewpositive_review

Happy NY!

comment:19 Changed 6 years ago by Volker Braun

Branch: u/chapoton/21951e3da5b2a6996fb16143002e8053ff205cc0fd81e
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.