Sage includes wrappers to many NetworkX commands, written mainly by Emily Kirkman and Robert Miller. The implementation of Cayley graphs was written by Bobby Moretti and Robert Miller.
sage: G = DihedralGroup(5) sage: C = G.cayley_graph(); C Digraph on 10 vertices
As another option to do graph theory in Sage, you may
also load Leonard Soicher's GAP package
GRAPE
(http://www.gap-system.org/Packages/grape.html),
which in turn calls the C programs in Brendan McKay's
nauty
(http://cs.anu.edu.au/people/bdm/nauty/).
These packages require a UNIX environment to be installed
(such as Linux or Cygwin - see the GRAPE readme file
http://www.maths.qmul.ac.uk/~leonard/grape/READMEfile for details).
To install GRAPE in Sage, see §16.8.
sage: print gap.eval('LoadPackage("grape")') # need optional gap packages true sage: print gap.eval("C := CayleyGraph(SymmetricGroup(4),[(1,2),(2,3),(3,4)])") # optional gap package rec( isGraph := true, order := 24, group := Group([ (1,10,17,19)(2,9,18,20)(3,12,14,21)(4,11,13,22)(5,7,16, 23)(6,8,15,24), (1,7)(2,8)(3,9)(4,10)(5,11)(6,12)(13,15)(14,16)(17, 18)(19,21)(20,22)(23,24) ]), schreierVector := [ -1, 1, 1, 2, 2, 1, 2, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2 ], adjacencies := [ [ 2, 3, 7 ] ], representatives := [ 1 ], names := [ (), (3,4), (2,3), (2,3,4), (2,4,3), (2,4), (1,2), (1,2)(3,4), (1,2,3), (1,2,3,4), (1,2,4,3), (1,2,4), (1,3,2), (1,3,4,2), (1,3), (1,3,4), (1,3)(2,4), (1,3,2,4), (1,4,3,2), (1,4,2), (1,4,3), (1,4), (1,4,2,3), (1,4)(2,3) ], isSimple := true ) sage: print gap.eval("Girth(C)") # optional gap package 4 sage: print gap.eval("Diameter(C)") # optional gap package 6 sage: print gap.eval("AutGroupGraph(C)") # optional gap package (uses nauty) Group([ (2,7)(4,13)(5,9)(6,15)(10,19)(12,21)(16,20)(18,23), (1,2)(3,5)(4,6)(7,8)(9,11)(10,12)(13,19)(14,20)(15,21)(16,22)(17,23)(18,24), (1,3)(2,4)(5,6)(7,13)(8,14)(9,15)(10,16)(11,17)(12,18)(19,20)(21,23)(22,24) ])
The command AutGroupGraph
uses the 2.2 version of nauty
.
Here is a more Pythonic version (thanks to Jack Schmidt for helping with this):
C3 = CyclicPermutationGroup(3)._gap_() C = C3.CayleyGraph(C3.GeneratorsOfGroup()) V = C.Vertices().Elements() E = C.UndirectedEdges() L = [[y[1] for y in [x for x in E if v in x] if y[1]!=v]+[y[2] for y in [x for x in E if v in x] if y[2]!=v] for v in V] d = dict(zip(V,L)) G = Graph(d) show(G.plot())
See About this document... for information on suggesting changes.