Coverage for local/lib/python2.7/site-packages/sage/combinat/rigged_configurations/kleber_tree.py : 80%

r""" 

Kleber Trees 

A Kleber tree is a tree of weights generated by Kleber's algorithm 

[Kleber1]_. The nodes correspond to the weights in the positive Weyl chamber 

obtained by subtracting a (non-zero) positive root. The edges are labeled by 

the coefficients of the roots of the difference. 

AUTHORS: 

- Travis Scrimshaw (2011-05-03): Initial version 

- Travis Scrimshaw (2013-02-13): Added support for virtual trees and improved 

`\LaTeX` output 

EXAMPLES:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree 

sage: KleberTree(['A', 3, 1], [[3,2], [2,1], [1,1], [1,1]]) 

Kleber tree of Cartan type ['A', 3, 1] and B = ((3, 2), (2, 1), (1, 1), (1, 1)) 

sage: KleberTree(['D', 4, 1], [[2,2]]) 

Kleber tree of Cartan type ['D', 4, 1] and B = ((2, 2),) 

TESTS:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree 

sage: KT = KleberTree(['A', 3, 1], [[3,2], [2,1], [1,1], [1,1]]) 

sage: sorted((x.weight.to_vector(), x.up_root.to_vector()) for x in KT.list()) 

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

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

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

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

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

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

((1, 1, 1), (1, 1, 1)), 

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

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

((3, 0, 1), (0, 1, 1))] 

sage: KT = KleberTree(['A', 7, 1], [[3,2], [2,1], [1,1]]) 

sage: KT 

Kleber tree of Cartan type ['A', 7, 1] and B = ((3, 2), (2, 1), (1, 1)) 

sage: sorted((x.weight.to_vector(), x.up_root.to_vector()) for x in KT.list()) 

[((0, 0, 0, 1, 1, 0, 0), (1, 1, 1, 0, 0, 0, 0)), 

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

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

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

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

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

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

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

""" 

#***************************************************************************** 

# Copyright (C) 2011, 2012 Travis Scrimshaw <tscrim@ucdavis.edu> 

# 

# Distributed under the terms of the GNU General Public License (GPL) 

# 

# This code is distributed in the hope that it will be useful, 

# but WITHOUT ANY WARRANTY; without even the implied warranty of 

# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 

# General Public License for more details. 

# 

# The full text of the GPL is available at: 

# 

# http://www.gnu.org/licenses/ 

#***************************************************************************** 

from six.moves import range 

import itertools 

from sage.misc.lazy_attribute import lazy_attribute 

from sage.misc.cachefunc import cached_method 

from sage.misc.latex import latex 

from sage.misc.misc_c import prod 

from sage.arith.all import binomial 

from sage.rings.integer import Integer 

from sage.rings.all import ZZ 

from sage.structure.parent import Parent 

from sage.structure.element import Element 

from sage.structure.unique_representation import UniqueRepresentation 

from sage.structure.richcmp import richcmp_not_equal, richcmp 

from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets 

from sage.modules.free_module import FreeModule 

from sage.combinat.root_system.cartan_type import CartanType 

from sage.graphs.digraph import DiGraph 

from sage.graphs.dot2tex_utils import have_dot2tex 

###################################### 

# Latex method for viewing the trees # 

###################################### 

def _draw_tree(tree_node, node_label=True, style_point=None, style_node='fill=white', style_line=None, 

hspace=2.5, vspace=-2.5, start=[0.,0.], rpos=[0.,0.], node_id=0, node_prefix='T', 

edge_labels=True, use_vector_notation=False): 

r""" 

Return the tikz latex for drawing the Kleber tree. 

AUTHORS: 

- Viviane Pons (2013-02-13): Initial version 

- Travis Scrimshaw (2013-03-02): Modified to work with Kleber tree output 

.. WARNING:: 

Internal latex function. 

EXAMPLES:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree 

sage: KT = KleberTree(['A',3,1], [[3,2],[1,1]]) 

sage: latex(KT) # indirect doctest 

\begin{tikzpicture} 

\node[fill=white] (T0) at (0.000, 0.000){$V_{\omega_{1}+2\omega_{3}}$}; 

\node (T00) at (0.000, -2.500){$V_{\omega_{3}}$}; 

\draw (T0) to node[sloped,above]{\tiny $\alpha_{1} + \alpha_{2} + \alpha_{3}$} (T00); 

\end{tikzpicture} 

""" 

