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: |
Description (last modified by )
using an algorithm of Schaeffer (bijection with blossoming trees)
Change History (19)
comment:1 Changed 6 years ago by
Branch: | → u/chapoton/21951 |
---|---|
Commit: | → 5173db430c60de75758f55efab1c6d21ba2a9135 |
comment:2 Changed 6 years ago by
Status: | new → needs_review |
---|
comment:3 Changed 6 years ago by
Cc: | Kevin Dilks added |
---|
comment:4 Changed 6 years ago by
Cc: | Dima Pasechnik Pablo Portilla David Coudert added |
---|---|
Description: | modified (diff) |
looking for a referee...
comment:5 Changed 6 years ago by
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
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
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
Commit: | 5173db430c60de75758f55efab1c6d21ba2a9135 → e3da5b2a6996fb16143002e8053ff205cc0fd81e |
---|
comment:9 follow-up: 10 Changed 6 years ago by
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.
comment:10 Changed 6 years ago by
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:12 Changed 6 years ago by
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
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
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...
comment:15 follow-up: 16 Changed 6 years ago by
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 Changed 6 years ago by
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
Thanks for your help.
As I have already explained in the doc, the distribution is uniform.
comment:18 Changed 6 years ago by
Reviewers: | → Dima Pasechnik |
---|---|
Status: | needs_review → positive_review |
Happy NY!
comment:19 Changed 6 years ago by
Branch: | u/chapoton/21951 → e3da5b2a6996fb16143002e8053ff205cc0fd81e |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
New commits:
implement a generator for random bicubic planar graphs (rooted maps)