code: def kahane_simplify(expression):
      r"""
      This function cancels contracted elements in a product of four
      dimensional gamma matrices, resulting in an expression equal to the given
      one, without the contracted gamma matrices.
  
      Parameters
      ==========
  
      `expression`    the tensor expression containing the gamma matrices to simplify.
  
      Notes
      =====
  
      If spinor indices are given, the matrices must be given in
      the order given in the product.
  
      Algorithm
      =========
  
      The idea behind the algorithm is to use some well-known identities,
      i.e., for contractions enclosing an even number of `\gamma` matrices
  
      `\gamma^\mu \gamma_{a_1} \cdots \gamma_{a_{2N}} \gamma_\mu = 2 (\gamma_{a_{2N}} \gamma_{a_1} \cdots \gamma_{a_{2N-1}} + \gamma_{a_{2N-1}} \cdots \gamma_{a_1} \gamma_{a_{2N}} )`
  
      for an odd number of `\gamma` matrices
  
      `\gamma^\mu \gamma_{a_1} \cdots \gamma_{a_{2N+1}} \gamma_\mu = -2 \gamma_{a_{2N+1}} \gamma_{a_{2N}} \cdots \gamma_{a_{1}}`
  
      Instead of repeatedly applying these identities to cancel out all contracted indices,
      it is possible to recognize the links that would result from such an operation,
      the problem is thus reduced to a simple rearrangement of free gamma matrices.
  
      Examples
      ========
  
      When using, always remember that the original expression coefficient
      has to be handled separately
  
      >>> from sympy.physics.hep.gamma_matrices import GammaMatrix as G, LorentzIndex
      >>> from sympy.physics.hep.gamma_matrices import kahane_simplify
      >>> from sympy.tensor.tensor import tensor_indices
      >>> i0, i1, i2 = tensor_indices('i0:3', LorentzIndex)
      >>> ta = G(i0)*G(-i0)
      >>> kahane_simplify(ta)
      Matrix([
      [4, 0, 0, 0],
      [0, 4, 0, 0],
      [0, 0, 4, 0],
      [0, 0, 0, 4]])
      >>> tb = G(i0)*G(i1)*G(-i0)
      >>> kahane_simplify(tb)
      -2*GammaMatrix(i1)
      >>> t = G(i0)*G(-i0)
      >>> kahane_simplify(t)
      Matrix([
      [4, 0, 0, 0],
      [0, 4, 0, 0],
      [0, 0, 4, 0],
      [0, 0, 0, 4]])
      >>> t = G(i0)*G(-i0)
      >>> kahane_simplify(t)
      Matrix([
      [4, 0, 0, 0],
      [0, 4, 0, 0],
      [0, 0, 4, 0],
      [0, 0, 0, 4]])
  
      If there are no contractions, the same expression is returned
  
      >>> tc = G(i0)*G(i1)
      >>> kahane_simplify(tc)
      GammaMatrix(i0)*GammaMatrix(i1)
  
      References
      ==========
  
      [1] Algorithm for Reducing Contracted Products of gamma Matrices,
      Joseph Kahane, Journal of Mathematical Physics, Vol. 9, No. 10, October 1968.
      """
  
      if isinstance(expression, Mul):
          return expression
      if isinstance(expression, TensAdd):
          return TensAdd(
              *[kahane_simplify(arg) for arg in expression.args]
          )
  
      if isinstance(expression, Tensor):
          return expression
  
      assert isinstance(expression, TensMul)
  
      gammas = expression.args
  
      for gamma in gammas:
          assert gamma.component == GammaMatrix
  
      free = expression.free
      # spinor_free = [_ for _ in expression.free_in_args if _[1] != 0]
  
      # if len(spinor_free) == 2:
      #     spinor_free.sort(key=lambda x: x[2])
      #     assert spinor_free[0][1] == 1 and spinor_free[-1][1] == 2
      #     assert spinor_free[0][2] == 0
      # elif spinor_free:
      #     raise ValueError('spinor indices do not match')
  
      dum = []
      for dum_pair in expression.dum:
          if expression.index_types[dum_pair[0]] == LorentzIndex:
              dum.append((dum_pair[0], dum_pair[1]))
  
      dum = sorted(dum)
  
      if len(dum) == 0:  # or GammaMatrixHead:
          # no contractions in `expression`, just return it.
          return expression
  
      # find the `first_dum_pos`, i.e. the position of the first contracted
      # gamma matrix, Kahane's algorithm as described in his paper requires the
      # gamma matrix expression to start with a contracted gamma matrix, this is
      # a workaround which ignores possible initial free indices, and re-adds
      # them later.
  
      first_dum_pos = min(map(min, dum))
  
      # for p1, p2, a1, a2 in expression.dum_in_args:
      #     if p1 != 0 or p2 != 0:
      #         # only Lorentz indices, skip Dirac indices:
      #         continue
      #     first_dum_pos = min(p1, p2)
      #     break
  
      total_number = len(free) + len(dum) * 2
      number_of_contractions = len(dum)
  
      free_pos = [None] * total_number
      for i in free:
          free_pos[i[1]] = i[0]
  
      # `index_is_free` is a list of booleans, to identify index position
      # and whether that index is free or dummy.
      index_is_free = [False] * total_number
  
      for i, indx in enumerate(free):
          index_is_free[indx[1]] = True
  
      # `links` is a dictionary containing the graph described in Kahane's paper,
      # to every key correspond one or two values, representing the linked indices.
      # All values in `links` are integers, negative numbers are used in the case
      # where it is necessary to insert gamma matrices between free indices, in
      # order to make Kahane's algorithm work (see paper).
      links = {i: [] for i in range(first_dum_pos, total_number)}
  
      # `cum_sign` is a step variable to mark the sign of every index, see paper.
      cum_sign = -1
      # `cum_sign_list` keeps storage for all `cum_sign` (every index).
      cum_sign_list = [None] * total_number
      block_free_count = 0
  
      # multiply `resulting_coeff` by the coefficient parameter, the rest
      # of the algorithm ignores a scalar coefficient.
      resulting_coeff = S.One
  
      # initialize a list of lists of indices. The outer list will contain all
      # additive tensor expressions, while the inner list will contain the
      # free indices (rearranged according to the algorithm).
      resulting_indices = [[]]
  
      # start to count the `connected_components`, which together with the number
      # of contractions, determines a -1 or +1 factor to be multiplied.
      connected_components = 1
  
      # First loop: here we fill `cum_sign_list`, and draw the links
      # among consecutive indices (they are stored in `links`). Links among
      # non-consecutive indices will be drawn later.
      for i, is_free in enumerate(index_is_free):
          # if `expression` starts with free indices, they are ignored here;
          # they are later added as they are to the beginning of all
          # `resulting_indices` list of lists of indices.
          if i < first_dum_pos:
              continue
  
          if is_free:
              block_free_count += 1
              # if previous index was free as well, draw an arch in `links`.
              if block_free_count > 1:
                  links[i - 1].append(i)
                  links[i].append(i - 1)
          else:
              # Change the sign of the index (`cum_sign`) if the number of free
              # indices preceding it is even.
              cum_sign *= 1 if (block_free_count % 2) else -1
              if block_free_count == 0 and i != first_dum_pos:
                  # check if there are two consecutive dummy indices:
                  # in this case create virtual indices with negative position,
                  # these "virtual" indices represent the insertion of two
                  # gamma^0 matrices to separate consecutive dummy indices, as
                  # Kahane's algorithm requires dummy indices to be separated by
                  # free indices. The product of two gamma^0 matrices is unity,
                  # so the new expression being examined is the same as the
                  # original one.
                  if cum_sign == -1:
                      links[-1 - i] = [-1 - i + 1]
                      links[-1 - i + 1] = [-1 - i]
              if (i - cum_sign) in links:
                  if i != first_dum_pos:
                      links[i].append(i - cum_sign)
                  if block_free_count != 0:
                      if i - cum_sign < len(index_is_free):
                          if index_is_free[i - cum_sign]:
                              links[i - cum_sign].append(i)
              block_free_count = 0
  
          cum_sign_list[i] = cum_sign
  
      # The previous loop has only created links between consecutive free indices,
      # it is necessary to properly create links among dummy (contracted) indices,
      # according to the rules described in Kahane's paper. There is only one exception
      # to Kahane's rules: the negative indices, which handle the case of some
      # consecutive free indices (Kahane's paper just describes dummy indices
      # separated by free indices, hinting that free indices can be added without
      # altering the expression result).
      for i in dum:
          # get the positions of the two contracted indices:
          pos1 = i[0]
          pos2 = i[1]
  
          # create Kahane's upper links, i.e. the upper arcs between dummy
          # (i.e. contracted) indices:
          links[pos1].append(pos2)
          links[pos2].append(pos1)
  
          # create Kahane's lower links, this corresponds to the arcs below
          # the line described in the paper:
  
          # first we move `pos1` and `pos2` according to the sign of the indices:
          linkpos1 = pos1 + cum_sign_list[pos1]
          linkpos2 = pos2 + cum_sign_list[pos2]
  
          # otherwise, perform some checks before creating the lower arcs:
  
          # make sure we are not exceeding the total number of indices:
          if linkpos1 >= total_number:
              continue
          if linkpos2 >= total_number:
              continue
  
          # make sure we are not below the first dummy index in `expression`:
          if linkpos1 < first_dum_pos:
              continue
          if linkpos2 < first_dum_pos:
              continue
  
          # check if the previous loop created "virtual" indices between dummy
          # indices, in such a case relink `linkpos1` and `linkpos2`:
          if (-1 - linkpos1) in links:
              linkpos1 = -1 - linkpos1
          if (-1 - linkpos2) in links:
              linkpos2 = -1 - linkpos2
  
          # move only if not next to free index:
          if linkpos1 >= 0 and not index_is_free[linkpos1]:
              linkpos1 = pos1
  
          if linkpos2 >= 0 and not index_is_free[linkpos2]:
              linkpos2 = pos2
  
          # create the lower arcs:
          if linkpos2 not in links[linkpos1]:
              links[linkpos1].append(linkpos2)
          if linkpos1 not in links[linkpos2]:
              links[linkpos2].append(linkpos1)
  
      # This loop starts from the `first_dum_pos` index (first dummy index)
      # walks through the graph deleting the visited indices from `links`,
      # it adds a gamma matrix for every free index in encounters, while it
      # completely ignores dummy indices and virtual indices.
      pointer = first_dum_pos
      previous_pointer = 0
      while True:
          if pointer in links:
              next_ones = links.pop(pointer)
          else:
              break
  
          if previous_pointer in next_ones:
              next_ones.remove(previous_pointer)
  
          previous_pointer = pointer
  
          if next_ones:
              pointer = next_ones[0]
          else:
              break
  
          if pointer == previous_pointer:
              break
          if pointer >= 0 and free_pos[pointer] is not None:
              for ri in resulting_indices:
                  ri.append(free_pos[pointer])
  
      # The following loop removes the remaining connected components in `links`.
      # If there are free indices inside a connected component, it gives a
      # contribution to the resulting expression given by the factor
      # `gamma_a gamma_b ... gamma_z + gamma_z ... gamma_b gamma_a`, in Kahanes's
      # paper represented as  {gamma_a, gamma_b, ... , gamma_z},
      # virtual indices are ignored. The variable `connected_components` is
      # increased by one for every connected component this loop encounters.
  
      # If the connected component has virtual and dummy indices only
      # (no free indices), it contributes to `resulting_indices` by a factor of two.
      # The multiplication by two is a result of the
      # factor {gamma^0, gamma^0} = 2 I, as it appears in Kahane's paper.
      # Note: curly brackets are meant as in the paper, as a generalized
      # multi-element anticommutator!
  
      while links:
          connected_components += 1
          pointer = min(links.keys())
          previous_pointer = pointer
          # the inner loop erases the visited indices from `links`, and it adds
          # all free indices to `prepend_indices` list, virtual indices are
          # ignored.
          prepend_indices = []
          while True:
              if pointer in links:
                  next_ones = links.pop(pointer)
              else:
                  break
  
              if previous_pointer in next_ones:
                  if len(next_ones) > 1:
                      next_ones.remove(previous_pointer)
  
              previous_pointer = pointer
  
              if next_ones:
                  pointer = next_ones[0]
  
              if (
                  pointer >= first_dum_pos
                  and free_pos[pointer] is not None
              ):
                  prepend_indices.insert(0, free_pos[pointer])
          # if `prepend_indices` is void, it means there are no free indices
          # in the loop (and it can be shown that there must be a virtual index),
          # loops of virtual indices only contribute by a factor of two:
          if len(prepend_indices) == 0:
              resulting_coeff *= 2
          # otherwise, add the free indices in `prepend_indices` to
          # the `resulting_indices`:
          else:
              expr1 = prepend_indices
              expr2 = list(reversed(prepend_indices))
              resulting_indices = [
                  expri + ri
                  for ri in resulting_indices
                  for expri in (expr1, expr2)
              ]
  
      # sign correction, as described in Kahane's paper:
      resulting_coeff *= (
          -1
          if (number_of_contractions - connected_components + 1) % 2
          else 1
      )
      # power of two factor, as described in Kahane's paper:
      resulting_coeff *= 2 ** (number_of_contractions)
  
      # If `first_dum_pos` is not zero, it means that there are trailing free gamma
      # matrices in front of `expression`, so multiply by them:
      resulting_indices = [
          free_pos[0:first_dum_pos] + ri for ri in resulting_indices
      ]
  
      resulting_expr = S.Zero
      for i in resulting_indices:
          temp_expr = S.One
          for j in i:
              temp_expr *= GammaMatrix(j)
          resulting_expr += temp_expr
  
      t = resulting_coeff * resulting_expr
      t1 = None
      if isinstance(t, TensAdd):
          t1 = t.args[0]
      elif isinstance(t, TensMul):
          t1 = t
      if t1:
          pass
      else:
          t = eye(4) * t
      return t
  
file_path: sympy/sympy/physics/hep/gamma_matrices.py
imports: from sympy.core.mul import Mul
  from sympy.core.singleton import S
  from sympy.matrices.dense import eye
  from sympy.matrices.expressions.trace import trace
  from sympy.tensor.tensor import TensorIndexType, TensorIndex, TensMul, TensAdd, tensor_mul, Tensor, TensorHead, TensorSymmetry
label_desc: Use image node_id 8 for calling a global function with example usage: kahane_simplify(expression) and returns: t, expression, TensAdd, expression, expression