draw_point = lambda point: '(%.3f, %.3f)'%(point[0],point[1]) 

if not tree_node.children: 

r = '' 

node_name = node_prefix + str(node_id) 

r = "\\node (%s) at %s"%(node_name, draw_point(start)) 

if node_label: 

r += "{$%s$};\n"%tree_node._latex_() 

else: 

r += "{};\n" 

rpos[0] = start[0] 

rpos[1] = start[1] 

start[0] += hspace 

return r 

node_name = node_prefix + str(node_id) 

if style_line is None: 

style_line_str = '' 

else: 

style_line_str = "[%s]"%style_line 

if node_label: 

node_place_str = '' 

else: 

node_place_str = ".center" 

nb_children = len(tree_node.children) 

half = nb_children // 2 

children_str = '' 

pos = [start[0],start[1]] 

start[1] += vspace 

lines_str = '' 

# Getting children string 

for i in range(nb_children): 

if i == half and nb_children % 2 == 0: 

pos[0] = start[0] 

start[0] += hspace 

if i == half+1 and nb_children % 2 == 1: 

pos[0] = rpos[0] 

child = tree_node.children[i] 

children_str += _draw_tree(child, node_label=node_label, style_node=style_node, style_point=style_point, style_line=style_line, hspace=hspace, vspace=vspace, start=start, rpos=rpos, node_id=i, node_prefix=node_name, edge_labels=edge_labels, use_vector_notation=use_vector_notation) 

if edge_labels: 

if use_vector_notation: 

edge_str = latex(child.up_root.to_vector()) 

else: 

edge_str = latex(child.up_root) 

lines_str += "\\draw%s (%s%s) to node[sloped,above]{\\tiny $%s$} (%s%s%s);\n"%(style_line_str, node_name, node_place_str, edge_str, node_name, i, node_place_str) 

else: 

lines_str += "\\draw%s (%s%s) -- (%s%s%s);\n"%(style_line_str, node_name, node_place_str, node_name, i, node_place_str) 

#drawing root 

if style_node is None: 

style_node = '' 

else: 

style_node = "[%s]"%style_node 

if style_point is None: 

style_point = '' 

else: 

style_point = "[%s]"%style_point 

start[1] -= vspace 

rpos[0] = pos[0] 

rpos[1] = pos[1] 

point_str = '' 

node_str = "\\node%s (%s) at %s"%(style_node, node_name, draw_point(pos)) 

if node_label: 

node_str += "{$%s$};\n"%tree_node._latex_() 

else: 

node_str += "{};\n" 

point_str = "\\draw%s (%s) circle;\n"%(style_point, node_name) 

res = node_str 

res += children_str 

res += lines_str 

res += point_str 

return res 

##################### 

# Kleber tree nodes # 

##################### 

class KleberTreeNode(Element): 

r""" 

A node in the Kleber tree. 

This class is meant to be used internally by the Kleber tree class and 

should not be created directly by the user. 

For more on the Kleber tree and the nodes, see :class:`KleberTree`. 

The dominating root is the ``up_root`` which is the difference 

between the parent node's weight and this node's weight. 

INPUT: 

- ``parent_obj`` -- The parent object of this element 

- ``node_weight`` -- The weight of this node 

- ``dominant_root`` -- The dominating root 

- ``parent_node`` -- (default:None) The parent node of this node 

""" 

def __init__(self, parent_obj, node_weight, dominant_root, parent_node=None): 

r""" 

Initialize the tree node. 

TESTS:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree 

sage: RS = RootSystem(['A', 2]) 

sage: WS = RS.weight_lattice() 

sage: R = RS.root_lattice() 

sage: KT = KleberTree(['A', 2, 1], [[1,1]]) 

sage: parent = KT(WS.sum_of_terms([(1,5), (2,2)]), R.zero()) 

sage: parent 

Kleber tree node with weight [5, 2] and upwards edge root [0, 0] 

sage: parent.parent_node 

sage: child = KT(WS.sum_of_terms([(1,3), (2,1)]), R.sum_of_terms([(1,1), (2,2)]), parent) 

sage: child 

Kleber tree node with weight [3, 1] and upwards edge root [1, 2] 

sage: child.parent_node 

Kleber tree node with weight [5, 2] and upwards edge root [0, 0] 

sage: TestSuite(parent).run() 

""" 

self.parent_node = parent_node 

self.children = [] 

self.weight = node_weight 

