Coverage for local/lib/python2.7/site-packages/sage/combinat/yang_baxter

[((1, 0, 2, 1, 0), (1, 2, 0, 1, 0), Swap-if-increasing at position 1), ((1, 2, 0, 1, 0), (1, 2, 1, 0, 0), Swap-if-increasing at position 2), ((1, 2, 0, 1, 0), (2, 1, 0, 1, 0), Swap-if-increasing at position 0), ((2, 1, 0, 1, 0), (2, 1, 1, 0, 0), Swap-if-increasing at position 2)]

"""

digraph = self._digraph

seen = {}

queue = [self._root]

seen[self._root] = True

while queue:

u = queue.pop()

for w in digraph.neighbor_out_iterator(u):

if w not in seen:

seen[w] = True

queue.append(w)

yield (u,w,digraph.edge_label(u,w))

def root(self):

r"""

Returns the root vertex of ``self``.

If ``self`` is the Yang-Baxter graph of the partition

`[p_1,p_2,\dots,p_k]`, then this is the vertex

`(p_k-1,p_k-2,\dots,0,\dots,p_1-1,p_1-2,\dots,0)`.

EXAMPLES::

sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator

sage: ops = [SwapIncreasingOperator(i) for i in range(4)]

sage: Y = YangBaxterGraph(root=(1,0,2,1,0), operators=ops)

sage: Y.root()

(1, 0, 2, 1, 0)

sage: Y = YangBaxterGraph(root=(0,1,0,2,1,0), operators=ops)

sage: Y.root()

(0, 1, 0, 2, 1, 0)

sage: Y = YangBaxterGraph(root=(1,0,3,2,1,0), operators=ops)

sage: Y.root()

(1, 0, 3, 2, 1, 0)

sage: Y = YangBaxterGraph(partition=[3,2])

sage: Y.root()

(1, 0, 2, 1, 0)

"""

return self._root

def successors(self, v):

r"""

Return the successors of the vertex ``v``.

EXAMPLES::

sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator

sage: ops = [SwapIncreasingOperator(i) for i in range(4)]

sage: Y = YangBaxterGraph(root=(1,0,2,1,0), operators=ops)

sage: Y.successors(Y.root())

[(1, 2, 0, 1, 0)]

sage: Y.successors((1, 2, 0, 1, 0))

[(1, 2, 1, 0, 0), (2, 1, 0, 1, 0)]

"""

return [a for (a,b) in self._successors(v)]

def plot(self, *args, **kwds):

r"""

Plots ``self`` as a digraph.

EXAMPLES::

sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator

sage: ops = [SwapIncreasingOperator(i) for i in range(4)]

sage: Y = YangBaxterGraph(root=(1,0,2,1,0), operators=ops)

sage: Y.plot()

Graphics object consisting of 16 graphics primitives

sage: Y.plot(edge_labels=False)

Graphics object consisting of 11 graphics primitives

"""

if "edge_labels" not in kwds:

kwds["edge_labels"] = True

if "vertex_labels" not in kwds:

kwds["vertex_labels"] = True

return self._digraph.plot(*args, **kwds)

def vertices(self):

r"""

Returns the vertices of ``self``.

EXAMPLES::

sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator

sage: ops = [SwapIncreasingOperator(i) for i in range(3)]

sage: Y = YangBaxterGraph(root=(0,2,1,0), operators=ops)

sage: Y.vertices()

[(2, 0, 1, 0), (2, 1, 0, 0), (0, 2, 1, 0)]

"""

return list(self)

def edges(self):

r"""

Returns the (labelled) edges of ``self``.

EXAMPLES::

sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator

sage: ops = [SwapIncreasingOperator(i) for i in range(3)]

sage: Y = YangBaxterGraph(root=(0,2,1,0), operators=ops)

sage: Y.edges()

[((0, 2, 1, 0), (2, 0, 1, 0), Swap-if-increasing at position 0), ((2, 0, 1, 0), (2, 1, 0, 0), Swap-if-increasing at position 1)]

"""

return self._digraph.edges()

def vertex_relabelling_dict(self, v, relabel_operator):

r"""

Return a dictionary pairing vertices ``u`` of ``self`` with

