Opened 5 years ago

Closed 5 years ago

#21951 closed enhancement (fixed)

implement random planar bicubic graphs in a bijective way

Reported by: chapoton Owned by:
Priority: major Milestone: sage-7.5
Component: graph theory Keywords:
Cc: kdilks, dimpase, pportilla, dcoudert 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 chapoton)

using an algorithm of Schaeffer (bijection with blossoming trees)

Change History (19)

comment:1 Changed 5 years ago by chapoton

  • Branch set to u/chapoton/21951
  • Commit set to 5173db430c60de75758f55efab1c6d21ba2a9135

New commits:

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

comment:2 Changed 5 years ago by chapoton

  • Status changed from new to needs_review

comment:3 Changed 5 years ago by kdilks

  • Cc kdilks added

comment:4 Changed 5 years ago by chapoton

  • Cc dimpase pportilla dcoudert added
  • Description modified (diff)

looking for a referee...

comment:5 Changed 5 years ago by dimpase

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 5 years ago by dcoudert

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

comment:7 Changed 5 years ago by dimpase

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 5 years ago by git

  • Commit changed from 5173db430c60de75758f55efab1c6d21ba2a9135 to e3da5b2a6996fb16143002e8053ff205cc0fd81e

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 follow-up: Changed 5 years ago by 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 ossible outputs is given by Tutte's formula in A257.

Version 0, edited 5 years ago by chapoton (next)

comment:10 in reply to: ↑ 9 Changed 5 years ago by dimpase

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 5 years ago by chapoton

ping ?

comment:12 Changed 5 years ago by dimpase

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 5 years ago by 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 5 years ago by dimpase

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 5 years ago by dimpase (previous) (diff)

comment:15 follow-up: Changed 5 years ago by 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 5 years ago by dimpase

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 5 years ago by chapoton

Thanks for your help.

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

Last edited 5 years ago by chapoton (previous) (diff)

comment:18 Changed 5 years ago by dimpase

  • Reviewers set to Dima Pasechnik
  • Status changed from needs_review to positive_review

Happy NY!

comment:19 Changed 5 years ago by vbraun

  • Branch changed from u/chapoton/21951 to e3da5b2a6996fb16143002e8053ff205cc0fd81e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.