Opened 8 years ago

Closed 6 years ago

#11360 closed enhancement (fixed)

The Rubik's Cube group in Sage doesn't support many basic operations for a dumb reason.

Reported by: was Owned by: jason, ncohen, rlm
Priority: minor Milestone: sage-5.12
Component: group theory Keywords:
Cc: Merged in: sage-5.12.beta0
Authors: Travis Scrimshaw Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by tscrim)

We have

sage: G = CubeGroup()
sage: G.order()
Traceback (most recent call last):
...
AttributeError: 'CubeGroup' object has no attribute '_gap_string'
sage: G.sylow_subgroup(3)
Traceback (most recent call last):
...
AttributeError: 'CubeGroup' object has no attribute '_gap_string'

However, these things are all easily computable in Sage:

sage: G2 = PermutationGroup(G.gens())
sage: G2.order()
43252003274489856000
sage: G2.sylow_subgroup(3)
Permutation Group with generators [(24,30,43)(32,48,38), ...

Apply:

Attachments (3)

trac_11360-cubegroup.patch (1.6 KB) - added by wdj 8 years ago.
applies to sage-4.7.1.rc1
trac_11360-cubegroup2.patch (869 bytes) - added by wdj 8 years ago.
apply only this patch to 4.7.1.rc1
trac_11360-cubegroup-ts.patch (36.4 KB) - added by tscrim 6 years ago.

Download all attachments as: .zip

Change History (22)

comment:1 follow-up: Changed 8 years ago by robertwb

This could be easily fixed by implementing CubeGroup._gap_init_(). Generically, one could implement this in terms of gens() if it's not already there.

Changed 8 years ago by wdj

applies to sage-4.7.1.rc1

comment:2 in reply to: ↑ 1 Changed 8 years ago by wdj

  • Status changed from new to needs_review

Replying to robertwb:

This could be easily fixed by implementing CubeGroup._gap_init_().

Is the attached patch what you had in mind?

Generically, one could implement this in terms of gens() if it's not already there.

comment:3 follow-up: Changed 8 years ago by robertwb

Yes, that works. You should elide the commented-out lines and the "Stored in the self._gap_string attribute" comment is also incorrect and should probably just be omitted.

I'm still curious as to why this is a group and has a ._group attribute, but that's probably for another ticket.

comment:4 Changed 8 years ago by ncohen

  • Status changed from needs_review to needs_work

(as Robert suggested, + cc me :-) )

Nathann

Changed 8 years ago by wdj

apply only this patch to 4.7.1.rc1

comment:5 in reply to: ↑ 3 Changed 8 years ago by wdj

  • Status changed from needs_work to needs_review

Replying to robertwb:

Yes, that works. You should elide the commented-out lines and the "Stored in the self._gap_string attribute" comment is also incorrect and should probably just be omitted.

Done. See attached.

I'm still curious as to why this is a group and has a ._group attribute, but that's probably for another ticket.

comment:6 Changed 8 years ago by robertwb

Apply both trac_11360-cubegroup.patch and trac_11360-cubegroup2.patch , right?

comment:7 Changed 8 years ago by ncohen

  • Description modified (diff)
  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

Helloooooo !!!

I guess this patch is more a "group theory" patch than "graph theory", but it is not so complicated anyway. And I checked what I needed to know on [1] :-)

Positive review to this patch !

By the way, I wondered about something. A colleague of mine is working on graph automorphisms, and it seems our library on this aspect is pretty poor. Can we do anything else than just "forward instructions to GAP" ? It seems Sage's a long way to be a good alternative to their code.. Perhaps it is not meant to be, however... I'd be glad to have an layman's opinion on that though :-)

Nathann

[1] http://www.gap-system.org/Doc/Examples/rubik.html

comment:8 Changed 8 years ago by ncohen

Hmmmmmmm O_o

I just checked the definition of "layman", just to be sure, and it looks like it is not exactly what I meant. What I meant was "I would be glad to have the opinion of somebody actually working with both Sage and GAP".

Sorry if my last sentence could be read as insulting, it really was not the intent ^^;

Nathann

comment:9 Changed 8 years ago by ncohen

  • Status changed from positive_review to needs_work

Arggggggggg !!! Sorry, this patch does not pass the tests O_o

sage -t  "devel/sage-2/sage/groups/perm_gps/cubegroup.py"   
**********************************************************************
File "/home/ncohen/.Sage/devel/sage-2/sage/groups/perm_gps/cubegroup.py", line 491:
    sage: G._gap_init_()
Expected:
     'Group([(1,14,48,27)(2,12,47,29)(3,9,46,32)(33,35,40,38)(34,37,39,36), (14,22,30,38)(15,23,31,39)(16,24,32,40)(41,43,48,46)(42,45,47,44), (6,25,43,16)(7,28,42,13)(8,30,41,11)(17,19,24,22)(18,21,23,20), (1,17,41,40)(4,20,44,37)(6,22,46,35)(9,11,16,14)(10,13,15,12), (3,38,43,19)(5,36,45,21)(8,33,48,24)(25,27,32,30)(26,29,31,28), (1,3,8,6)(2,5,7,4)(9,33,25,17)(10,34,26,18)(11,35,27,19)])'