the object obtained from ``v`` by applying the

``relabel_operator`` along a path from the root to ``u``. Note

that the root is paired with ``v``.

INPUT:

- ``v`` -- an object

- ``relabel_operator`` -- function mapping a vertex and a label to

the image of the vertex

OUTPUT:

- dictionary pairing vertices with the corresponding image of ``v``

EXAMPLES::

sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator

sage: ops = [SwapIncreasingOperator(i) for i in range(3)]

sage: Y = YangBaxterGraph(root=(0,2,1,0), operators=ops)

sage: def relabel_operator(op, u):

....: i = op.position()

....: return u[:i] + u[i:i+2][::-1] + u[i+2:]

sage: Y.vertex_relabelling_dict((1,2,3,4), relabel_operator)

{(0, 2, 1, 0): (1, 2, 3, 4),

(2, 0, 1, 0): (2, 1, 3, 4),

(2, 1, 0, 0): (2, 3, 1, 4)}

"""

relabelling = {self._root:v}

for (u,w,i) in self._edges_in_bfs():

relabelling[w] = relabel_operator(i, relabelling[u])

return relabelling

def relabel_vertices(self, v, relabel_operator, inplace=True):

r"""

Relabel the vertices ``u`` of ``self`` by the object obtained

from ``u`` by applying the ``relabel_operator`` to ``v`` along

a path from ``self.root()`` to ``u``.

Note that the ``self.root()`` is paired with ``v``.

INPUT:

- ``v`` -- tuple, Permutation, CombinatorialObject

- ``inplace`` -- if ``True``, modifies ``self``; otherwise returns a

modified copy of ``self``.

EXAMPLES::

sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator

sage: ops = [SwapIncreasingOperator(i) for i in range(3)]

sage: Y = YangBaxterGraph(root=(0,2,1,0), operators=ops)

sage: def relabel_op(op, u):

....: i = op.position()

....: return u[:i] + u[i:i+2][::-1] + u[i+2:]

sage: d = Y.relabel_vertices((1,2,3,4), relabel_op, inplace=False); d

Yang-Baxter graph with root vertex (1, 2, 3, 4)

sage: Y.vertices()

[(2, 0, 1, 0), (2, 1, 0, 0), (0, 2, 1, 0)]

sage: e = Y.relabel_vertices((1,2,3,4), relabel_op); e

sage: Y.vertices()

[(2, 1, 3, 4), (1, 2, 3, 4), (2, 3, 1, 4)]

"""

from copy import copy

relabelling = self.vertex_relabelling_dict(v, relabel_operator)

Y = self if inplace else copy(self)

Y._root = relabelling[Y._root]

Y._digraph.relabel(relabelling, inplace=True)

if inplace is False:

return Y

def relabel_edges(self, edge_dict, inplace=True):

r"""

Relabel the edges of ``self``.

INPUT:

- ``edge_dict`` -- a dictionary keyed by the (unlabelled) edges.

EXAMPLES::

sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator

sage: ops = [SwapIncreasingOperator(i) for i in range(3)]

sage: Y = YangBaxterGraph(root=(0,2,1,0), operators=ops)

sage: def relabel_op(op, u):

....: i = op.position()

....: return u[:i] + u[i:i+2][::-1] + u[i+2:]

sage: Y.edges()

[((0, 2, 1, 0), (2, 0, 1, 0), Swap-if-increasing at position 0), ((2, 0, 1, 0), (2, 1, 0, 0), Swap-if-increasing at position 1)]

sage: d = {((0,2,1,0),(2,0,1,0)):17, ((2,0,1,0),(2,1,0,0)):27}

sage: Y.relabel_edges(d, inplace=False).edges()

[((0, 2, 1, 0), (2, 0, 1, 0), 17), ((2, 0, 1, 0), (2, 1, 0, 0), 27)]

sage: Y.edges()

[((0, 2, 1, 0), (2, 0, 1, 0), Swap-if-increasing at position 0), ((2, 0, 1, 0), (2, 1, 0, 0), Swap-if-increasing at position 1)]

sage: Y.relabel_edges(d, inplace=True)

sage: Y.edges()