self.up_root = dominant_root 

Element.__init__(self, parent_obj) 

@lazy_attribute 

def depth(self): 

""" 

Return the depth of this node in the tree. 

EXAMPLES:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree 

sage: RS = RootSystem(['A', 2]) 

sage: WS = RS.weight_lattice() 

sage: R = RS.root_lattice() 

sage: KT = KleberTree(['A', 2, 1], [[1,1]]) 

sage: n = KT(WS.sum_of_terms([(1,5), (2,2)]), R.zero()) 

sage: n.depth 

0 

sage: n2 = KT(WS.sum_of_terms([(1,5), (2,2)]), R.zero(), n) 

sage: n2.depth 

1 

""" 

depth = -1 # Offset 

cur = self 

while cur is not None: 

depth += 1 

cur = cur.parent_node 

return depth 

@cached_method 

def multiplicity(self): 

r""" 

Return the multiplicity of ``self``. 

The multiplicity of a node `x` of depth `d` weight `\lambda` in a 

simply-laced Kleber tree is equal to: 

.. MATH:: 

\prod_{i > 0} \prod_{a \in \overline{I}} 

\binom{p_i^{(a)} + m_i^{(a)}}{p_i^{(a)}} 

Recall that 

.. MATH:: 

m_i^{(a)} = \left( \lambda^{(i-1)} - 2 \lambda^{(i)} + 

\lambda^{(i+1)} \mid \overline{\Lambda}_a \right), 

p_i^{(a)} = \left( \alpha_a \mid \lambda^{(i)} \right) 

- \sum_{j > i} (j - i) L_j^{(a)}, 

where `\lambda^{(i)}` is the weight node at depth `i` in the path 

to `x` from the root and we set `\lambda^{(j)} = \lambda` for all 

`j \geq d`. 

Note that `m_i^{(a)} = 0` for all `i > d`. 

EXAMPLES:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree 

sage: KT = KleberTree(['A',3,1], [[3,2],[2,1],[1,1],[1,1]]) 

sage: for x in KT: x, x.multiplicity() 

(Kleber tree node with weight [2, 1, 2] and upwards edge root [0, 0, 0], 1) 

(Kleber tree node with weight [3, 0, 1] and upwards edge root [0, 1, 1], 1) 

(Kleber tree node with weight [0, 2, 2] and upwards edge root [1, 0, 0], 1) 

(Kleber tree node with weight [1, 0, 3] and upwards edge root [1, 1, 0], 2) 

(Kleber tree node with weight [1, 1, 1] and upwards edge root [1, 1, 1], 4) 

(Kleber tree node with weight [0, 0, 2] and upwards edge root [2, 2, 1], 2) 

(Kleber tree node with weight [2, 0, 0] and upwards edge root [0, 1, 1], 2) 

(Kleber tree node with weight [0, 0, 2] and upwards edge root [1, 1, 0], 1) 

(Kleber tree node with weight [0, 1, 0] and upwards edge root [1, 1, 1], 2) 

(Kleber tree node with weight [0, 1, 0] and upwards edge root [0, 0, 1], 1) 

TESTS: 

We check that :trac:`16057` is fixed:: 

sage: RC = RiggedConfigurations(['D',4,1], [[1,3],[3,3],[4,3]]) 

sage: sum(x.multiplicity() for x in RC.kleber_tree()) == len(RC.module_generators) 

True 

""" 

# The multiplicity corresponding to the root is always 1 

if self.parent_node is None: 

return Integer(1) 

mult = Integer(1) 

I = self.parent()._classical_ct.index_set() 

for a,m in self.up_root: 

p = self.weight[a] 

for r,s in self.parent().B: 

if r == a and s > self.depth: 

p -= s - self.depth 

mult *= binomial(m + p, m) 

prev_up_root = self.up_root 

cur = self.parent_node 

while cur.parent_node is not None: 

root_diff = cur.up_root - prev_up_root 

for a,m in root_diff: 

p = cur.weight[a] 

for r,s in self.parent().B: 

if r == a and s > cur.depth: 

p -= s - cur.depth 

mult *= binomial(m + p, m) 

prev_up_root = cur.up_root 

cur = cur.parent_node 

return mult 

def __hash__(self): 

