Opened 7 years ago

Closed 7 years ago

#12942 closed enhancement (fixed)

Balaban's 10-Cage

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.1
Component: graph theory Keywords:
Cc: wdj, dimpase Merged in: sage-5.1.beta1
Authors: Nathann Cohen Reviewers: Keshav Kini
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

This patch adds one graph constructor and an interesting embedding for it. This one took a loooooooottt of sweat, but I'm learning a lot of tricks to create new embeddings :-)

Oh, and the patch also adds a helper method which I plan on using very often for other patches : it sets the position of some points so that they are on a circle of given center and radius.. This will *really* be useful for many embeddings :-)

Nathann

Attachments (2)

trac_12942.patch (5.7 KB) - added by ncohen 7 years ago.
trac_12942.reviewer.patch (5.0 KB) - added by kini 7 years ago.
apply to $SAGE_ROOT/devel/sage

Download all attachments as: .zip

Change History (21)

comment:1 Changed 7 years ago by ncohen

  • Status changed from new to needs_review

comment:2 follow-up: Changed 7 years ago by kini

Oh, thanks for reminding me to rebase my old Balaban 11-cage patch :)

comment:3 in reply to: ↑ 2 Changed 7 years ago by ncohen

Oh, thanks for reminding me to rebase my old Balaban 11-cage patch :)

Arg O_o

You wrote it already ? :-D

Well, anyway I learnt to fight with automorphism groups a bit.. I'm giving the 11cage a try right now :-D

Nathann

comment:4 follow-up: Changed 7 years ago by kini

Yup... as you can see, the patch looks very mysterious :P http://boxen.math.washington.edu/home/keshav/files/trac_9136-balaban-11-cage.patch

I think I will use your helper function instead, and maybe extend it so that it doesn't only do evenly spaced points around the circle... (maybe allow for some None elements of the list of points, for example)

comment:5 Changed 7 years ago by kini

That patch applies to Sage 4.7.1.rc1 by the way :D

comment:6 in reply to: ↑ 4 Changed 7 years ago by ncohen

Yup... as you can see, the patch looks very mysterious :P

I see :-D

by the way : you can actually space points differently with this patch. That's more or less what I did in the embedding : you create two cicles with different shifts :-)

Well, perhaps the _circle thing will have to be modified too..

And GOD, the 11cage is really something O_o

Nathann

comment:7 Changed 7 years ago by kini

No, I mean, to put points on a circle but not evenly spaced. Maybe three points clustered near the top of the circle, three near the bottom, three near the left, and three near the right, for example. So then you would pass [v1, v2, v3, None, None, None, v4, v5, v6, None, None, None, v7, v8, v9, None, None, None, v10, v11, v12, None, None, None] with shift=-1.5, or something like that.

comment:8 Changed 7 years ago by ncohen

Well, this you can do ! The points v1, v4, v7, and v10 are evenly spaced ! And the same for v2, v5, v8, v11. That's what happens to the point from the "inner layer" in my patch's embedding. Some vertices are "clones" of each other, and I made them closer so that this appears in the drawing :-)

Nathann

comment:9 Changed 7 years ago by kini

Err, you're right :) But the less symmetry there is, the more calls you will need to that function... then again, if there's so little symmetry, why even use a circular embedding? :P

comment:10 Changed 7 years ago by kini

I'll test and review this patch once I finish doctesting my rebase of #12533.

Changed 7 years ago by ncohen

Changed 7 years ago by kini

apply to $SAGE_ROOT/devel/sage

comment:11 Changed 7 years ago by kini

Passes all doctests! I added a reviewer patch which wraps docstrings to 72 columns per PEP 8, and makes a few minor changes. I also changed the name of the graph to "the Balaban 10-cage" instead of "Balaban's 10-cage" (because of how it's named on Wikipedia). Is there a reason to have it as "Balaban's 10-cage"?

comment:12 Changed 7 years ago by kini

Hey patchbot: apply trac_12942.patch and then trac_12942.reviewer.patch .

(Will that work?)

comment:13 Changed 7 years ago by kini

ncohen: if you agree to the name change, I'll give this positive review, otherwise I'll revert the name change and then give it positive review. Thanks for making this helper function in particular! :)

comment:14 Changed 7 years ago by ncohen

No prob with this at all ! But the max width for the lines is 80, so mine were not too long :-)

Good to go !

Nathann

comment:15 follow-up: Changed 7 years ago by kini

  • Status changed from needs_review to positive_review

Well, PEP 8 prescribes 79 columns for code and recommends 72 for documentation... http://www.python.org/dev/peps/pep-0008/#maximum-line-length And we supposedly follow PEP 8 in Sage. So that's why I wrapped the docstrings to 72.

Positive review!

comment:16 in reply to: ↑ 15 Changed 7 years ago by ncohen

Well, PEP 8 prescribes 79 columns for code and recommends 72 for documentation...

O_O

My GOD. You will have to become a lawyer to send Sage patches very soon :-D

They're mad guys O_O

Nathann

comment:17 Changed 7 years ago by jdemeyer

  • Authors set to Nathann Cohen
  • Reviewers set to Keshav Kini

comment:18 Changed 7 years ago by kini

Nathann: Not to send Sage patches, only to review them :P

comment:19 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.1.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.