[((0, 2, 1, 0), (2, 0, 1, 0), 17), ((2, 0, 1, 0), (2, 1, 0, 0), 27)]

"""

if inplace:

Y = self

else:

from copy import copy

Y = copy(self)

digraph = Y._digraph

for (u,v,i) in digraph.edges():

digraph.set_edge_label(u,v,edge_dict[u,v])

if not inplace:

return Y

##### Yang-Baxter Graphs defined by a partition ###########################

class YangBaxterGraph_partition(YangBaxterGraph_generic):

def __init__(self, partition):

r"""

A class to model the Yang-Baxter graph of a partition.

The Yang-Baxter graph defined by a partition `[p_1,\dots,p_k]`

is the labelled directed graph with vertex set obtained by

bubble-sorting `(p_k-1,p_k-2,\dots,0,\dots,p_1-1,p_1-2,\dots,0)`;

there is an arrow from `u` to `v` labelled by `i` if `v` is

obtained by swapping the `i`-th and `(i+1)`-th elements of `u`.

.. note::

This is a lazy implementation: the digraph is only computed

when it is needed.

EXAMPLES::

sage: Y = YangBaxterGraph(partition=[3,2,1]); Y

Yang-Baxter graph of [3, 2, 1], with top vertex (0, 1, 0, 2, 1, 0)

sage: loads(dumps(Y)) == Y

True

AUTHORS:

- Franco Saliola (2009-04-23)

"""

self._partition = partition

beta = sorted(self._partition, reverse=True)

root = sum([tuple(range(b)) for b in beta], tuple())[::-1]

operators = [SwapIncreasingOperator(i) for i in range(sum(partition)-1)]

super(YangBaxterGraph_partition, self).__init__(root, operators)

def __repr__(self):

r"""

EXAMPLES::

sage: Y = YangBaxterGraph(partition=[3,2])

sage: Y.__repr__()

'Yang-Baxter graph of [3, 2], with top vertex (1, 0, 2, 1, 0)'

"""

return "Yang-Baxter graph of %s, with top vertex %s" % (self._partition, self._root)

def __copy__(self):

r"""

Returns a copy of ``self``.

EXAMPLES::

sage: Y = YangBaxterGraph(partition=[3,2]); Y

Yang-Baxter graph of [3, 2], with top vertex (1, 0, 2, 1, 0)

sage: B = copy(Y); B

Yang-Baxter graph of [3, 2], with top vertex (1, 0, 2, 1, 0)

sage: Y is B

False

sage: Y == B

True

"""

from copy import copy

Y = self.__class__(self._partition)

Y._digraph = copy(self._digraph)

return Y

@lazy_attribute

def _digraph(self):

r"""

Constructs the underlying digraph and stores the result as an

attribute.

EXAMPLES::

sage: Y = YangBaxterGraph(partition=[2,1])

sage: Y._digraph

Digraph on 2 vertices

sage: Y.edges()

[((0, 1, 0), (1, 0, 0), Swap positions 0 and 1)]

"""

digraph = super(YangBaxterGraph_partition, self)._digraph

for (u,v,op) in digraph.edges():

digraph.set_edge_label(u,v,SwapOperator(op.position()))

return digraph

@lazy_attribute

def _vertex_ordering(self):

r"""

Returns a list of the vertices of ``self``, sorted using

Pythons ``sorted`` method.

EXAMPLES::

sage: Y = YangBaxterGraph(partition=[3,2])

sage: Y._vertex_ordering

[(1, 0, 2, 1, 0), (1, 2, 0, 1, 0), (1, 2, 1, 0, 0), (2, 1, 0, 1, 0), (2, 1, 1, 0, 0)]

"""

return sorted(self._digraph.vertices())

def __iter__(self):

r"""

Iterate over the vertices ``self``.

.. NOTE::

The vertices are first sorted using Python's sorted command.

EXAMPLES::

sage: Y = YangBaxterGraph(partition=[3,2])

sage: list(Y.__iter__())

[(1, 0, 2, 1, 0), (1, 2, 0, 1, 0), (1, 2, 1, 0, 0), (2, 1, 0, 1, 0), (2, 1, 1, 0, 0)]

