text: 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: 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, 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: 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 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 sage.misc.lazy_attribute import lazy_attribute
  from sage.misc.cachefunc import cached_method
  from sage.misc.latex import latex
  from sage.rings.arith import binomial
  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
  
  ######################################
  # 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 len(tree_node.children) == 0:
          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 xrange(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_space()
              sage: R = RS.root_space()
              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_space()
              sage: R = RS.root_space()
              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 [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 [3, 0, 1] and upwards edge root [0, 1, 1], 1)
              (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)
          CM = self.parent()._classical_ct.cartan_matrix()
          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 __cmp__(self, rhs):
          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_space()
              sage: R = RS.root_space()
              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: 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: from sage.combinat.rigged_configurations.kleber_tree import KleberTree
              sage: RS = RootSystem(['A', 3])
              sage: WS = RS.weight_space()
              sage: R = RS.root_space()
              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_space()
              sage: R = RS.root_space()
              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(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 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
      """
      @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(map(tuple, 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
          self._build_tree(B)
          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 len(options) == 0:
              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, B):
          """
          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
          """
          # Create an empty node at first step
          self.root = KleberTreeNode(self, self._classical_ct.root_system().weight_space().zero(),
                                     self._classical_ct.root_system().root_space().zero())
          full_list = [self.root] # The list of tree nodes
  
          n = self._classical_ct.rank()
  
          # Convert the B values into an L matrix
          L = []
          for i in range(0, n):
              L.append([0])
  
          for r,s in B:
              while len(L[0]) < s: # Add more columns if needed
                  for row in L:
                      row.append(0)
              L[r - 1][s - 1] += 1 # The -1 is b/c of indexing
  
          # Perform a special case of the algorithm for the root node
          weight_basis = self._classical_ct.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():
              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
  
          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):
                              if not self._prune(new_child, depth):
                                  new_children.append(new_child)
              else:
                  for x in leaves:
                      for new_child in self._children_iter(x):
                          if not self._prune(new_child, depth):
                              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 _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: 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]
          """
          pos_roots = list(self._classical_ct.root_system().root_space().positive_roots())
          WS = self._classical_ct.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: 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: 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]
          """
          RS = self._classical_ct.root_system().root_space()
          WS = self._classical_ct.root_system().weight_space()
  
          L = [range(val + 1) for val in node.up_root.to_vector()]
  
          for root in CartesianProduct(*L).list()[1:]: # First element is the zero element
              # Convert the list to an honest root in the root space
              converted_root = RS.sum_of_terms([[i+1, val] for i, val in enumerate(root)])
  
              new_weight = node.weight - WS(converted_root)
              if new_weight.is_dominant():
                  yield KleberTreeNode(self, new_weight, converted_root, 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]
              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 self._depth_first_iter(None)
  
      def _depth_first_iter(self, cur):
          r"""
          Helper recursive function used in depth-first iteration.
  
          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(None): 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: from sage.combinat.rigged_configurations.kleber_tree import KleberTree
              sage: KleberTree(['D', 4, 1], [[2, 2]]) # indirect doctest
              Kleber tree of Cartan type ['D', 4, 1] and B = ((2, 2),)
          """
          return "Kleber tree of Cartan type %s and B = %s"%(repr(self._cartan_type), self.B)
  
      def cartan_type(self):
          r"""
          Return the Cartan type of this Kleber tree.
  
          EXAMPLES::
  
              sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree
              sage: KT = KleberTree(['A', 3, 1], [[1,1]])
              sage: KT.cartan_type()
              ['A', 3, 1]
          """
          return self._cartan_type
  
      def digraph(self):
          r"""
          Return a DiGraph representation of this Kleber tree.
  
          EXAMPLES::
  
              sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree
              sage: KT = KleberTree(['D', 4, 1], [[2, 2]])
              sage: KT.digraph() # optional - dot2tex, graphviz
              Digraph on 3 vertices
          """
          d = {}
          for x in self.breadth_first_iter():
              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: from sage.combinat.rigged_configurations.kleber_tree import KleberTree
              sage: KT = KleberTree(['D', 4, 1], [[2, 2]])
              sage: print(KT.plot()) # optional - dot2tex, graphviz
              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 Kleber tree node.
  
          EXAMPLES::
  
              sage: from sage.combinat.rigged_configurations.kleber_tree import KleberTree
              sage: RS = RootSystem(['A', 2])
              sage: WS = RS.weight_space()
              sage: R = RS.root_space()
              sage: KT = KleberTree(['A', 2, 1], [[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
  
  class VirtualKleberTree(KleberTree):
      """
      A virtual Kleber tree.
  
      We can use a modified version of the Kleber algorithm called the virtual
      Kleber algorithm [OSS03]_ to compute all admissible rigged configurations
      for non-simply-laced types. This uses the following embeddings
      into the simply-laced types:
  
      .. MATH::
  
          C_n^{(1)}, A_{2n}^{(2)}, A_{2n}^{(2)\dagger}, D_{n+1}^{(2)}
          \hookrightarrow A_{2n-1}^{(1)}
  
          A_{2n-1}^{(2)}, B_n^{(1)} \hookrightarrow D_{n+1}^{(1)}
  
          E_6^{(2)}, F_4^{(1)} \hookrightarrow E_6^{(1)}
  
          D_4^{(3)}, G_2^{(1)} \hookrightarrow D_4^{(1)}
  
      One then selects the subset of admissible nodes which are translates of
      the virtual requirements. In the graph, the selected nodes are indicated
      by brackets `[]`.
  
      .. NOTE::
  
          Because these are virtual nodes, all information is given
          in the corresponding simply-laced type.
  
      .. SEEALSO::
  
          For more on the Kleber algorithm, see :class:`KleberTree`.
  
      REFERENCES:
  
      .. [OSS03] Masato Okado, Anne Schilling, and Mark Shimozono.
         *Virtual crystals and Klebers algorithm*. Commun. Math. Phys. **238**
         (2003). 187-209. :arxiv:`math.QA/0209082`.
  
      INPUT:
  
      - ``cartan_type`` -- an affine non-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
  
      EXAMPLES::
  
          sage: from sage.combinat.rigged_configurations.kleber_tree import VirtualKleberTree
          sage: KT = VirtualKleberTree(['C', 4, 1], [[2,2]])
          sage: KT.cardinality()
          3
          sage: KT.base_tree().cardinality()
          6
          sage: KT = VirtualKleberTree(['C', 4, 1], [[4,5]])
          sage: KT.cardinality()
          1
          sage: KT = VirtualKleberTree(['D', 5, 2], [[2,1], [1,1]])
          sage: KT.cardinality()
          8
          sage: KT = VirtualKleberTree(CartanType(['A', 4, 2]).dual(), [[1,1], [2,2]])
          sage: KT.cardinality()
          15
      """
      @staticmethod
      def __classcall_private__(cls, cartan_type, B):
          """
          Normalize the input arguments to ensure unique representation.
  
          EXAMPLES::
  
              sage: from sage.combinat.rigged_configurations.kleber_tree import VirtualKleberTree
              sage: KT1 = VirtualKleberTree(CartanType(['C',3,1]).as_folding(), [[2,2]])
              sage: KT2 = VirtualKleberTree(CartanType(['C',3,1]), [(2,2)])
              sage: KT3 = VirtualKleberTree(['C',3,1], ((2,2),))
              sage: KT2 is KT1, KT3 is KT1
              (True, True)
          """
          cartan_type = CartanType(cartan_type)
          # Standardize B input into a tuple of tuples
          B = tuple(map(tuple, B))
          if cartan_type.type() == 'BC' or cartan_type.dual().type() == 'BC':
              # Types A_{2n}^{(2)} and its dual
              return KleberTreeTypeA2Even(cartan_type, B)
          if cartan_type.classical().is_simply_laced():
              raise ValueError("use KleberTree for simply-laced types")
          return super(VirtualKleberTree, cls).__classcall__(cls, cartan_type, B)
  
      def __init__(self, cartan_type, B):
          """
          Initialize ``self``.
  
          EXAMPLES::
  
              sage: from sage.combinat.rigged_configurations.kleber_tree import VirtualKleberTree
              sage: KT = VirtualKleberTree(['C',4,1], [[2,2]])
              sage: TestSuite(KT).run(skip="_test_elements")
          """
          self._folded_ct = cartan_type.as_folding()
          virtual_dims = []
          self.base_dims = B
          sigma = self._folded_ct.folding_orbit()
          gamma = self._folded_ct.scaling_factors()
          classical_ct = self._folded_ct.folding_of().classical()
          for r,s in B:
              for i in sigma[r]:
                  virtual_dims.append([i, s * gamma[r]])
  
          KleberTree.__init__(self, cartan_type, virtual_dims, classical_ct)
  
      def _repr_(self):
          """
          Return a text representation of this Kleber tree.
  
          EXAMPLES::
  
              sage: from sage.combinat.rigged_configurations.kleber_tree import VirtualKleberTree
              sage: VirtualKleberTree(['C', 4, 1], [[2, 2]])
              Virtual Kleber tree of Cartan type ['C', 4, 1] and B = ((2, 2),)
          """
          return "Virtual Kleber tree of Cartan type %s and B = %s"%(repr(self._cartan_type), self.base_dims)
  
      def _prune(self, new_child, depth):
          r"""
          Return ``True`` if we are to prune the tree at ``new_child``.
  
          Suppose `\lambda` is the weight of the child we want to add at depth
          `\ell`. We prune ``new_child`` if either of the following conditions
          are not satisfied:
  
          1. `(\lambda \mid \alpha_a) = (\lambda \mid \alpha_b)` if `a` and `b`
             are in the same `\sigma`-orbit.
          2. If `\ell - 1 \notin \gamma_a \ZZ`, then the `a`-th component of
             ``up_root`` of ``new_child`` must equal the `a`-th component of
             ``up_root`` of its ``parent_node``. Note that from condition 1,
             we only need to check one such `a` from each `\sigma`-orbit.
  
          These conditions are equivalent to Definition 4.1 in [OSS03]_.
  
          EXAMPLES::
  
              sage: from sage.combinat.rigged_configurations.kleber_tree import VirtualKleberTree
              sage: RS = RootSystem(['A', 3])
              sage: WS = RS.weight_space()
              sage: R = RS.root_space()
              sage: KT = VirtualKleberTree(['C',2,1], [[1,2],[1,1],[2,1]])
              sage: x = KT(WS.sum_of_terms([(1,1), (2,1), (3,3)]), R.sum_of_terms([(1,2),(2,2),(3,1)]), KT.root)
              sage: KT._prune(x, 1)
              True
          """
          sigma = self._folded_ct._orbit
          for orbit in sigma[1:]:
              start = new_child.weight[orbit[0]]
              for i in orbit[1:]:
                  if new_child.weight[i] != start:
                      return True
          gamma = self._folded_ct.scaling_factors()
          for a in range(1, len(gamma)):
              if (depth - 1) % gamma[a] != 0 and new_child.up_root[sigma[a][0]] \
                != new_child.parent_node.up_root[sigma[a][0]]:
                  return True
          return False
  
      def breadth_first_iter(self, all_nodes=False):
          r"""
          Iterate over all nodes in the tree following a breadth-first traversal.
  
          INPUT:
  
          - ``all_nodes`` -- (default: ``False``) if ``True``, output all
            nodes in the tree
  
          EXAMPLES::
  
              sage: from sage.combinat.rigged_configurations.kleber_tree import VirtualKleberTree
              sage: KT = VirtualKleberTree(['C', 2, 1], [[1,1], [2,1]])
              sage: for x in KT.breadth_first_iter(): x
              Kleber tree node with weight [1, 2, 1] and upwards edge root [0, 0, 0]
              Kleber tree node with weight [1, 0, 1] and upwards edge root [0, 1, 0]
              sage: for x in KT.breadth_first_iter(True): x
              Kleber tree node with weight [1, 2, 1] and upwards edge root [0, 0, 0]
              Kleber tree node with weight [0, 2, 0] and upwards edge root [1, 1, 1]
              Kleber tree node with weight [1, 0, 1] and upwards edge root [0, 1, 0]
          """
          s_factors = self._folded_ct.scaling_factors()
          gamma = max(s_factors)
          # Subtract 1 for indexing
          if gamma > 1:
              sigma = self._folded_ct.folding_orbit()
              L = [sigma[a][0] for a in range(1, len(s_factors))
                   if s_factors[a] == gamma]
          else:
              L = []
  
          for x in KleberTree.breadth_first_iter(self):
              if all_nodes or (x.depth) % gamma == 0 or all(x.up_root[a] == 0 for a in L):
                  yield x
  
      def depth_first_iter(self, all_nodes=False):
          r"""
          Iterate (recursively) over the nodes in the tree following a
          depth-first traversal.
  
          INPUT:
  
          - ``all_nodes`` -- (default: ``False``) if ``True``, output all
            nodes in the tree
  
          EXAMPLES::
  
              sage: from sage.combinat.rigged_configurations.kleber_tree import VirtualKleberTree
              sage: KT = VirtualKleberTree(['C', 2, 1], [[1,1], [2,1]])
              sage: for x in KT.depth_first_iter(): x
              Kleber tree node with weight [1, 2, 1] and upwards edge root [0, 0, 0]
              Kleber tree node with weight [1, 0, 1] and upwards edge root [0, 1, 0]
              sage: for x in KT.depth_first_iter(True): x
              Kleber tree node with weight [1, 2, 1] and upwards edge root [0, 0, 0]
              Kleber tree node with weight [0, 2, 0] and upwards edge root [1, 1, 1]
              Kleber tree node with weight [1, 0, 1] and upwards edge root [0, 1, 0]
          """
          s_factors = self._folded_ct.scaling_factors()
          gamma = max(s_factors)
          # Subtract 1 for indexing
          if gamma > 1:
              sigma = self._folded_ct.folding_orbit()
              L = [sigma[a][0] for a in range(1, len(s_factors))
                   if s_factors[a] == gamma]
          else:
              L = []
  
          for x in self._depth_first_iter(None):
              if all_nodes or (x.depth) % gamma == 0 or all(x.up_root[a] == 0 for a in L):
                  yield x
  
      __iter__ = breadth_first_iter
  
      def base_tree(self):
          """
          Return the underlying virtual Kleber tree associated to ``self``.
  
          EXAMPLES::
  
              sage: from sage.combinat.rigged_configurations.kleber_tree import VirtualKleberTree
              sage: KT = VirtualKleberTree(['C', 4, 1], [[2,2]])
              sage: KT.base_tree()
              Kleber tree of Cartan type ['A', 7, 1] and B = ((2, 2), (6, 2))
          """
          return KleberTree(self._folded_ct.folding_of(), self.B)
  
  class KleberTreeTypeA2Even(VirtualKleberTree):
      r"""
      Kleber tree for types `A_{2n}^{(2)}` and `A_{2n}^{(2)\dagger}`.
  
      Note that here for `A_{2n}^{(2)}` we use `\tilde{\gamma}_a` in place of
      `\gamma_a` in constructing the virtual Kleber tree, and so we end up
      selecting all nodes since `\tilde{\gamma}_a = 1` for all `a \in
      \overline{I}`. For type `A_{2n}^{(2)\dagger}`, we have `\gamma_a = 1`
      for all `a \in \overline{I}`.
  
      .. SEEALSO::
  
          :class:`VirtualKleberTree`
      """
      @staticmethod
      def __classcall_private__(cls, cartan_type, B):
          """
          Normalize the input arguments to ensure unique representation.
  
          EXAMPLES::
  
              sage: from sage.combinat.rigged_configurations.kleber_tree import VirtualKleberTree
              sage: KT1 = VirtualKleberTree(CartanType(['A',6,2]), [[2,2]])
              sage: KT2 = VirtualKleberTree(['A',6,2], [(2,2)])
              sage: KT3 = VirtualKleberTree(['A',6,2], ((2,2),))
              sage: KT2 is KT1, KT3 is KT1
              (True, True)
          """
          cartan_type = CartanType(cartan_type)
          # Standardize B input into a tuple of tuples
          B = tuple(map(tuple, B))
          return super(KleberTreeTypeA2Even, cls).__classcall__(cls, cartan_type, B)
  
      def __init__(self, cartan_type, B):
          """
          Initialize ``self``.
  
          EXAMPLES::
  
              sage: from sage.combinat.rigged_configurations.kleber_tree import VirtualKleberTree
              sage: KT = VirtualKleberTree(['A',6,2], [[2,2]]); KT
              Virtual Kleber tree of Cartan type ['BC', 3, 2] and B = ((2, 2),)
              sage: TestSuite(KT).run(skip="_test_elements")
          """
          self._folded_ct = cartan_type.as_folding()
          virtual_dims = []
          n = cartan_type.classical().rank()
          self.base_dims = B
          sigma = self._folded_ct.folding_orbit()
          classical_ct = self._folded_ct.folding_of().classical()
          for r,s in B:
              if r == n:
                  virtual_dims.extend([[n, s], [n, s]])
              else:
                  for i in sigma[r]:
                      virtual_dims.append([i, s])
  
          KleberTree.__init__(self, cartan_type, virtual_dims, classical_ct)
  
      def __iter__(self):
          """
          Iterate over all of the nodes.
  
          EXAMPLES::
  
              sage: from sage.combinat.rigged_configurations.kleber_tree import VirtualKleberTree
              sage: KT = VirtualKleberTree(['A',6,2], [[2,2]])
              sage: L = [x for x in KT]
              sage: len(L) == KT.cardinality()
              True
          """
          return KleberTree.__iter__(self)
  
      def _prune(self, new_child, depth):
          r"""
          Return ``True`` if we are to prune the tree at ``new_child``.
  
          Suppose `\lambda` is the weight of the child we want to add at
          depth `\ell`. We prune ``new_child`` if `(\lambda \mid \alpha_a)
          \neq (\lambda \mid \alpha_b)` if `a` and `b` are in the same
          `\sigma`-orbit.
  
          These conditions are equivalent to Definition 4.1 in [OSS03]_ by using
          `\tilde{\gamma}`, and since `\tilde{\gamma}_a = 1` for all `a`, the
          second condition becomes vacuous.
  
          EXAMPLES::
  
              sage: from sage.combinat.rigged_configurations.kleber_tree import VirtualKleberTree
              sage: RS = RootSystem(['A', 5])
              sage: WS = RS.weight_space()
              sage: R = RS.root_space()
              sage: KT = VirtualKleberTree(['A',6,2], [[2,2]])
              sage: x = KT(WS.sum_of_terms([(2,1), (4,1)]), R.sum_of_terms([(1,1),(2,2),(3,2),(4,2),(5,1)]), KT.root)
              sage: KT._prune(x, 1)
              False
          """
          sigma = self._folded_ct._orbit
          for orbit in sigma[1:]:
              start = new_child.weight[orbit[0]]
              for i in orbit[1:]:
                  if new_child.weight[i] != start:
                      return True
          return False
  
      def breadth_first_iter(self, all_nodes=False):
          r"""
          Iterate over all nodes in the tree following a breadth-first traversal.
  
          INPUT:
  
          - ``all_nodes`` -- (default: ``False``) if ``True``, output all
            nodes in the tree
  
          EXAMPLES::
  
              sage: from sage.combinat.rigged_configurations.kleber_tree import VirtualKleberTree
              sage: KT = VirtualKleberTree(['A', 4, 2], [[2,1]])
              sage: for x in KT.breadth_first_iter(): x
              Kleber tree node with weight [0, 2, 0] and upwards edge root [0, 0, 0]
              Kleber tree node with weight [1, 0, 1] and upwards edge root [0, 1, 0]
              Kleber tree node with weight [0, 0, 0] and upwards edge root [1, 2, 1]
              sage: for x in KT.breadth_first_iter(True): x
              Kleber tree node with weight [0, 2, 0] and upwards edge root [0, 0, 0]
              Kleber tree node with weight [1, 0, 1] and upwards edge root [0, 1, 0]
              Kleber tree node with weight [0, 0, 0] and upwards edge root [1, 2, 1]
          """
          return KleberTree.breadth_first_iter(self)
  
      def depth_first_iter(self, all_nodes=False):
          r"""
          Iterate (recursively) over the nodes in the tree following a
          depth-first traversal.
  
          INPUT:
  
          - ``all_nodes`` -- (default: ``False``) if ``True``, output all
            nodes in the tree
  
          EXAMPLES::
  
              sage: from sage.combinat.rigged_configurations.kleber_tree import VirtualKleberTree
              sage: KT = VirtualKleberTree(['A', 4, 2], [[2,1]])
              sage: for x in KT.depth_first_iter(): x
              Kleber tree node with weight [0, 2, 0] and upwards edge root [0, 0, 0]
              Kleber tree node with weight [1, 0, 1] and upwards edge root [0, 1, 0]
              Kleber tree node with weight [0, 0, 0] and upwards edge root [1, 2, 1]
              sage: for x in KT.depth_first_iter(True): x
              Kleber tree node with weight [0, 2, 0] and upwards edge root [0, 0, 0]
              Kleber tree node with weight [1, 0, 1] and upwards edge root [0, 1, 0]
              Kleber tree node with weight [0, 0, 0] and upwards edge root [1, 2, 1]
          """
          return KleberTree.depth_first_iter(self)
  
  