r""" 

TESTS:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree 

sage: RS = RootSystem(['A', 2]) 

sage: WS = RS.weight_lattice() 

sage: R = RS.root_lattice() 

sage: KT = KleberTree(['A', 2, 1], [[1,1]]) 

sage: n = KT(WS.sum_of_terms([(1,5), (2,2)]), R.zero()) 

sage: hash(n) 

-603608031356818252 # 64-bit 

-1956156236 # 32-bit 

""" 

return hash(self.depth) ^ hash(self.weight) 

def _richcmp_(self, rhs, op): 

r""" 

Check whether two nodes are equal. 

TESTS:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree 

sage: RS = RootSystem(['A', 2]) 

sage: WS = RS.weight_lattice() 

sage: R = RS.root_lattice() 

sage: KT = KleberTree(['A', 2, 1], [[1,1]]) 

sage: n = KT(WS.sum_of_terms([(1,5), (2,2)]), R.zero()) 

sage: n2 = KT(WS.sum_of_terms([(1,5), (2,2)]), R.zero(), n) 

sage: n2 > n 

True 

sage: n3 = KT(WS.sum_of_terms([(1,5), (2,2)]), R.zero(), n) 

sage: n2 == n3 

True 

sage: n3 = KT(WS.sum_of_terms([(1,5), (2,3)]), R.zero(), n) 

sage: n2 < n3 

True 

""" 

lx = self.depth 

rx = rhs.depth 

if lx != rx: 

return richcmp_not_equal(lx, rx, op) 

lx = self.parent_node 

rx = rhs.parent_node 

if lx != rx: 

return richcmp_not_equal(lx, rx, op) 

return richcmp(self.weight, rhs.weight, op) 

def _repr_(self): 

r""" 

Return the string representation of ``self``. 

EXAMPLES:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree 

sage: RS = RootSystem(['A', 3]) 

sage: WS = RS.weight_lattice() 

sage: R = RS.root_lattice() 

sage: KT = KleberTree(['A', 2, 1], [[1,1]]) 

sage: node = KT(WS.sum_of_terms([(1,2), (2,1), (3,1)]), R.sum_of_terms([(1,3), (3,3)])); node 

Kleber tree node with weight [2, 1, 1] and upwards edge root [3, 0, 3] 

With virtual nodes:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import VirtualKleberTree 

sage: KT = VirtualKleberTree(['A',6,2], [[2,2]]) 

sage: KT.root 

Kleber tree node with weight [0, 2, 0, 2, 0] and upwards edge root [0, 0, 0, 0, 0] 

""" 

return "Kleber tree node with weight %s and upwards edge root %s"%( 

list(self.weight.to_vector()), list(self.up_root.to_vector()) ) 

def _latex_(self): 

r""" 

Return latex representation of ``self``. 

TESTS:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree 

sage: RS = RootSystem(['A', 3]) 

sage: WS = RS.weight_lattice() 

sage: R = RS.root_lattice() 

sage: KT = KleberTree(['A', 3, 1], [[3,2], [1,1]]) 

sage: node = KT(WS.sum_of_terms([(1,4), (3,1)]), R.zero()) 

sage: latex(node) 

V_{4\omega_{1}+\omega_{3}} 

sage: node = KT(WS.zero(), R.zero()) 

sage: latex(node) 

V_{0} 

sage: node = KT(WS.sum_of_terms([(1,2)]), R.zero()) 

sage: latex(node) 

V_{2\omega_{1}} 

With virtual nodes:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import VirtualKleberTree 

sage: KT = VirtualKleberTree(['C',3,1], [[2,2]]) 

sage: latex(KT.root) 

[V_{2\omega_{2}+2\omega_{4}}] 

sage: KT = VirtualKleberTree(['A',6,2], [[2,2]]) 

sage: latex(KT.root) 

[V_{2\omega_{2}+2\omega_{4}}] 

""" 

ret_str = "V_{" 

if self.multiplicity() != 1: 

ret_str = repr(self.multiplicity()) + ret_str 

for pair in self.weight: 

if pair[1] > 1: 

ret_str += repr(pair[1]) + "\omega_{" + repr(pair[0]) + "}+" 

elif pair[1] == 1: 

ret_str += "\omega_{" + repr(pair[0]) + "}+" 

if ret_str[-1] == '{': 

ret_str += "0}" 

else: 

ret_str = ret_str[:-1] + "}" 

ct = self.parent()._cartan_type 

if ct.type() == 'BC' or ct.dual().type() == 'BC': 

return "[" + ret_str + "]" 

elif not ct.is_simply_laced(): 