"""

for v in self._vertex_ordering:

yield v

def _swap_operator(self, operator, u):

r"""

Return the image of ``u`` under ``operator``.

INPUT:

- ``i`` -- positive integer between 1 and len(u)-1, inclusive

- ``u`` -- tuple, list, permutation, CombinatorialObject, ....

EXAMPLES::

sage: Y = YangBaxterGraph(partition=[3,1])

sage: from sage.combinat.yang_baxter_graph import SwapOperator

sage: ops = [SwapOperator(i) for i in range(3)]

sage: [Y._swap_operator(op, (1,2,3,4)) for op in ops]

[(2, 1, 3, 4), (1, 3, 2, 4), (1, 2, 4, 3)]

sage: [Y._swap_operator(op, [4,3,2,1]) for op in ops]

[[3, 4, 2, 1], [4, 2, 3, 1], [4, 3, 1, 2]]

sage: [Y._swap_operator(op, Permutation([1,2,3,4])) for op in ops]

[[2, 1, 3, 4], [1, 3, 2, 4], [1, 2, 4, 3]]

"""

return operator(u)

def vertex_relabelling_dict(self, v):

r"""

Return a dictionary pairing vertices ``u`` of ``self`` with the object

obtained from ``v`` by applying transpositions corresponding to the

edges labels along a path from the root to ``u``.

Note that the root is paired with ``v``.

INPUT:

- ``v`` -- an object

OUTPUT:

- dictionary pairing vertices with the corresponding image of ``v``

EXAMPLES::

sage: Y = YangBaxterGraph(partition=[3,1])

sage: Y.vertex_relabelling_dict((1,2,3,4))

{(0, 2, 1, 0): (1, 2, 3, 4),

(2, 0, 1, 0): (2, 1, 3, 4),

(2, 1, 0, 0): (2, 3, 1, 4)}

sage: Y.vertex_relabelling_dict((4,3,2,1))

{(0, 2, 1, 0): (4, 3, 2, 1),

(2, 0, 1, 0): (3, 4, 2, 1),

(2, 1, 0, 0): (3, 2, 4, 1)}

"""

return super(YangBaxterGraph_partition, self).vertex_relabelling_dict(v, self._swap_operator)

def relabel_vertices(self, v, inplace=True):

r"""

Relabel the vertices of ``self`` with the object obtained from

``v`` by applying the transpositions corresponding to the edge

labels along some path from the root to the vertex.

INPUT:

- ``v`` -- tuple, Permutation, CombinatorialObject

- ``inplace`` -- if ``True``, modifies ``self``; otherwise

returns a modified copy of ``self``.

EXAMPLES::

sage: Y = YangBaxterGraph(partition=[3,1]); Y

Yang-Baxter graph of [3, 1], with top vertex (0, 2, 1, 0)

sage: d = Y.relabel_vertices((1,2,3,4), inplace=False); d

Digraph on 3 vertices

sage: Y.vertices()

[(0, 2, 1, 0), (2, 0, 1, 0), (2, 1, 0, 0)]

sage: e = Y.relabel_vertices((1,2,3,4)); e

sage: Y.vertices()

[(1, 2, 3, 4), (2, 1, 3, 4), (2, 3, 1, 4)]

"""

relabelling = self.vertex_relabelling_dict(v)

if inplace:

Y = self

Y._root = relabelling[Y._root]

Y._digraph.relabel(relabelling, inplace=inplace)

Y._vertex_ordering = sorted(Y._digraph.vertices())

return

else:

from copy import copy

Y = copy(self)

Y._root = relabelling[Y._root]

return Y._digraph.relabel(relabelling, inplace=inplace)

##### Some Yang-Baxter operators ##########################################

class SwapOperator(SageObject):

def __init__(self, i):

r"""

The operator that swaps the items in positions ``i`` and ``i+1``.

EXAMPLES::

sage: from sage.combinat.yang_baxter_graph import SwapOperator

sage: s3 = SwapOperator(3)

sage: s3 == loads(dumps(s3))

True

"""

self._position = i

def __hash__(self):

r"""

TESTS::

sage: from sage.combinat.yang_baxter_graph import SwapOperator

sage: s = [SwapOperator(i) for i in range(3)]

