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