s_factors = self.parent()._folded_ct.scaling_factors() 

gamma = max(s_factors) 

# Subtract 1 for indexing 

if gamma > 1: 

L = [self.parent()._folded_ct.folding_orbit()[a][0] for a in 

range(1, len(s_factors)) if s_factors[a] == gamma] 

else: 

L = [] 

if self.depth % gamma == 0 or all(self.up_root[a] == 0 for a in L): 

return "[" + ret_str + "]" 

return ret_str 

####################### 

# Kleber tree classes # 

####################### 

class KleberTree(UniqueRepresentation, Parent): 

r""" 

The tree that is generated by Kleber's algorithm. 

A Kleber tree is a tree of weights generated by Kleber's algorithm 

[Kleber1]_. It is used to generate the set of all admissible rigged 

configurations for the simply-laced affine types `A_n^{(1)}`, 

`D_n^{(1)}`, `E_6^{(1)}`, `E_7^{(1)}`, and `E_8^{(1)}`. 

.. SEEALSO:: 

There is a modified version for non-simply-laced affine types at 

:class:`VirtualKleberTree`. 

The nodes correspond to the weights in the positive Weyl chamber obtained 

by subtracting a (non-zero) positive root. The edges are labeled by the 

coefficients of the roots, and `X` is a child of `Y` if `Y` is the root 

else if the edge label of `Y` to its parent `Z` is greater (in every 

component) than the label from `X` to `Y`. 

For a Kleber tree, one needs to specify an affine (simply-laced) 

Cartan type and a sequence of pairs `(r,s)`, where `s` is any positive 

integer and `r` is a node in the Dynkin diagram. Each `(r,s)` can be 

viewed as a rectangle of width `s` and height `r`. 

INPUT: 

- ``cartan_type`` -- an affine simply-laced Cartan type 

- ``B`` -- a list of dimensions of rectangles by `[r, c]` 

where `r` is the number of rows and `c` is the number of columns 

REFERENCES: 

.. [Kleber1] Michael Kleber. 

*Combinatorial structure of finite dimensional representations of 

Yangians: the simply-laced case*. 

Internat. Math. Res. Notices. (1997) no. 4. 187-201. 

.. [Kleber2] Michael Kleber. 

*Finite dimensional representations of quantum affine algebras*. 

Ph.D. dissertation at University of California Berkeley. (1998). 

:arxiv:`math.QA/9809087`. 

EXAMPLES: 

Simply-laced example:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree 

sage: KT = KleberTree(['A', 3, 1], [[3,2], [1,1]]) 

sage: KT.list() 

[Kleber tree node with weight [1, 0, 2] and upwards edge root [0, 0, 0], 

Kleber tree node with weight [0, 0, 1] and upwards edge root [1, 1, 1]] 

sage: KT = KleberTree(['A', 3, 1], [[3,2], [2,1], [1,1], [1,1]]) 

sage: KT.cardinality() 

10 

sage: KT = KleberTree(['D', 4, 1], [[2,2]]) 

sage: KT.cardinality() 

3 

sage: KT = KleberTree(['D', 4, 1], [[4,5]]) 

sage: KT.cardinality() 

1 

From [Kleber2]_:: 

sage: KT = KleberTree(['E', 6, 1], [[4, 2]]) # long time (9s on sage.math, 2012) 

sage: KT.cardinality() # long time 

12 

We check that relabelled types work (:trac:`16876`):: 

sage: ct = CartanType(['A',3,1]).relabel(lambda x: x+2) 

sage: kt = KleberTree(ct, [[3,1],[5,1]]) 

sage: list(kt) 

[Kleber tree node with weight [1, 0, 1] and upwards edge root [0, 0, 0], 

Kleber tree node with weight [0, 0, 0] and upwards edge root [1, 1, 1]] 

sage: kt = KleberTree(['A',3,1], [[1,1],[3,1]]) 

sage: list(kt) 

[Kleber tree node with weight [1, 0, 1] and upwards edge root [0, 0, 0], 

Kleber tree node with weight [0, 0, 0] and upwards edge root [1, 1, 1]] 

""" 

@staticmethod 

def __classcall_private__(cls, cartan_type, B, classical=None): 

""" 

Normalize the input arguments to ensure unique representation. 

EXAMPLES:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree 

sage: KT1 = KleberTree(CartanType(['A',3,1]), [[2,2]]) 

sage: KT2 = KleberTree(['A',3,1], [(2,2)]) 

sage: KT3 = KleberTree(['A',3,1], ((2,2),)) 

sage: KT2 is KT1, KT3 is KT1 

(True, True) 

""" 

