Bases: sage.combinat.yang_baxter_graph.SwapOperator
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
Bases: sage.structure.sage_object.SageObject
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 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()
3
Construct the Yang-Baxter graph from root by repeated application of operators, or the Yang-Baxter graph associated to partition.
INPUT:
The user needs to provide either partition or both root and operators, where
OUTPUT:
EXAMPLES:
The Yang-Baxter graph defined by a partition is
the labelled directed graph with vertex set obtained by
bubble-sorting
;
there is an arrow from
to
labelled by
if
is
obtained by swapping the
-th and
-th elements of
.
For example, if the partition is
, then we begin with
and generate all tuples obtained from it by swapping
two adjacent entries if they are increasing:
sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
sage: bubbleswaps = [SwapIncreasingOperator(i) for i in range(3)]
sage: Y = YangBaxterGraph(root=(0,2,1,0), operators=bubbleswaps); Y
Yang-Baxter graph with root vertex (0, 2, 1, 0)
sage: Y.vertices()
[(2, 0, 1, 0), (2, 1, 0, 0), (0, 2, 1, 0)]
The partition keyword is a shorthand for the above construction.
sage: Y = YangBaxterGraph(partition=[3,1]); Y
Yang-Baxter graph of [3, 1], with top vertex (0, 2, 1, 0)
sage: Y.vertices()
[(0, 2, 1, 0), (2, 0, 1, 0), (2, 1, 0, 0)]
The permutahedron can be realized as a Yang-Baxter graph.
sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
sage: swappers = [SwapIncreasingOperator(i) for i in range(3)]
sage: Y = YangBaxterGraph(root=(1,2,3,4), operators=swappers); Y
Yang-Baxter graph with root vertex (1, 2, 3, 4)
sage: Y.plot()
The Cayley graph of a finite group can be realized as a Yang-Baxter graph.
sage: def left_multiplication_by(g):
... return lambda h : h*g
sage: G = CyclicPermutationGroup(4)
sage: operators = [ left_multiplication_by(gen) for gen in G.gens() ]
sage: Y = YangBaxterGraph(root=G.identity(), operators=operators); Y
Yang-Baxter graph with root vertex ()
sage: Y.plot(edge_labels=False)
sage: G = SymmetricGroup(4)
sage: operators = [left_multiplication_by(gen) for gen in G.gens()]
sage: Y = YangBaxterGraph(root=G.identity(), operators=operators); Y
Yang-Baxter graph with root vertex ()
sage: Y.plot(edge_labels=False)
AUTHORS:
Bases: sage.structure.sage_object.SageObject
A class to model the Yang-Baxter graph defined by root and operators.
INPUT:
Note
This is a lazy implementation: the digraph is only computed when it is needed.
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); Y
Yang-Baxter graph with root vertex (1, 0, 2, 1, 0)
sage: loads(dumps(Y)) == Y
True
AUTHORS:
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)]
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()
sage: Y.plot(edge_labels=False)
Relabel the edges of self.
INPUT:
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)]
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:
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)]
Returns the root vertex of self.
If self is the Yang-Baxter graph of the partition
, then this is the vertex
.
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 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))
[(2, 1, 0, 1, 0), (1, 2, 1, 0, 0)]
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:
OUTPUT:
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)
{(2, 0, 1, 0): (2, 1, 3, 4), (2, 1, 0, 0): (2, 3, 1, 4), (0, 2, 1, 0): (1, 2, 3, 4)}
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)]
Bases: sage.combinat.yang_baxter_graph.YangBaxterGraph_generic
A class to model the Yang-Baxter graph of a partition.
The Yang-Baxter graph defined by a partition
is the labelled directed graph with vertex set obtained by
bubble-sorting
;
there is an arrow from
to
labelled by
if
is
obtained by swapping the
-th and
-th elements of
.
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:
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:
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)]
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:
OUTPUT:
EXAMPLES:
sage: Y = YangBaxterGraph(partition=[3,1])
sage: Y.vertex_relabelling_dict((1,2,3,4))
{(2, 0, 1, 0): (2, 1, 3, 4), (2, 1, 0, 0): (2, 3, 1, 4), (0, 2, 1, 0): (1, 2, 3, 4)}
sage: Y.vertex_relabelling_dict((4,3,2,1))
{(2, 0, 1, 0): (3, 4, 2, 1), (2, 1, 0, 0): (3, 2, 4, 1), (0, 2, 1, 0): (4, 3, 2, 1)}