sage: [hash(t) for t in s]

[0, 1, 2]

"""

return hash(self._position)

def __eq__(self, other):

r"""

Compare two swap operators.

The comparison is done by comparing the positions.

EXAMPLES::

sage: from sage.combinat.yang_baxter_graph import SwapOperator

sage: s = [SwapOperator(i) for i in range(3)]

sage: s[0] == s[0]

True

sage: s[1] == s[0]

False

"""

if not isinstance(other, SwapOperator):

return False

return self._position == other._position

def __ne__(self, other):

"""

Check whether ``self`` is not equal to ``other``.

EXAMPLES::

sage: from sage.combinat.yang_baxter_graph import SwapOperator

sage: s = [SwapOperator(i) for i in range(3)]

sage: s[0] != s[0]

False

sage: s[1] != s[0]

True

"""

return not (self == other)

def __repr__(self):

r"""

Representation string.

EXAMPLES::

sage: from sage.combinat.yang_baxter_graph import SwapOperator

sage: s3 = SwapOperator(3)

sage: s3.__repr__()

'Swap positions 3 and 4'

"""

return "Swap positions %s and %s" % (self._position, self._position+1)

def __str__(self):

r"""

A short str representation (used, for example, in labelling edges of

graphs).

EXAMPLES::

sage: from sage.combinat.yang_baxter_graph import SwapOperator

sage: s3 = SwapOperator(3)

sage: s3.__str__()

'3'

"""

return "%s" % self._position

def __call__(self, u):

r"""

Return the object obtained from swapping the items in positions

``i`` and ``i+1`` of ``u``.

EXAMPLES::

sage: from sage.combinat.yang_baxter_graph import SwapOperator

sage: s3 = SwapOperator(3)

sage: s3((1,2,3,4,5))

(1, 2, 3, 5, 4)

sage: s3([1,2,3,4,5])

[1, 2, 3, 5, 4]

"""

i = self._position

if isinstance(u, Permutation):

return Permutation(u[:i] + u[i:i+2][::-1] + u[i+2:])

return type(u)(u[:i] + u[i:i+2][::-1] + u[i+2:])

def position(self):

r"""

``self`` is the operator that swaps positions ``i`` and ``i+1``. This

method returns ``i``.

EXAMPLES::

sage: from sage.combinat.yang_baxter_graph import SwapOperator

sage: s3 = SwapOperator(3)

sage: s3.position()

"""

return self._position

class SwapIncreasingOperator(SwapOperator):

def __repr__(self):

r"""

Representation string.

EXAMPLES::

sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator

sage: s3 = SwapIncreasingOperator(3)

sage: s3.__repr__()

'Swap-if-increasing at position 3'

"""

return "Swap-if-increasing at position %s" % self._position

def __call__(self, u):

r"""

Returns a copy of ``u`` with ``u[i-1]`` and ``u[i]`` swapped if

``u[i-1] > u[i]``; otherwise returns ``u``.

INPUT:

- ``i`` -- positive integer between ``1`` and ``len(u)-1``, inclusive

- ``u`` -- tuple, list, permutation, CombinatorialObject, ....

EXAMPLES::

sage: Y = YangBaxterGraph(partition=[2,2])

sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator

sage: operators = [SwapIncreasingOperator(i) for i in range(3)]

sage: [op((1,2,3,4)) for op in operators]

[(2, 1, 3, 4), (1, 3, 2, 4), (1, 2, 4, 3)]

sage: [op([4,3,2,1]) for op in operators]

[[4, 3, 2, 1], [4, 3, 2, 1], [4, 3, 2, 1]]

sage: [op(Permutation([1,3,2,4])) for op in operators]

[[3, 1, 2, 4], [1, 3, 2, 4], [1, 3, 4, 2]]

"""

i = self._position

j = i+1

if u[i] < u[j]:

v = list(u)

(v[j], v[i]) = (v[i], v[j])

if isinstance(u, Permutation):

return Permutation(v)

return type(u)(v)

else:

return u

Coverage for local/lib/python2.7/site-packages/sage/combinat/yang_baxter_graph.py : 71%

173 statements 123 run 50 missing 0 excluded