cartan_type = CartanType(cartan_type) 

if not cartan_type.is_affine(): 

raise ValueError("The Cartan type must be affine") 

if not cartan_type.classical().is_simply_laced(): 

raise ValueError("use VirtualKleberTree for non-simply-laced types") 

# Standardize B input into a tuple of tuples 

B = tuple([tuple(rs) for rs in B]) 

if classical is None: 

classical = cartan_type.classical() 

else: 

classical = CartanType(classical) 

return super(KleberTree, cls).__classcall__(cls, cartan_type, B, classical) 

def __init__(self, cartan_type, B, classical_ct): 

r""" 

Construct a Kleber tree. 

The input ``classical_ct`` is the classical Cartan type to run the 

algorithm on and is only meant to be used internally. 

EXAMPLES:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree 

sage: KT = KleberTree(['D', 3, 1], [[1,1], [1,1]]); KT 

Kleber tree of Cartan type ['D', 3, 1] and B = ((1, 1), (1, 1)) 

sage: TestSuite(KT).run(skip="_test_elements") 

""" 

Parent.__init__(self, category=FiniteEnumeratedSets()) 

self._cartan_type = cartan_type 

self.B = B 

self._classical_ct = classical_ct 

# Our computations in _children_iter_vector use dense vectors. 

# Moreover, ranks are relatively small, so just use the dense 

# version of the Cartan matrix. 

self._CM = self._classical_ct.cartan_matrix().dense_matrix() 

self._build_tree() 

self._latex_options = dict(edge_labels=True, use_vector_notation=False, 

hspace=2.5, vspace=min(-2.5, -0.75*self._classical_ct.rank())) 

def latex_options(self, **options): 

""" 

Return the current latex options if no arguments are passed, otherwise 

set the corresponding latex option. 

OPTIONS: 

- ``hspace`` -- (default: `2.5`) the horizontal spacing of the 

tree nodes 

- ``vspace`` -- (default: ``x``) the vertical spacing of the tree 

nodes, here ``x`` is the minimum of `-2.5` or `-.75n` where `n` is 

the rank of the classical type 

- ``edge_labels`` -- (default: ``True``) display edge labels 

- ``use_vector_notation`` -- (default: ``False``) display edge labels 

using vector notation instead of a linear combination 

EXAMPLES:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree 

sage: KT = KleberTree(['D', 3, 1], [[2,1], [2,1]]) 

sage: KT.latex_options(vspace=-4, use_vector_notation=True) 

sage: sorted(KT.latex_options().items()) 

[('edge_labels', True), ('hspace', 2.5), ('use_vector_notation', True), ('vspace', -4)] 

""" 

if not options: 

from copy import copy 

return copy(self._latex_options) 

for k in options: 

self._latex_options[k] = options[k] 

def _latex_(self): 

r""" 

Return a latex representation of this Kleber tree. 

.. SEEALSO:: 

:meth:`latex_options()` 

EXAMPLES:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree 

sage: KT = KleberTree(['D', 3, 1], [[2,1], [2,1]]) 

sage: KT._latex_() 

'\\begin{tikzpicture}...\\end{tikzpicture}' 

""" 

from sage.graphs.graph_latex import setup_latex_preamble 

setup_latex_preamble() 

return "\\begin{tikzpicture}\n" + \ 

_draw_tree(self.root, **self._latex_options) \ 

+ "\\end{tikzpicture}" 

def _build_tree(self): 

""" 

Build the Kleber tree. 

TESTS: 

This is called from the constructor:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree 

sage: KT = KleberTree(['A',3,1], [[2,2]]) # indirect doctest 

""" 

P = self._classical_ct.root_system().weight_lattice() 

# Create an empty node at first step 

self.root = KleberTreeNode(self, P.zero(), 

self._classical_ct.root_system().root_lattice().zero()) 

full_list = [self.root] # The list of tree nodes 

n = self._classical_ct.rank() 

# Convert the B values into an L matrix 

L = [] 

I = self._classical_ct.index_set() 

for i in range(n): 

L.append([0]) 

for r,s in self.B: 

while len(L[0]) < s: # Add more columns if needed 

for row in L: 

row.append(0) 

L[I.index(r)][s - 1] += 1 # The -1 is for indexing 

