#18239: Constructing Cayley graphs is slow
-------------------------+-------------------------------------------------
Reporter: azi | Owner:
Type: | Status: needs_review
defect | Milestone: sage-6.7
Priority: major | Resolution:
Component: group | Merged in:
theory | Reviewers:
Keywords: | Work issues:
Authors: | Commit:
Vincent Delecroix | 7dbf867236b6c9c88acd25009fdf8453571b9d75
Report Upstream: N/A | Stopgaps:
Branch: |
public/18239 |
Dependencies: |
-------------------------+-------------------------------------------------
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
>
> {{{
> 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.
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=[p, q, p.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.
With the branch applied
{{{
sage: %time G = A.cayley_graph(generators=[p,q,p.inverse()], simple=True)
CPU times: user 728 ms, sys: 0 ns, total: 728 ms
Wall time: 726 ms
}}}
--
Comment (by vdelecroix):
In the description ticket I assumed that `x` meant `p` and `g` meant `q`.
If I did wrong, please modify.
--
Ticket URL: <http://trac.sagemath.org/ticket/18239#comment:14>
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.
