#18239: Constructing Cayley graphs is slow
----------------------------+----------------------------
Reporter: azi | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-6.7
Component: group theory | Keywords:
Merged in: | Authors:
Reviewers: | Report Upstream: N/A
Work issues: | Branch:
Commit: | Dependencies:
Stopgaps: |
----------------------------+----------------------------
I am leaving this here as a future task that needs to be addressed.
Hopefully someone can do it instead of me :-)
Constructing Cayley graphs is''' awfully''' slow, compared to what we can
get with GAP. Example
Let $x,g$ be two permutations
{{{
sage: x,g
((2,9)(7,28)(10,32)(11,33)(12,34)(13,47)(14,36)(18,58)(22,66)(26,73)(30,77)(35,45)(37,81)(38,82)(39,98)(40,84)(41,85)(42,86)(43,106)(44,88)(46,89)(48,112)(49,91)(52,111)(56,125)(60,129)(64,136)(68,140)(71,144)(75,148)(79,152)(83,96)(87,104)(90,109)(92,156)(93,157)(94,177)(95,159)(97,160)(99,182)(100,162)(101,163)(102,187)(103,165)(105,166)(107,193)(108,168)(110,169)(113,199)(114,171)(117,192)(120,198)(123,211)(127,215)(131,219)(134,223)(138,227)(142,231)(146,235)(150,239)(154,243)(158,175)(161,180)(164,185)(167,190)(170,196)(172,246)(173,266)(174,248)(176,249)(178,271)(179,251)(181,252)(183,276)(184,254)(186,255)(188,282)(189,257)(191,258)(194,288)(195,260)(197,261)(200,294)(201,263)(203,281)(206,287)(209,293)(213,305)(217,309)(221,313)(225,316)(229,320)(233,324)(237,327)(241,331)(245,334)(247,264)(250,269)(253,274)(256,279)(259,285)(262,291)(265,335)(267,354)(268,337)(270,338)(272,359)(273,340)(275,341)(277,364)(278,343)(280,344)(283,369)(284,346)(286,347)(289,375)(290,349)(292,350)(295,379)(297,368)(300,374)(303,378)(307,388)(311,392)(315,395)(318,396)(322,400)(326,403)(329,404)(333,407)(336,352)(339,357)(342,362)(345,366)(348,372)(351,377)(353,408)(355,423)(356,410)(358,411)(360,428)(361,413)(363,414)(365,431)(367,416)(370,435)(371,418)(373,419)(376,439)(381,434)(384,438)(387,440)(390,446)(394,449)(398,450)(402,453)(406,454)(409,421)(412,426)(415,430)(417,432)(420,437)(422,455)(424,464)(425,457)(427,458)(429,467)(433,460)(436,470)(442,469)(445,471)(448,474)(452,475)(456,462)(459,466)(461,468)(463,476)(465,479)(473,480)(477,478),
(1,107,306,184,333,101,19,272,328,201,56,265,31,289,447,10,75,280,132,429,70,14,217,422,155,43,212,100,241,433,3,178,236,114,394,172,8,194,389,278,26,186,61,360,405,2,127,353,80,376,122,40,150,367,222,94,145,49,311,463)(4,167,380,254,402,163,53,339,397,263,117,335,69,348,472,32,138,344,210,459,133,36,300,455,234,87,296,162,322,460,15,250,317,171,445,246,23,259,441,343,64,255,121,412,451,9,206,408,143,420,202,84,229,416,304,158,224,91,384,476)(5,188,130,273,406,12,57,355,153,290,123,97,76,370,314,37,146,110,218,465,6,44,307,275,242,102,59,179,329,292,16,267,78,195,448,38,27,283,220,361,71,46,128,424,244,11,213,181,151,436,17,95,237,197,312,173,29,108,390,363)(7,105,214,277,332,41,60,270,238,295,55,174,79,286,391,39,74,189,221,427,24,48,216,356,245,42,124,183,240,371,18,176,147,200,393,92,30,191,308,365,25,103,131,358,330,13,126,268,154,373,54,99,149,284,315,93,72,113,310,425)(20,256,208,340,452,34,118,409,232,349,203,160,139,417,386,81,225,169,301,477,21,88,381,341,323,164,119,251,398,350,50,336,141,260,473,82,65,345,302,413,134,89,207,456,325,33,297,252,230,461,51,159,318,261,385,247,67,168,442,414)(22,166,298,342,401,85,120,338,319,351,116,248,142,347,443,83,137,257,303,458,62,90,299,410,326,86,204,253,321,418,52,249,226,262,444,156,68,258,382,415,63,165,209,411,399,35,205,337,233,419,115,161,228,346,387,157,135,170,383,457)(28,190,388,362,407,185,129,357,404,377,125,352,152,372,474,96,148,366,313,466,144,109,309,462,334,104,305,274,331,468,58,269,327,291,449,264,77,285,446,430,73,279,219,426,454,45,215,421,243,437,211,180,239,432,395,175,235,196,392,478)(47,287,423,324,439,281,182,320,435,440,177,316,199,438,479,66,193,434,364,453,187,198,359,450,379,192,354,231,375,480,98,227,369,378,467,223,112,374,464,403,106,368,276,400,470,111,271,396,294,471,266,140,288,469,431,136,282,293,428,475))
}}}
The following code
{{{
G = A.cayley_graph(generators=[g,x, g.inverse()], simple=True)
}}}
takes '''26''' seconds to finish and it returns a DiGraph that still to
be converted to a Graph.
In order to obtain a list of edges of the above Cayley Graph one can also
do
{{{
gout = gap('UndirectedEdges(CayleyGraph((Group(' + str(x) + ',' + str(g)+
' )), [' + str(g) + ',' + str(x) + ',' + str(g.inverse()) + ']));')
ast.literal_eval(str(gout))
}}}
which takes '''0.4s'''.
I need to do this for roughly 300k such permutation groups and it makes a
big difference which implementation we use.
Note that the last example assumed ast is imported and also that
{{{
gap.LoadPackage('"grape"')
}}}
was loaded.
--
Ticket URL: <http://trac.sagemath.org/ticket/18239>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