# Perform a special case of the algorithm for the root node 

weight_basis = P.basis() 

for a in range(n): 

self.root.weight += sum(L[a]) * weight_basis[I[a]] 

new_children = [] 

for new_child in self._children_iter(self.root): 

if not self._prune(new_child, 1): 

new_children.append(new_child) 

self.root.children.append(new_child) 

full_list.append(new_child) 

depth = 1 

growth = True 

# self._has_normaliz is set by _children_iter 

if self._classical_ct.rank() >= 7 or self._has_normaliz: 

child_itr = self._children_iter 

else: 

child_itr = self._children_iter_vector 

while growth: 

growth = False 

depth += 1 

leaves = new_children 

if depth <= len(L[0]): 

new_children = [] 

for x in full_list: 

growth = True 

for a in range(n): 

for i in range(depth - 1, len(L[a])): # Subtract 1 for indexing 

x.weight += L[a][i] * weight_basis[I[a]] 

new_children = [new_child 

for x in leaves 

for new_child in child_itr(x) 

if not self._prune(new_child, depth)] 

# Connect the new children into the tree 

if new_children: 

growth = True 

for new_child in new_children: 

new_child.parent_node.children.append(new_child) 

full_list.append(new_child) 

self._set = full_list 

def _children_iter(self, node): 

r""" 

Iterate over the children of ``node``. 

Helper iterator to iterate over all children, by generating and/or 

computing them, of the Kleber tree node. 

We compute the children by computing integral points (expressed as 

simple roots) in the polytope given by the intersection of the 

negative root cone and shifted positive weight cone. More precisely, 

we rewrite the condition `\lambda - \mu \in Q^+`, for `\mu \in P^+`, 

as `\lambda - Q^+ = \mu \in P^+`. 

INPUT: 

- ``node`` -- the current node in the tree whose children we want 

to generate 

TESTS:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree 

sage: KT = KleberTree(['D', 3, 1], [[1,1], [1,1]]) 

sage: for x in KT: x # indirect doctest 

Kleber tree node with weight [2, 0, 0] and upwards edge root [0, 0, 0] 

Kleber tree node with weight [0, 1, 1] and upwards edge root [1, 0, 0] 

Kleber tree node with weight [0, 0, 0] and upwards edge root [2, 1, 1] 

sage: KT = KleberTree(['D', 4, 1], [[2,2]]) 

sage: KT[1] 

Kleber tree node with weight [0, 1, 0, 0] and upwards edge root [1, 2, 1, 1] 

sage: for x in KT: x 

Kleber tree node with weight [0, 2, 0, 0] and upwards edge root [0, 0, 0, 0] 

Kleber tree node with weight [0, 1, 0, 0] and upwards edge root [1, 2, 1, 1] 

Kleber tree node with weight [0, 0, 0, 0] and upwards edge root [1, 2, 1, 1] 

sage: for x in KT._children_iter(KT[1]): x 

Kleber tree node with weight [0, 0, 0, 0] and upwards edge root [1, 2, 1, 1] 

""" 

# It is faster to just cycle through than build the polytope and its 

# lattice points when we are sufficiently small 

# The number 500 comes from testing on my machine about where the 

# tradeoff occurs between the methods. However, this may grow as 

# the _children_iter_vector is further optimized. 

if node != self.root and prod(val+1 for val in node.up_root.coefficients()) < 1000: 

for x in self._children_iter_vector(node): 

yield x 

return 

n = self._classical_ct.rank() 

I = self._classical_ct.index_set() 

Q = self._classical_ct.root_system().root_lattice() 

P = self._classical_ct.root_system().weight_lattice() 

# Construct the polytope by inequalities 

from sage.geometry.polyhedron.constructor import Polyhedron 

# Construct the shifted weight cone 

root_weight = node.weight.to_vector() 

ieqs = [[root_weight[i]] + list(col) 

for i,col in enumerate(self._CM.columns())] 

# Construct the negative weight cone 

for i in range(n): 

v = [0] * (n+1) 

v[i+1] = -1 

ieqs.append(v) 

ieqs.append([-1]*(n+1)) # For avoiding the origin 

# Construct the bounds for the non-root nodes 

if node != self.root: 

for i,c in enumerate(node.up_root.to_vector()): 

v = [0] * (n+1) 

v[0] = c 

v[i+1] = 1 

ieqs.append(v) 

try: 

poly = Polyhedron(ieqs=ieqs, backend='normaliz') 

