r"""
Kleber tree

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:

- <NAME> (2011-05-03): Initial version

REFERENCES:

    .. [Kleber1] <NAME>.
        Combinatorial structure of finite dimensional representations of Yangians:
        the simply-laced case.
        Internat. Math. Res. Notices 1997. no. 4. 187-201.

    .. [Kleber2] <NAME>.
        Finite dimensional representations of quantum affine algebras.
        Ph.D. dissertation at University of California Berkeley. 1998.
        math.QA/9809087.

.. TODO:: Output the tree as a graph using the graph code

EXAMPLES::

    sage: KleberTree(['A', 3], [[3,2], [2,1], [1,1], [1,1]])
    Kleber tree of Cartan type ['A', 3] and root weight [2, 1, 2]
    sage: KleberTree(['D', 4], [[2,2]])
    Kleber tree of Cartan type ['D', 4] and root weight [0, 2, 0, 0]

TESTS::

    sage: KT = KleberTree(['A', 3], [[3,2], [2,1], [1,1], [1,1]])
    sage: for x in set(KT.list()): x
    ...
    Kleber tree node with weight [1, 0, 3] and upwards edge root [1, 1, 0]
    Kleber tree node with weight [0, 2, 2] and upwards edge root [1, 0, 0]
    Kleber tree node with weight [2, 1, 2] and upwards edge root [0, 0, 0]
    Kleber tree node with weight [2, 0, 0] and upwards edge root [0, 1, 1]
    Kleber tree node with weight [0, 0, 2] and upwards edge root [1, 1, 0]
    Kleber tree node with weight [0, 1, 0] and upwards edge root [0, 0, 1]
    Kleber tree node with weight [3, 0, 1] and upwards edge root [0, 1, 1]
    Kleber tree node with weight [0, 1, 0] and upwards edge root [1, 1, 1]
    Kleber tree node with weight [1, 1, 1] and upwards edge root [1, 1, 1]
    Kleber tree node with weight [0, 0, 2] and upwards edge root [2, 2, 1]

    sage: KT = KleberTree(['A', 7], [[3,2], [2,1], [1,1]])
    sage: KT
    Kleber tree of Cartan type ['A', 7] and root weight [1, 1, 2, 0, 0, 0, 0]
    sage: for x in set(KT.list()): x
    ...
    Kleber tree node with weight [1, 0, 1, 0, 1, 0, 0] and upwards edge root [1, 2, 2, 1, 0, 0, 0]
    Kleber tree node with weight [0, 0, 1, 0, 0, 1, 0] and upwards edge root [2, 3, 3, 2, 1, 0, 0]
    Kleber tree node with weight [1, 1, 2, 0, 0, 0, 0] and upwards edge root [0, 0, 0, 0, 0, 0, 0]
    Kleber tree node with weight [2, 0, 1, 1, 0, 0, 0] and upwards edge root [0, 1, 1, 0, 0, 0, 0]
    Kleber tree node with weight [1, 0, 0, 2, 0, 0, 0] and upwards edge root [0, 1, 1, 0, 0, 0, 0]
    Kleber tree node with weight [0, 0, 3, 0, 0, 0, 0] and upwards edge root [1, 1, 0, 0, 0, 0, 0]
    Kleber tree node with weight [0, 0, 0, 1, 1, 0, 0] and upwards edge root [1, 1, 1, 0, 0, 0, 0]
    Kleber tree node with weight [0, 1, 1, 1, 0, 0, 0] and upwards edge root [1, 1, 1, 0, 0, 0, 0]

"""

#*****************************************************************************
#       Copyright (C) 2011, 2012 <NAME> <<EMAIL>>
#
#  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 sage.misc.lazy_attribute import lazy_attribute
from sage.misc.latex import latex
from sage.rings.integer import Integer

from sage.structure.parent import Parent
from sage.structure.element import Element
from sage.structure.unique_representation import UniqueRepresentation
from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets

from sage.combinat.root_system.cartan_type import CartanType
from sage.combinat.cartesian_product import CartesianProduct

