#18239: Constructing Cayley graphs is slow
--------------------------------+------------------------
Reporter: azi | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-6.7
Component: group theory | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
--------------------------------+------------------------
Description changed by ncohen:
Old description:
> Computing the Cayley graph of a group and generator set is extremely slow
> in Sage. The solution is to use GRAPE directly.
>
> As an 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.
New description:
Computing the Cayley graph of a group and generator set is extremely slow
in Sage. The solution is to use GRAPE directly.
As an example
Let x,g be two permutations
{{{
p=((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))
q=((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),)
A = PermutationGroup([p,q])
p,q = A(p),A(q)
}}}
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#comment:11>
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.