self._has_normaliz = True 

except ImportError: 

poly = Polyhedron(ieqs=ieqs) 

self._has_normaliz = False 

# Build the nodes from the polytope 

# Sort for a consistent ordering (it is typically a small list) 

for pt in sorted(poly.integral_points(), reverse=True): 

up_root = Q._from_dict({I[i]: -val for i,val in enumerate(pt) if val != 0}, 

remove_zeros=False) 

wt = node.weight + sum(val * P.simple_root(I[i]) for i,val in enumerate(pt)) 

yield KleberTreeNode(self, wt, up_root, node) 

def _children_iter_vector(self, node): 

r""" 

Iterate over the children of ``node``. 

Helper iterator to iterate over all children, by generating and/or 

computing them, of the Kleber tree node. This implementation 

iterates over all possible uproot vectors. 

.. SEEALSO:: 

:meth:`_children_iter` 

INPUT: 

- ``node`` -- the current node in the tree whose children we want 

to generate 

TESTS:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree 

sage: KT = KleberTree(['D', 4, 1], [[2,2]]) 

sage: KT[1] 

Kleber tree node with weight [0, 1, 0, 0] and upwards edge root [1, 2, 1, 1] 

sage: for x in KT._children_iter(KT[1]): x 

Kleber tree node with weight [0, 0, 0, 0] and upwards edge root [1, 2, 1, 1] 

""" 

Q = self._classical_ct.root_system().root_lattice() 

P = self._classical_ct.root_system().weight_lattice() 

I = self._classical_ct.index_set() 

wt = node.weight.to_vector() 

cols = self._CM.columns() 

F = FreeModule(ZZ, self._classical_ct.rank()) 

L = [range(val + 1) for val in node.up_root.to_vector()] 

it = itertools.product(*L) 

next(it) # First element is the zero element 

for root in it: 

# Convert the list to the weight lattice 

converted_root = sum(cols[i] * c for i,c in enumerate(root) if c != 0) 

if all(wt[i] >= val for i,val in enumerate(converted_root)): 

wd = {I[i]: wt[i] - val for i,val in enumerate(converted_root)} 

rd = {I[i]: val for i,val in enumerate(root) if val != 0} 

yield KleberTreeNode(self, 

P._from_dict(wd), 

Q._from_dict(rd, remove_zeros=False), 

node) 

def _prune(self, new_child, depth): 

r""" 

Return ``True`` if we are to prune the tree at ``new_child``. 

This always returns ``False`` since we do not do any pruning. 

EXAMPLES:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree 

sage: KT = KleberTree(['A', 2, 1], [[1,1]]) 

sage: KT._prune(KT.root, 0) 

False 

""" 

return False 

def breadth_first_iter(self): 

r""" 

Iterate over all nodes in the tree following a breadth-first traversal. 

EXAMPLES:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree 

sage: KT = KleberTree(['A', 3, 1], [[2, 2], [2, 3]]) 

sage: for x in KT.breadth_first_iter(): x 

Kleber tree node with weight [0, 5, 0] and upwards edge root [0, 0, 0] 

Kleber tree node with weight [1, 3, 1] and upwards edge root [0, 1, 0] 

Kleber tree node with weight [0, 3, 0] and upwards edge root [1, 2, 1] 

Kleber tree node with weight [2, 1, 2] and upwards edge root [0, 1, 0] 

Kleber tree node with weight [1, 1, 1] and upwards edge root [0, 1, 0] 

Kleber tree node with weight [0, 1, 0] and upwards edge root [1, 2, 1] 

""" 

cur = [] 

next = [self.root] 

while len(next) > 0: 

cur = next 

next = [] 

for node in cur: 

yield node 

next.extend(node.children) 

def depth_first_iter(self): 

r""" 

Iterate (recursively) over the nodes in the tree following a 

depth-first traversal. 

EXAMPLES:: 

sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree 

sage: KT = KleberTree(['A', 3, 1], [[2, 2], [2, 3]]) 

sage: for x in KT.depth_first_iter(): x 

Kleber tree node with weight [0, 5, 0] and upwards edge root [0, 0, 0] 

Kleber tree node with weight [1, 3, 1] and upwards edge root [0, 1, 0] 

Kleber tree node with weight [2, 1, 2] and upwards edge root [0, 1, 0] 

Kleber tree node with weight [0, 3, 0] and upwards edge root [1, 2, 1]