from sage.graphs.digraph import DiGraph
from sage.graphs.dot2tex_utils import have_dot2tex

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`.
    """

    def __init__(self, parent_obj, node_weight, dominant_root, parent_node=None):
        r"""
        Initialize the tree node.

        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

        TESTS::

            sage: RS = RootSystem(['A', 2])
            sage: WS = RS.weight_space()
            sage: R = RS.root_space()
            sage: KT = KleberTree(['A', 2], [[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: RS = RootSystem(['A', 2])
            sage: WS = RS.weight_space()
            sage: R = RS.root_space()
            sage: KT = KleberTree(['A', 2], [[1,1]])
            sage: n = KT(WS.sum_of_terms([(1,5), (2,2)]), R.zero())
            sage: n.depth
            1
            sage: n2 = KT(WS.sum_of_terms([(1,5), (2,2)]), R.zero(), n)
            sage: n2.depth
            2
        """
        depth = 0
        cur = self
        while cur is not None:
            depth += 1
            cur = cur.parent_node

        return depth

    def __cmp__(self, rhs):
        r"""
        Check whether two nodes are equal.

        TESTS::

            sage: RS = RootSystem(['A', 2])
            sage: WS = RS.weight_space()
            sage: R = RS.root_space()
            sage: KT = KleberTree(['A', 2], [[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: cmp(n2, n)
            1
            sage: n3 = KT(WS.sum_of_terms([(1,5), (2,2)]), R.zero(), n)
            sage: cmp(n2, n3)
            0
            sage: n3 = KT(WS.sum_of_terms([(1,5), (2,3)]), R.zero(), n)
            sage: cmp(n2, n3)
            -1
        """
        if isinstance(rhs, KleberTreeNode):
            if self.depth < rhs.depth:
                return -1
            elif self.depth > rhs.depth:
                return 1
            elif self.parent_node is not rhs.parent_node:
                return cmp(self.parent_node, rhs.parent_node)
            return cmp(self.weight, rhs.weight)
        return cmp(type(self), type(rhs))

    def _repr_(self):
        r"""
        Return the string representation of ``self``.

        EXAMPLES::

            sage: RS = RootSystem(['A', 3])
            sage: WS = RS.weight_space()
            sage: R = RS.root_space()
            sage: KT = KleberTree(['A', 2], [[1,1]])
            sage: node = sage.combinat.rigged_configurations.kleber_tree.KleberTreeNode(KT, WS.sum_of_terms([(1,2), (2,1), (3,1)]), R.sum_of_terms([(1,3), (3,3)])); node # indirect doctest
            Kleber tree node with weight [2, 1, 1] and upwards edge root [3, 0, 3]
        """
        ret_str = "Kleber tree node with weight " + repr(list(self.weight.to_vector()))
        ret_str += " and upwards edge root " + repr(list(self.up_root.to_vector()))
        return ret_str

    def _latex_(self):
        r"""
        Return latex representation of ``self``.

        TESTS::

            sage: RS = RootSystem(['A', 3])
            sage: WS = RS.weight_space()
            sage: R = RS.root_space()
            sage: KT = KleberTree(['A', 3], [[3,2], [1,1]])
            sage: node = sage.combinat.rigged_configurations.kleber_tree.KleberTreeNode(KT, WS.sum_of_terms([(1,4), (3,1)]), R.zero())
            sage: latex(node) # indirect doctest
            V_{4\omega_{1}+\omega_{3}}
            sage: node = sage.combinat.rigged_configurations.kleber_tree.KleberTreeNode(KT, WS.zero(), R.zero())
            sage: latex(node) # indirect doctest
            V_{0}
            sage: node = sage.combinat.rigged_configurations.kleber_tree.KleberTreeNode(KT, WS.sum_of_terms([(1,2)]), R.zero())
            sage: latex(node) # indirect doctest
            V_{2\omega_{1}}
        """
        retStr = "V_{"
        for pair in self.weight:
            if pair[1] > 1:
                retStr += repr(pair[1]) + "\omega_{" + repr(pair[0]) + "}+"
            elif pair[1] == 1:
                retStr += "\omega_{" + repr(pair[0]) + "}+"

        if retStr[-1] == '{':
            retStr += "0}"
        else:
            retStr = retStr[:-1] + "}"
        return retStr

class KleberTree(Parent, UniqueRepresentation):
    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 types `A_n`, `D_n`, `E_6`, `E_7`,
    and `E_8`.

    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 a Cartan type and a sequence of
    tuples `[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`.

    EXAMPLES::

        sage: KT = KleberTree(['E', 6], [[4, 2]])  # long time (9s on sage.math, 2012)
        sage: KT.cardinality()  # long time
        12
        sage: KT = KleberTree(['A', 3], [[3,2], [1,1]])  # long time
        sage: KT.list()  # long time
        [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]]
    """

    @staticmethod
    def __classcall_private__(cls, cartan_type, B):
        """
        Normalize the input arguments to ensure unique representation.

        EXAMPLES::

            sage: KT1 = KleberTree(CartanType(['A',3]), [[2,2]])
            sage: KT2 = KleberTree(['A',3], [(2,2)])
            sage: KT3 = KleberTree(['A',3], ((2,2),))
            sage: KT2 is KT1, KT3 is KT1
            (True, True)
        """
        cartan_type = CartanType(cartan_type)
        # Standardize B input into a tuple of tuples
        assert B is not None
        B = tuple(tuple(dim) for dim in B)
        return super(KleberTree, cls).__classcall__(cls, cartan_type, B)

    def __init__(self, cartan_type, B):
        r"""
        Construct a Kleber tree.

        INPUT:

        - ``cartan_type`` -- The 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.

        EXAMPLES::

            sage: KT = KleberTree(['D', 3], [[1,1], [1,1]]); KT
            Kleber tree of Cartan type ['D', 3] and root weight [2, 0, 0]
            sage: TestSuite(KT).run(skip="_test_elements")
        """
        Parent.__init__(self, category=FiniteEnumeratedSets())

        self._cartan_type = cartan_type
        self.dims = B
        n = self._cartan_type.n
        # Create an empty node at first step
        self.root = KleberTreeNode(self, self._cartan_type.root_system().weight_space().zero(),
                                   self._cartan_type.root_system().root_space().zero())
        full_list = [self.root] # The list of tree nodes

        # Convert the B values into an L matrix
        L = []
        for i in range(0, n):
            L.append([0])

        for dim in B:
            while len(L[0]) < dim[1]: # Add more columns if needed
                for row in L:
                    row.append(0)
            L[dim[0] - 1][dim[1] - 1] += 1 # The -1 is b/c of indexing

        # Perform a special case of the algorithm for the root node
        weight_basis = self._cartan_type.root_system().weight_space().basis()
        for a in range(n):
            self.root.weight += sum(L[a]) * weight_basis[a+1] # Add 1 for indexing
        new_children = []
        for new_child in self._children_root_iter():
            new_children.append(new_child)
            self.root.children.append(new_child)
            full_list.append(new_child)

        depth = 1
        growth = True

        while growth:
            growth = False
            depth += 1
            leaves = new_children
            new_children = []

            if depth <= len(L[0]):
                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[a+1] # Add 1 for indexing

                    if x in leaves:
                        for new_child in self._children_iter(x):
                            new_children.append(new_child)
            else:
                for x in leaves:
                    for new_child in self._children_iter(x):
                        new_children.append(new_child)

            # Connect the new children into the tree
            if len(new_children) > 0:
                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 _latex_(self, **options):
        r"""
        Return a latex representation of this Kleber tree.

        EXAMPLES::

            sage: KT = KleberTree(['D', 3], [[2,1], [2,1]])
            sage: KT._latex_()   #optional - dot2tex
            ...
            sage: view(KT, pdflatex=True, tightpage=True) #optional - dot2tex graphviz

        """
        if not have_dot2tex():
            print "dot2tex not available.  Install after running \'sage -sh\'"
            return
        G = self.digraph()
        G.set_latex_options(format="dot2tex", edge_labels=True, **options)
        return G._latex_()

    def _children_root_iter(self):
        """
        Iterate over the children of the root node.

        Helper iterator to iterate over all children, by generating and/or
        computing them, of the Kleber tree root.

        Right now we are just assuming that if a linear combination of positive
        roots keeps us in the Weyl chamber, then a shorter linear combination
        does as well.

        TESTS::

            sage: KT = KleberTree(['D', 3], [[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]
        """
        n = self._cartan_type.n
        cartan_matrix = self._cartan_type.cartan_matrix()
        pos_roots = list(self._cartan_type.root_system().root_space().positive_roots())
        WS = self._cartan_type.root_system().weight_space()
        num_pos_roots = len(pos_roots)
        roots_visited = []

        for root in pos_roots:
            # If we've already tried this root
            if root in roots_visited:
                continue

            # If not, then try it

            roots_visited.append(root)

            new_weight = self.root.weight - WS(root)

            if new_weight.is_dominant():
                yield KleberTreeNode(self, new_weight, root, self.root)
                root_stack = [root]
                index_stack = [0]

                # Now try all of its children
                while len(root_stack) > 0:
                    # If we've tried all of the roots, then back up
                    if index_stack[-1] == num_pos_roots:
                        root_stack.pop()
                        index_stack.pop()
                        continue

                    new_root = root_stack[-1] + pos_roots[index_stack[-1]]
                    index_stack[-1] += 1

                    # If we've already tried this root, move on to the next one
                    if new_root in roots_visited:
                        continue

                    roots_visited.append(new_root)

                    new_weight = self.root.weight - WS(new_root)

                    if new_weight.is_dominant():
                        yield KleberTreeNode(self, new_weight, new_root, self.root)
                        root_stack.append(new_root)
                        index_stack.append(0)

    def _children_iter(self, node):
        """
        Iterate over all children nodes.

        This is a helper iterator to iterate over all children, by generating
        and/or computing them, of a given Kleber tree node this isn't the root.

        We perform the dominance iteration by using the condition that that
        new root must be smaller than the previous root.

        INPUT:

        - ``node`` -- The current node in the tree whose children we want
            to generate

        TESTS::

            sage: KT = KleberTree(['D', 4], [[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]
        """
        n = self._cartan_type.n
        cartan_matrix = self._cartan_type.cartan_matrix()
        RS = self._cartan_type.root_system()
        WS = RS.weight_space()

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

        root_list = CartesianProduct(*L).list()
        root_list.pop(0) # First element is the zero element

        root_basis = RS.root_space().basis()
        for root in root_list:
            # Convert the list to an honest root in the root space
            converted_root = RS.root_space().zero()
            for i, val in enumerate(root):
                converted_root += val * root_basis[i+1] # Add 1 for indexing

            new_weight = node.weight - WS(converted_root)
            if new_weight.is_dominant():
                yield KleberTreeNode(self, new_weight, converted_root, node)

    def breadth_first_iter(self):
        r"""
        Iterate over all nodes in the tree following a breadth-first traversal.

        EXAMPLES::

            sage: KT = KleberTree(['A', 3], [[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, cur=None):
        r"""
        Iterate (recursively) over the nodes in the tree following a
        depth-first traversal.

        EXAMPLES::

            sage: KT = KleberTree(['A', 3], [[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]
            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]
        """

        if cur is None:
            cur = self.root

        yield cur

        for child in cur.children:
            for x in self.depth_first_iter(child):
                yield x

    __iter__ = breadth_first_iter

    def _repr_(self):
        """
        Return a text representation of this Kleber tree.

        EXAMPLES::

            sage: KT = KleberTree(['D', 4], [[2, 2]]); KT # indirect doctest
            Kleber tree of Cartan type ['D', 4] and root weight [0, 2, 0, 0]
        """
        ret_str = "Kleber tree of Cartan type " + repr(self._cartan_type) \
            + " and root weight " + repr(list(self.root.weight.to_vector()))
        return ret_str

    def cartan_type(self):
        r"""
        Return the Cartan type of this Kleber tree.

        EXAMPLES::

            sage: KT = KleberTree(['A', 3], [[1,1]])
            sage: KT.cartan_type()
            ['A', 3]
        """
        return(self._cartan_type)

    def digraph(self):
        r"""
        Return a DiGraph representation of this Kleber tree.

        EXAMPLES::

            sage: KT = KleberTree(['D', 4], [[2, 2]])
            sage: KT.digraph()
            Digraph on 3 vertices
        """
        d = {}
        for x in self:
            d[x] = {}
            if x.parent_node is None:
                continue
            d[x][x.parent_node] = tuple(x.up_root.to_vector())
        G = DiGraph(d)

        if have_dot2tex():
            G.set_latex_options(format="dot2tex", edge_labels=True)
                                # edge_options = lambda (u,v,label): ({"backward":label ==0}))
        return G

    def plot(self, **options):
        """
        Return the plot of self as a directed graph.

        EXAMPLES::

            sage: KT = KleberTree(['D', 4], [[2, 2]])
            sage: show_default(False) #do not show the plot by default
            sage: KT.plot()
            Graphics object consisting of 8 graphics primitives
        """
        return self.digraph().plot(edge_labels=True, vertex_size=0, **options)

    def _element_constructor_(self, node_weight, dominant_root, parent_node=None):
        """
        Construct a KleberTree.

        EXAMPLES::

            sage: RS = RootSystem(['A', 2])
            sage: WS = RS.weight_space()
            sage: R = RS.root_space()
            sage: KT = KleberTree(['A', 2], [[1,1]])
            sage: root = KT(WS.sum_of_terms([(1,5), (2,2)]), R.zero()); root # indirect doctest
            Kleber tree node with weight [5, 2] and upwards edge root [0, 0]
            sage: child = KT(WS.sum_of_terms([(1,5), (2,1)]), R.zero(), root); child # indirect doctest
            Kleber tree node with weight [5, 1] and upwards edge root [0, 0]
            sage: child.parent_node
            Kleber tree node with weight [5, 2] and upwards edge root [0, 0]

        """
        return self.element_class(self, node_weight, dominant_root, parent_node)

    Element = KleberTreeNode


r"""
Kleber tree

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:

- <NAME> (2011-05-03): Initial version

REFERENCES:

    .. [Kleber1] <NAME>.
        Combinatorial structure of finite dimensional representations of Yangians:
        the simply-laced case.
        Internat. Math. Res. Notices 1997. no. 4. 187-201.

    .. [Kleber2] <NAME>.
        Finite dimensional representations of quantum affine algebras.
        Ph.D. dissertation at University of California Berkeley. 1998.
        math.QA/9809087.

.. TODO:: Output the tree as a graph using the graph code

EXAMPLES::

    sage: KleberTree(['A', 3], [[3,2], [2,1], [1,1], [1,1]])
    Kleber tree of Cartan type ['A', 3] and root weight [2, 1, 2]
    sage: KleberTree(['D', 4], [[2,2]])
    Kleber tree of Cartan type ['D', 4] and root weight [0, 2, 0, 0]

TESTS::

    sage: KT = KleberTree(['A', 3], [[3,2], [2,1], [1,1], [1,1]])
    sage: for x in set(KT.list()): x
    ...
    Kleber tree node with weight [1, 0, 3] and upwards edge root [1, 1, 0]
    Kleber tree node with weight [0, 2, 2] and upwards edge root [1, 0, 0]
    Kleber tree node with weight [2, 1, 2] and upwards edge root [0, 0, 0]
    Kleber tree node with weight [2, 0, 0] and upwards edge root [0, 1, 1]
    Kleber tree node with weight [0, 0, 2] and upwards edge root [1, 1, 0]
    Kleber tree node with weight [0, 1, 0] and upwards edge root [0, 0, 1]
    Kleber tree node with weight [3, 0, 1] and upwards edge root [0, 1, 1]
    Kleber tree node with weight [0, 1, 0] and upwards edge root [1, 1, 1]
    Kleber tree node with weight [1, 1, 1] and upwards edge root [1, 1, 1]
    Kleber tree node with weight [0, 0, 2] and upwards edge root [2, 2, 1]

    sage: KT = KleberTree(['A', 7], [[3,2], [2,1], [1,1]])
    sage: KT
    Kleber tree of Cartan type ['A', 7] and root weight [1, 1, 2, 0, 0, 0, 0]
    sage: for x in set(KT.list()): x
    ...
    Kleber tree node with weight [1, 0, 1, 0, 1, 0, 0] and upwards edge root [1, 2, 2, 1, 0, 0, 0]
    Kleber tree node with weight [0, 0, 1, 0, 0, 1, 0] and upwards edge root [2, 3, 3, 2, 1, 0, 0]
    Kleber tree node with weight [1, 1, 2, 0, 0, 0, 0] and upwards edge root [0, 0, 0, 0, 0, 0, 0]
    Kleber tree node with weight [2, 0, 1, 1, 0, 0, 0] and upwards edge root [0, 1, 1, 0, 0, 0, 0]
    Kleber tree node with weight [1, 0, 0, 2, 0, 0, 0] and upwards edge root [0, 1, 1, 0, 0, 0, 0]
    Kleber tree node with weight [0, 0, 3, 0, 0, 0, 0] and upwards edge root [1, 1, 0, 0, 0, 0, 0]
    Kleber tree node with weight [0, 0, 0, 1, 1, 0, 0] and upwards edge root [1, 1, 1, 0, 0, 0, 0]
    Kleber tree node with weight [0, 1, 1, 1, 0, 0, 0] and upwards edge root [1, 1, 1, 0, 0, 0, 0]

"""

#*****************************************************************************
#       Copyright (C) 2011, 2012 <NAME> <<EMAIL>>
#
#  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 sage.misc.lazy_attribute import lazy_attribute
from sage.misc.latex import latex
from sage.rings.integer import Integer

from sage.structure.parent import Parent
from sage.structure.element import Element
from sage.structure.unique_representation import UniqueRepresentation
from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets

from sage.combinat.root_system.cartan_type import CartanType
from sage.combinat.cartesian_product import CartesianProduct

from sage.graphs.digraph import DiGraph
from sage.graphs.dot2tex_utils import have_dot2tex

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`.
    """

    def __init__(self, parent_obj, node_weight, dominant_root, parent_node=None):
        r"""
        Initialize the tree node.

        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

        TESTS::

            sage: RS = RootSystem(['A', 2])
            sage: WS = RS.weight_space()
            sage: R = RS.root_space()
            sage: KT = KleberTree(['A', 2], [[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: RS = RootSystem(['A', 2])
            sage: WS = RS.weight_space()
            sage: R = RS.root_space()
            sage: KT = KleberTree(['A', 2], [[1,1]])
            sage: n = KT(WS.sum_of_terms([(1,5), (2,2)]), R.zero())
            sage: n.depth
            1
            sage: n2 = KT(WS.sum_of_terms([(1,5), (2,2)]), R.zero(), n)
            sage: n2.depth
            2
        """
        depth = 0
        cur = self
        while cur is not None:
            depth += 1
            cur = cur.parent_node

        return depth

    def __cmp__(self, rhs):
        r"""
        Check whether two nodes are equal.

        TESTS::

            sage: RS = RootSystem(['A', 2])
            sage: WS = RS.weight_space()
            sage: R = RS.root_space()
            sage: KT = KleberTree(['A', 2], [[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: cmp(n2, n)
            1
            sage: n3 = KT(WS.sum_of_terms([(1,5), (2,2)]), R.zero(), n)
            sage: cmp(n2, n3)
            0
            sage: n3 = KT(WS.sum_of_terms([(1,5), (2,3)]), R.zero(), n)
            sage: cmp(n2, n3)
            -1
        """
        if isinstance(rhs, KleberTreeNode):
            if self.depth < rhs.depth:
                return -1
            elif self.depth > rhs.depth:
                return 1
            elif self.parent_node is not rhs.parent_node:
                return cmp(self.parent_node, rhs.parent_node)
            return cmp(self.weight, rhs.weight)
        return cmp(type(self), type(rhs))

    def _repr_(self):
        r"""
        Return the string representation of ``self``.

        EXAMPLES::

            sage: RS = RootSystem(['A', 3])
            sage: WS = RS.weight_space()
            sage: R = RS.root_space()
            sage: KT = KleberTree(['A', 2], [[1,1]])
            sage: node = sage.combinat.rigged_configurations.kleber_tree.KleberTreeNode(KT, WS.sum_of_terms([(1,2), (2,1), (3,1)]), R.sum_of_terms([(1,3), (3,3)])); node # indirect doctest
            Kleber tree node with weight [2, 1, 1] and upwards edge root [3, 0, 3]
        """
        ret_str = "Kleber tree node with weight " + repr(list(self.weight.to_vector()))
        ret_str += " and upwards edge root " + repr(list(self.up_root.to_vector()))
        return ret_str

    def _latex_(self):
        r"""
        Return latex representation of ``self``.

        TESTS::

            sage: RS = RootSystem(['A', 3])
            sage: WS = RS.weight_space()
            sage: R = RS.root_space()
            sage: KT = KleberTree(['A', 3], [[3,2], [1,1]])
            sage: node = sage.combinat.rigged_configurations.kleber_tree.KleberTreeNode(KT, WS.sum_of_terms([(1,4), (3,1)]), R.zero())
            sage: latex(node) # indirect doctest
            V_{4\omega_{1}+\omega_{3}}
            sage: node = sage.combinat.rigged_configurations.kleber_tree.KleberTreeNode(KT, WS.zero(), R.zero())
            sage: latex(node) # indirect doctest
            V_{0}
            sage: node = sage.combinat.rigged_configurations.kleber_tree.KleberTreeNode(KT, WS.sum_of_terms([(1,2)]), R.zero())
            sage: latex(node) # indirect doctest
            V_{2\omega_{1}}
        """
        retStr = "V_{"
        for pair in self.weight:
            if pair[1] > 1:
                retStr += repr(pair[1]) + "\omega_{" + repr(pair[0]) + "}+"
            elif pair[1] == 1:
                retStr += "\omega_{" + repr(pair[0]) + "}+"

        if retStr[-1] == '{':
            retStr += "0}"
        else:
            retStr = retStr[:-1] + "}"
        return retStr

class KleberTree(Parent, UniqueRepresentation):
    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 types `A_n`, `D_n`, `E_6`, `E_7`,
    and `E_8`.

    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 a Cartan type and a sequence of
    tuples `[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`.

    EXAMPLES::

        sage: KT = KleberTree(['E', 6], [[4, 2]])  # long time (9s on sage.math, 2012)
        sage: KT.cardinality()  # long time
        12
        sage: KT = KleberTree(['A', 3], [[3,2], [1,1]])  # long time
        sage: KT.list()  # long time
        [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]]
    """

    @staticmethod
    def __classcall_private__(cls, cartan_type, B):
        """
        Normalize the input arguments to ensure unique representation.

        EXAMPLES::

            sage: KT1 = KleberTree(CartanType(['A',3]), [[2,2]])
            sage: KT2 = KleberTree(['A',3], [(2,2)])
            sage: KT3 = KleberTree(['A',3], ((2,2),))
            sage: KT2 is KT1, KT3 is KT1
            (True, True)
        """
        cartan_type = CartanType(cartan_type)
        # Standardize B input into a tuple of tuples
        assert B is not None
        B = tuple(tuple(dim) for dim in B)
        return super(KleberTree, cls).__classcall__(cls, cartan_type, B)

    def __init__(self, cartan_type, B):
        r"""
        Construct a Kleber tree.

        INPUT:

        - ``cartan_type`` -- The 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.

        EXAMPLES::

            sage: KT = KleberTree(['D', 3], [[1,1], [1,1]]); KT
            Kleber tree of Cartan type ['D', 3] and root weight [2, 0, 0]
            sage: TestSuite(KT).run(skip="_test_elements")
        """
        Parent.__init__(self, category=FiniteEnumeratedSets())

        self._cartan_type = cartan_type
        self.dims = B
        n = self._cartan_type.n
        # Create an empty node at first step
        self.root = KleberTreeNode(self, self._cartan_type.root_system().weight_space().zero(),
                                   self._cartan_type.root_system().root_space().zero())
        full_list = [self.root] # The list of tree nodes

        # Convert the B values into an L matrix
        L = []
        for i in range(0, n):
            L.append([0])

        for dim in B:
            while len(L[0]) < dim[1]: # Add more columns if needed
                for row in L:
                    row.append(0)
            L[dim[0] - 1][dim[1] - 1] += 1 # The -1 is b/c of indexing

        # Perform a special case of the algorithm for the root node
        weight_basis = self._cartan_type.root_system().weight_space().basis()
        for a in range(n):
            self.root.weight += sum(L[a]) * weight_basis[a+1] # Add 1 for indexing
        new_children = []
        for new_child in self._children_root_iter():
            new_children.append(new_child)
            self.root.children.append(new_child)
            full_list.append(new_child)

        depth = 1
        growth = True

        while growth:
            growth = False
            depth += 1
            leaves = new_children
            new_children = []

            if depth <= len(L[0]):
                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[a+1] # Add 1 for indexing

                    if x in leaves:
                        for new_child in self._children_iter(x):
                            new_children.append(new_child)
            else:
                for x in leaves:
                    for new_child in self._children_iter(x):
                        new_children.append(new_child)

            # Connect the new children into the tree
            if len(new_children) > 0:
                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 _latex_(self, **options):
        r"""
        Return a latex representation of this Kleber tree.

        EXAMPLES::

            sage: KT = KleberTree(['D', 3], [[2,1], [2,1]])
            sage: KT._latex_()   #optional - dot2tex
            ...
            sage: view(KT, pdflatex=True, tightpage=True) #optional - dot2tex graphviz

        """
        if not have_dot2tex():
            print "dot2tex not available.  Install after running \'sage -sh\'"
            return
        G = self.digraph()
        G.set_latex_options(format="dot2tex", edge_labels=True, **options)
        return G._latex_()

    def _children_root_iter(self):
        """
        Iterate over the children of the root node.

        Helper iterator to iterate over all children, by generating and/or
        computing them, of the Kleber tree root.

        Right now we are just assuming that if a linear combination of positive
        roots keeps us in the Weyl chamber, then a shorter linear combination
        does as well.

        TESTS::

            sage: KT = KleberTree(['D', 3], [[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]
        """
        n = self._cartan_type.n
        cartan_matrix = self._cartan_type.cartan_matrix()
        pos_roots = list(self._cartan_type.root_system().root_space().positive_roots())
        WS = self._cartan_type.root_system().weight_space()
        num_pos_roots = len(pos_roots)
        roots_visited = []

        for root in pos_roots:
            # If we've already tried this root
            if root in roots_visited:
                continue

            # If not, then try it

            roots_visited.append(root)

            new_weight = self.root.weight - WS(root)

            if new_weight.is_dominant():
                yield KleberTreeNode(self, new_weight, root, self.root)
                root_stack = [root]
                index_stack = [0]

                # Now try all of its children
                while len(root_stack) > 0:
                    # If we've tried all of the roots, then back up
                    if index_stack[-1] == num_pos_roots:
                        root_stack.pop()
                        index_stack.pop()
                        continue

                    new_root = root_stack[-1] + pos_roots[index_stack[-1]]
                    index_stack[-1] += 1

                    # If we've already tried this root, move on to the next one
                    if new_root in roots_visited:
                        continue

                    roots_visited.append(new_root)

                    new_weight = self.root.weight - WS(new_root)

                    if new_weight.is_dominant():
                        yield KleberTreeNode(self, new_weight, new_root, self.root)
                        root_stack.append(new_root)
                        index_stack.append(0)

    def _children_iter(self, node):
        """
        Iterate over all children nodes.

        This is a helper iterator to iterate over all children, by generating
        and/or computing them, of a given Kleber tree node this isn't the root.

        We perform the dominance iteration by using the condition that that
        new root must be smaller than the previous root.

        INPUT:

        - ``node`` -- The current node in the tree whose children we want
            to generate

        TESTS::

            sage: KT = KleberTree(['D', 4], [[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]
        """
        n = self._cartan_type.n
        cartan_matrix = self._cartan_type.cartan_matrix()
        RS = self._cartan_type.root_system()
        WS = RS.weight_space()

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

        root_list = CartesianProduct(*L).list()
        root_list.pop(0) # First element is the zero element

        root_basis = RS.root_space().basis()
        for root in root_list:
            # Convert the list to an honest root in the root space
            converted_root = RS.root_space().zero()
            for i, val in enumerate(root):
                converted_root += val * root_basis[i+1] # Add 1 for indexing

            new_weight = node.weight - WS(converted_root)
            if new_weight.is_dominant():
                yield KleberTreeNode(self, new_weight, converted_root, node)

    def breadth_first_iter(self):
        r"""
        Iterate over all nodes in the tree following a breadth-first traversal.

        EXAMPLES::

            sage: KT = KleberTree(['A', 3], [[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, cur=None):
        r"""
        Iterate (recursively) over the nodes in the tree following a
        depth-first traversal.

        EXAMPLES::

            sage: KT = KleberTree(['A', 3], [[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]
            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]
        """

        if cur is None:
            cur = self.root

        yield cur

        for child in cur.children:
            for x in self.depth_first_iter(child):
                yield x

    __iter__ = breadth_first_iter

    def _repr_(self):
        """
        Return a text representation of this Kleber tree.

        EXAMPLES::

            sage: KT = KleberTree(['D', 4], [[2, 2]]); KT # indirect doctest
            Kleber tree of Cartan type ['D', 4] and root weight [0, 2, 0, 0]
        """
        ret_str = "Kleber tree of Cartan type " + repr(self._cartan_type) \
            + " and root weight " + repr(list(self.root.weight.to_vector()))
        return ret_str

    def cartan_type(self):
        r"""
        Return the Cartan type of this Kleber tree.

        EXAMPLES::

            sage: KT = KleberTree(['A', 3], [[1,1]])
            sage: KT.cartan_type()
            ['A', 3]
        """
        return(self._cartan_type)

    def digraph(self):
        r"""
        Return a DiGraph representation of this Kleber tree.

        EXAMPLES::

            sage: KT = KleberTree(['D', 4], [[2, 2]])
            sage: KT.digraph()
            Digraph on 3 vertices
        """
        d = {}
        for x in self:
            d[x] = {}
            if x.parent_node is None:
                continue
            d[x][x.parent_node] = tuple(x.up_root.to_vector())
        G = DiGraph(d)

        if have_dot2tex():
            G.set_latex_options(format="dot2tex", edge_labels=True)
                                # edge_options = lambda (u,v,label): ({"backward":label ==0}))
        return G

    def plot(self, **options):
        """
        Return the plot of self as a directed graph.

        EXAMPLES::

            sage: KT = KleberTree(['D', 4], [[2, 2]])
            sage: show_default(False) #do not show the plot by default
            sage: KT.plot()
            Graphics object consisting of 8 graphics primitives
        """
        return self.digraph().plot(edge_labels=True, vertex_size=0, **options)

    def _element_constructor_(self, node_weight, dominant_root, parent_node=None):
        """
        Construct a KleberTree.

        EXAMPLES::

            sage: RS = RootSystem(['A', 2])
            sage: WS = RS.weight_space()
            sage: R = RS.root_space()
            sage: KT = KleberTree(['A', 2], [[1,1]])
            sage: root = KT(WS.sum_of_terms([(1,5), (2,2)]), R.zero()); root # indirect doctest
            Kleber tree node with weight [5, 2] and upwards edge root [0, 0]
            sage: child = KT(WS.sum_of_terms([(1,5), (2,1)]), R.zero(), root); child # indirect doctest
            Kleber tree node with weight [5, 1] and upwards edge root [0, 0]
            sage: child.parent_node
            Kleber tree node with weight [5, 2] and upwards edge root [0, 0]

        """
        return self.element_class(self, node_weight, dominant_root, parent_node)

    Element = KleberTreeNode


Kleber tree  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:  - <NAME> (2011-05-03): Initial version  REFERENCES:      .. [Kleber1] <NAME>.         Combinatorial structure of finite dimensional representations of Yangians:         the simply-laced case.         Internat. Math. Res. Notices 1997. no. 4. 187-201.      .. [Kleber2] <NAME>.         Finite dimensional representations of quantum affine algebras.         Ph.D. dissertation at University of California Berkeley. 1998.         math.QA/9809087.  .. TODO:: Output the tree as a graph using the graph code  EXAMPLES::      sage: KleberTree(['A', 3], [[3,2], [2,1], [1,1], [1,1]])     Kleber tree of Cartan type ['A', 3] and root weight [2, 1, 2]     sage: KleberTree(['D', 4], [[2,2]])     Kleber tree of Cartan type ['D', 4] and root weight [0, 2, 0, 0]  TESTS::      sage: KT = KleberTree(['A', 3], [[3,2], [2,1], [1,1], [1,1]])     sage: for x in set(KT.list()): x     ...     Kleber tree node with weight [1, 0, 3] and upwards edge root [1, 1, 0]     Kleber tree node with weight [0, 2, 2] and upwards edge root [1, 0, 0]     Kleber tree node with weight [2, 1, 2] and upwards edge root [0, 0, 0]     Kleber tree node with weight [2, 0, 0] and upwards edge root [0, 1, 1]     Kleber tree node with weight [0, 0, 2] and upwards edge root [1, 1, 0]     Kleber tree node with weight [0, 1, 0] and upwards edge root [0, 0, 1]     Kleber tree node with weight [3, 0, 1] and upwards edge root [0, 1, 1]     Kleber tree node with weight [0, 1, 0] and upwards edge root [1, 1, 1]     Kleber tree node with weight [1, 1, 1] and upwards edge root [1, 1, 1]     Kleber tree node with weight [0, 0, 2] and upwards edge root [2, 2, 1]      sage: KT = KleberTree(['A', 7], [[3,2], [2,1], [1,1]])     sage: KT     Kleber tree of Cartan type ['A', 7] and root weight [1, 1, 2, 0, 0, 0, 0]     sage: for x in set(KT.list()): x     ...     Kleber tree node with weight [1, 0, 1, 0, 1, 0, 0] and upwards edge root [1, 2, 2, 1, 0, 0, 0]     Kleber tree node with weight [0, 0, 1, 0, 0, 1, 0] and upwards edge root [2, 3, 3, 2, 1, 0, 0]     Kleber tree node with weight [1, 1, 2, 0, 0, 0, 0] and upwards edge root [0, 0, 0, 0, 0, 0, 0]     Kleber tree node with weight [2, 0, 1, 1, 0, 0, 0] and upwards edge root [0, 1, 1, 0, 0, 0, 0]     Kleber tree node with weight [1, 0, 0, 2, 0, 0, 0] and upwards edge root [0, 1, 1, 0, 0, 0, 0]     Kleber tree node with weight [0, 0, 3, 0, 0, 0, 0] and upwards edge root [1, 1, 0, 0, 0, 0, 0]     Kleber tree node with weight [0, 0, 0, 1, 1, 0, 0] and upwards edge root [1, 1, 1, 0, 0, 0, 0]     Kleber tree node with weight [0, 1, 1, 1, 0, 0, 0] and upwards edge root [1, 1, 1, 0, 0, 0, 0] #***************************************************************************** #       Copyright (C) 2011, 2012 <NAME> <<EMAIL>> # #  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/ #***************************************************************************** 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`. Initialize the tree node.          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          TESTS::              sage: RS = RootSystem(['A', 2])             sage: WS = RS.weight_space()             sage: R = RS.root_space()             sage: KT = KleberTree(['A', 2], [[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() Return the depth of this node in the tree.          EXAMPLES::              sage: RS = RootSystem(['A', 2])             sage: WS = RS.weight_space()             sage: R = RS.root_space()             sage: KT = KleberTree(['A', 2], [[1,1]])             sage: n = KT(WS.sum_of_terms([(1,5), (2,2)]), R.zero())             sage: n.depth             1             sage: n2 = KT(WS.sum_of_terms([(1,5), (2,2)]), R.zero(), n)             sage: n2.depth             2 Check whether two nodes are equal.          TESTS::              sage: RS = RootSystem(['A', 2])             sage: WS = RS.weight_space()             sage: R = RS.root_space()             sage: KT = KleberTree(['A', 2], [[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: cmp(n2, n)             1             sage: n3 = KT(WS.sum_of_terms([(1,5), (2,2)]), R.zero(), n)             sage: cmp(n2, n3)             0             sage: n3 = KT(WS.sum_of_terms([(1,5), (2,3)]), R.zero(), n)             sage: cmp(n2, n3)             -1 Return the string representation of ``self``.          EXAMPLES::              sage: RS = RootSystem(['A', 3])             sage: WS = RS.weight_space()             sage: R = RS.root_space()             sage: KT = KleberTree(['A', 2], [[1,1]])             sage: node = sage.combinat.rigged_configurations.kleber_tree.KleberTreeNode(KT, WS.sum_of_terms([(1,2), (2,1), (3,1)]), R.sum_of_terms([(1,3), (3,3)])); node # indirect doctest             Kleber tree node with weight [2, 1, 1] and upwards edge root [3, 0, 3] Return latex representation of ``self``.          TESTS::              sage: RS = RootSystem(['A', 3])             sage: WS = RS.weight_space()             sage: R = RS.root_space()             sage: KT = KleberTree(['A', 3], [[3,2], [1,1]])             sage: node = sage.combinat.rigged_configurations.kleber_tree.KleberTreeNode(KT, WS.sum_of_terms([(1,4), (3,1)]), R.zero())             sage: latex(node) # indirect doctest             V_{4\omega_{1}+\omega_{3}}             sage: node = sage.combinat.rigged_configurations.kleber_tree.KleberTreeNode(KT, WS.zero(), R.zero())             sage: latex(node) # indirect doctest             V_{0}             sage: node = sage.combinat.rigged_configurations.kleber_tree.KleberTreeNode(KT, WS.sum_of_terms([(1,2)]), R.zero())             sage: latex(node) # indirect doctest             V_{2\omega_{1}} 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 types `A_n`, `D_n`, `E_6`, `E_7`,     and `E_8`.      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 a Cartan type and a sequence of     tuples `[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`.      EXAMPLES::          sage: KT = KleberTree(['E', 6], [[4, 2]])  # long time (9s on sage.math, 2012)         sage: KT.cardinality()  # long time         12         sage: KT = KleberTree(['A', 3], [[3,2], [1,1]])  # long time         sage: KT.list()  # long time         [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]] Normalize the input arguments to ensure unique representation.          EXAMPLES::              sage: KT1 = KleberTree(CartanType(['A',3]), [[2,2]])             sage: KT2 = KleberTree(['A',3], [(2,2)])             sage: KT3 = KleberTree(['A',3], ((2,2),))             sage: KT2 is KT1, KT3 is KT1             (True, True) # Standardize B input into a tuple of tuples Construct a Kleber tree.          INPUT:          - ``cartan_type`` -- The 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.          EXAMPLES::              sage: KT = KleberTree(['D', 3], [[1,1], [1,1]]); KT             Kleber tree of Cartan type ['D', 3] and root weight [2, 0, 0]             sage: TestSuite(KT).run(skip="_test_elements") # Create an empty node at first step # The list of tree nodes # Convert the B values into an L matrix # Add more columns if needed # The -1 is b/c of indexing # Perform a special case of the algorithm for the root node # Add 1 for indexing # Subtract 1 for indexing # Add 1 for indexing # Connect the new children into the tree Return a latex representation of this Kleber tree.          EXAMPLES::              sage: KT = KleberTree(['D', 3], [[2,1], [2,1]])             sage: KT._latex_()   #optional - dot2tex             ...             sage: view(KT, pdflatex=True, tightpage=True) #optional - dot2tex graphviz Iterate over the children of the root node.          Helper iterator to iterate over all children, by generating and/or         computing them, of the Kleber tree root.          Right now we are just assuming that if a linear combination of positive         roots keeps us in the Weyl chamber, then a shorter linear combination         does as well.          TESTS::              sage: KT = KleberTree(['D', 3], [[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] # If we've already tried this root # If not, then try it # Now try all of its children # If we've tried all of the roots, then back up # If we've already tried this root, move on to the next one Iterate over all children nodes.          This is a helper iterator to iterate over all children, by generating         and/or computing them, of a given Kleber tree node this isn't the root.          We perform the dominance iteration by using the condition that that         new root must be smaller than the previous root.          INPUT:          - ``node`` -- The current node in the tree whose children we want             to generate          TESTS::              sage: KT = KleberTree(['D', 4], [[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] # First element is the zero element # Convert the list to an honest root in the root space # Add 1 for indexing Iterate over all nodes in the tree following a breadth-first traversal.          EXAMPLES::              sage: KT = KleberTree(['A', 3], [[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] Iterate (recursively) over the nodes in the tree following a         depth-first traversal.          EXAMPLES::              sage: KT = KleberTree(['A', 3], [[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]             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] Return a text representation of this Kleber tree.          EXAMPLES::              sage: KT = KleberTree(['D', 4], [[2, 2]]); KT # indirect doctest             Kleber tree of Cartan type ['D', 4] and root weight [0, 2, 0, 0] Return the Cartan type of this Kleber tree.          EXAMPLES::              sage: KT = KleberTree(['A', 3], [[1,1]])             sage: KT.cartan_type()             ['A', 3] Return a DiGraph representation of this Kleber tree.          EXAMPLES::              sage: KT = KleberTree(['D', 4], [[2, 2]])             sage: KT.digraph()             Digraph on 3 vertices # edge_options = lambda (u,v,label): ({"backward":label ==0})) Return the plot of self as a directed graph.          EXAMPLES::              sage: KT = KleberTree(['D', 4], [[2, 2]])             sage: show_default(False) #do not show the plot by default             sage: KT.plot()             Graphics object consisting of 8 graphics primitives Construct a KleberTree.          EXAMPLES::              sage: RS = RootSystem(['A', 2])             sage: WS = RS.weight_space()             sage: R = RS.root_space()             sage: KT = KleberTree(['A', 2], [[1,1]])             sage: root = KT(WS.sum_of_terms([(1,5), (2,2)]), R.zero()); root # indirect doctest             Kleber tree node with weight [5, 2] and upwards edge root [0, 0]             sage: child = KT(WS.sum_of_terms([(1,5), (2,1)]), R.zero(), root); child # indirect doctest             Kleber tree node with weight [5, 1] and upwards edge root [0, 0]             sage: child.parent_node             Kleber tree node with weight [5, 2] and upwards edge root [0, 0]