Got:
    'Group([PermList([14, 12, 9, 4, 5, 6, 7, 8, 46, 10, 11, 47, 13, 48, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 1, 28, 2, 30, 31, 3, 35, 37, 40, 34, 39, 33, 36, 38, 41, 42, 43, 44, 45, 32, 29, 27]), PermList([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 22, 23, 24, 17, 18, 19, 20, 21, 30, 31, 32, 25, 26, 27, 28, 29, 38, 39, 40, 33, 34, 35, 36, 37, 14, 15, 16, 43, 45, 48, 42, 47, 41, 44, 46]), PermList([1, 2, 3, 4, 5, 25, 28, 30, 9, 10, 8, 12, 7, 14, 15, 6, 19, 21, 24, 18, 23, 17, 20, 22, 43, 26, 27, 42, 29, 41, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 11, 13, 16, 44, 45, 46, 47, 48]), PermList([17, 2, 3, 20, 5, 22, 7, 8, 11, 13, 16, 10, 15, 9, 12, 14, 41, 18, 19, 44, 21, 46, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 6, 36, 4, 38, 39, 1, 40, 42, 43, 37, 45, 35, 47, 48]), PermList([1, 2, 38, 4, 36, 6, 7, 33, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 3, 20, 5, 22, 23, 8, 27, 29, 32, 26, 31, 25, 28, 30, 48, 34, 35, 45, 37, 43, 39, 40, 41, 42, 19, 44, 21, 46, 47, 24]), PermList([3, 5, 8, 2, 7, 1, 4, 6, 33, 34, 35, 12, 13, 14, 15, 16, 9, 10, 11, 20, 21, 22, 23, 24, 17, 18, 19, 28, 29, 30, 31, 32, 25, 26, 27, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48])])'
**********************************************************************

Nathann

comment:10 Changed 6 years ago by tscrim

  • Authors set to Travis Scrimshaw
  • Description modified (diff)
  • Status changed from needs_work to needs_review

Here's a new version of the patch which fixes the problem by making CubeGroup properly use OOP by calling its superclass's __init__ (and subsequently got rid of the _group attribute). While I was at it, I brought the file up to full coverage.

For patchbot:

Apply: trac_11360-cubegroup-ts.patch

comment:11 Changed 6 years ago by ncohen

  • Component changed from graph theory to group theory

comment:12 Changed 6 years ago by ncohen

  • Status changed from needs_review to needs_work

Helloooooooooo !!

Well, this is very far from being a code I fully understand, but as the modifications are superficial I just had to check that "if what was there before made sense, then what this patch changes makes sense too" :-D

It looks good, though I have two comments :

  • Why don't the __str__ and __repr__ method return the same string ? O_o
  • You added a check argument to parse which is not documented.

Nathann

comment:13 Changed 6 years ago by tscrim

Updated patch addressing your comments. The __str__ and __repr__ methods were like that before I got there, and it is perfectly valid (if slightly wonky) to do so in python. However I think this is worthwhile to change. I documented the parse argument, which is simply passed to the __call__; I'm not in favor of documenting things like this since it could render the code unsafe and its telling the (average) user can set this, rather than those needing every drop of speed. Anyways, I added the doc since it's not a big deal here.

For patchbot:

Apply: trac_11360-cubegroup-ts.patch

comment:14 Changed 6 years ago by ncohen

  • Status changed from needs_work to positive_review

Coooooooool ! Then let it go :-)

Nathann

comment:15 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12
  • Status changed from positive_review to needs_work
sage -t --long devel/sage/sage/groups/perm_gps/cubegroup.py
**********************************************************************
File "devel/sage/sage/groups/perm_gps/cubegroup.py", line 1067, in sage.groups.perm_gps.cubegroup.CubeGroup.solve
Failed example:
    rubik.solve(state, algorithm='gap')       # long time
Exception raised:
    Traceback (most recent call last):
      File "/mazur/release/merger/sage-5.11.rc0/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 486, in _run
        self.execute(example, compiled, test.globs)
      File "/mazur/release/merger/sage-5.11.rc0/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 845, in execute
        exec compiled in globs
      File "<doctest sage.groups.perm_gps.cubegroup.CubeGroup.solve[4]>", line 1, in <module>
        rubik.solve(state, algorithm='gap')       # long time
      File "/mazur/release/merger/sage-5.11.rc0/local/lib/python2.7/site-packages/sage/groups/perm_gps/cubegroup.py", line 1086, in solve
        hom = G._gap_().EpimorphismFromFreeGroup()
    NameError: global name 'G' is not defined
**********************************************************************

Changed 6 years ago by tscrim

comment:16 Changed 6 years ago by tscrim

  • Status changed from needs_work to needs_review

Fixed. Nathann, I just changed the offending line 1086, could you double-check to make sure it passes the long doctest? Thanks.

For patchbot:

Apply: trac_11360-cubegroup-ts.patch

comment:17 Changed 6 years ago by ncohen

  • Status changed from needs_review to positive_review

All long tests pass in the group folder. Sorry for that :-/

Nathann

comment:18 Changed 6 years ago by tscrim

It's partly my fault in that I forgot to do the long tests on the file. Thanks.

comment:19 Changed 6 years ago by jdemeyer

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