File: /projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/categories/semigroups.py
Source:
def cayley_graph(self, side="right", simple=False, elements = None, generators = None, connecting_set = None):
r"""
Return the Cayley graph for this finite semigroup.
INPUT:
- ``side`` -- "left", "right", or "twosided":
the side on which the generators act (default:"right")
- ``simple`` -- boolean (default:False):
if True, returns a simple graph (no loops, no labels,
no multiple edges)
- ``generators`` -- a list, tuple, or family of elements
of ``self`` (default: ``self.semigroup_generators()``)
- ``connecting_set`` -- alias for ``generators``; deprecated
- ``elements`` -- a list (or iterable) of elements of ``self``
OUTPUT:
- :class:`DiGraph`
EXAMPLES:
We start with the (right) Cayley graphs of some classical groups::
sage: D4 = DihedralGroup(4); D4
Dihedral group of order 8 as a permutation group
sage: G = D4.cayley_graph()
sage: show(G, color_by_label=True, edge_labels=True)
sage: A5 = AlternatingGroup(5); A5
Alternating group of order 5!/2 as a permutation group
sage: G = A5.cayley_graph()
sage: G.show3d(color_by_label=True, edge_size=0.01, edge_size2=0.02, vertex_size=0.03)
sage: G.show3d(vertex_size=0.03, edge_size=0.01, edge_size2=0.02, vertex_colors={(1,1,1):G.vertices()}, bgcolor=(0,0,0), color_by_label=True, xres=700, yres=700, iterations=200) # long time (less than a minute)
sage: G.num_edges()
120
sage: w = WeylGroup(['A',3])
sage: d = w.cayley_graph(); d
Digraph on 24 vertices
sage: d.show3d(color_by_label=True, edge_size=0.01, vertex_size=0.03)
Alternative generators may be specified::
sage: G = A5.cayley_graph(generators=[A5.gens()[0]])
sage: G.num_edges()
60
sage: g=PermutationGroup([(i+1,j+1) for i in range(5) for j in range(5) if j!=i])
sage: g.cayley_graph(generators=[(1,2),(2,3)])
Digraph on 120 vertices
If ``elements`` is specified, then only the subgraph
induced and those elements is returned. Here we use it to
display the Cayley graph of the free monoid truncated on
the elements of length at most 3::
sage: M = Monoids().example(); M
An example of a monoid: the free monoid generated by ('a', 'b', 'c', 'd')
sage: elements = [ M.prod(w) for w in sum((list(Words(M.semigroup_generators(),k)) for k in range(4)),[]) ]
sage: G = M.cayley_graph(elements = elements)
sage: G.num_verts(), G.num_edges()
(85, 84)
sage: G.show3d(color_by_label=True, edge_size=0.001, vertex_size=0.01)
We now illustrate the ``side`` and ``simple`` options on
a semigroup::
sage: S = FiniteSemigroups().example(alphabet=('a','b'))
sage: g = S.cayley_graph(simple=True)
sage: g.vertices()
['a', 'ab', 'b', 'ba']
sage: g.edges()
[('a', 'ab', None), ('b', 'ba', None)]
::
sage: g = S.cayley_graph(side="left", simple=True)
sage: g.vertices()
['a', 'ab', 'b', 'ba']
sage: g.edges()
[('a', 'ba', None), ('ab', 'ba', None), ('b', 'ab', None),
('ba', 'ab', None)]
::
sage: g = S.cayley_graph(side="twosided", simple=True)
sage: g.vertices()
['a', 'ab', 'b', 'ba']
sage: g.edges()
[('a', 'ab', None), ('a', 'ba', None), ('ab', 'ba', None),
('b', 'ab', None), ('b', 'ba', None), ('ba', 'ab', None)]
::
sage: g = S.cayley_graph(side="twosided")
sage: g.vertices()
['a', 'ab', 'b', 'ba']
sage: g.edges()
[('a', 'a', (0, 'left')), ('a', 'a', (0, 'right')), ('a', 'ab', (1, 'right')), ('a', 'ba', (1, 'left')), ('ab', 'ab', (0, 'left')), ('ab', 'ab', (0, 'right')), ('ab', 'ab', (1, 'right')), ('ab', 'ba', (1, 'left')), ('b', 'ab', (0, 'left')), ('b', 'b', (1, 'left')), ('b', 'b', (1, 'right')), ('b', 'ba', (0, 'right')), ('ba', 'ab', (0, 'left')), ('ba', 'ba', (0, 'right')), ('ba', 'ba', (1, 'left')), ('ba', 'ba', (1, 'right'))]
::
sage: s1 = SymmetricGroup(1); s = s1.cayley_graph(); s.vertices()
[()]
TESTS::
sage: SymmetricGroup(2).cayley_graph(side="both")
Traceback (most recent call last):
...
ValueError: option 'side' must be 'left', 'right' or 'twosided'
.. TODO::
- Add more options for constructing subgraphs of the
Cayley graph, handling the standard use cases when
exploring large/infinite semigroups (a predicate,
generators of an ideal, a maximal length in term of the
generators)
- Specify good default layout/plot/latex options in the graph
- Generalize to combinatorial modules with module generators / operators
AUTHORS:
- Bobby Moretti (2007-08-10)
- Robert Miller (2008-05-01): editing
- Nicolas M. Thiery (2008-12): extension to semigroups,
``side``, ``simple``, and ``elements`` options, ...
"""
from sage.graphs.digraph import DiGraph
from monoids import Monoids
from groups import Groups
if not side in ["left", "right", "twosided"]:
raise ValueError("option 'side' must be 'left', 'right' or 'twosided'")
if elements is None:
assert self.is_finite(), "elements should be specified for infinite semigroups"
elements = self
else:
elements = set(elements)
if simple or self in Groups():
result = DiGraph()
else:
result = DiGraph(multiedges = True, loops = True)
result.add_vertices(elements)
if connecting_set is not None:
generators = connecting_set
if generators is None:
if self in Monoids and hasattr(self, "monoid_generators"):
generators = self.monoid_generators()
else:
generators = self.semigroup_generators()
if isinstance(generators, (list, tuple)):
generators = dict((self(g), self(g)) for g in generators)
left = (side == "left" or side == "twosided")
right = (side == "right" or side == "twosided")
def add_edge(source, target, label, side_label):
"""
Skips edges whose targets are not in elements
Return an appropriate edge given the options
"""
if (elements is not self and
target not in elements):
return
if simple:
result.add_edge([source, target])
elif side == "twosided":
result.add_edge([source, target, (label, side_label)])
else:
result.add_edge([source, target, label])
for x in elements:
for i in generators.keys():
if left:
add_edge(x, generators[i]*x, i, "left" )
if right:
add_edge(x, x*generators[i], i, "right")
return result
