code: def quadratic_assignment(A, B, method="faq", options=None):
      r"""
      Approximates solution to the quadratic assignment problem and
      the graph matching problem.
  
      Quadratic assignment solves problems of the following form:
  
      .. math::
  
          \min_P & \ {\ \text{trace}(A^T P B P^T)}\\
          \mbox{s.t. } & {P \ \epsilon \ \mathcal{P}}\\
  
      where :math:`\mathcal{P}` is the set of all permutation matrices,
      and :math:`A` and :math:`B` are square matrices.
  
      Graph matching tries to *maximize* the same objective function.
      This algorithm can be thought of as finding the alignment of the
      nodes of two graphs that minimizes the number of induced edge
      disagreements, or, in the case of weighted graphs, the sum of squared
      edge weight differences.
  
      Note that the quadratic assignment problem is NP-hard. The results given
      here are approximations and are not guaranteed to be optimal.
  
  
      Parameters
      ----------
      A : 2-D array, square
          The square matrix :math:`A` in the objective function above.
  
      B : 2-D array, square
          The square matrix :math:`B` in the objective function above.
  
      method :  str in {'faq', '2opt'} (default: 'faq')
          The algorithm used to solve the problem.
          :ref:`'faq' <optimize.qap-faq>` (default) and
          :ref:`'2opt' <optimize.qap-2opt>` are available.
  
      options : dict, optional
          A dictionary of solver options. All solvers support the following:
  
          maximize : bool (default: False)
              Maximizes the objective function if ``True``.
  
          partial_match : 2-D array of integers, optional (default: None)
              Fixes part of the matching. Also known as a "seed" [2]_.
  
              Each row of `partial_match` specifies a pair of matched nodes:
              node ``partial_match[i, 0]`` of `A` is matched to node
              ``partial_match[i, 1]`` of `B`. The array has shape ``(m, 2)``,
              where ``m`` is not greater than the number of nodes, :math:`n`.
  
          rng : {None, int, `numpy.random.Generator`,
                 `numpy.random.RandomState`}, optional
  
              If `seed` is None (or `np.random`), the `numpy.random.RandomState`
              singleton is used.
              If `seed` is an int, a new ``RandomState`` instance is used,
              seeded with `seed`.
              If `seed` is already a ``Generator`` or ``RandomState`` instance then
              that instance is used.
  
          For method-specific options, see
          :func:`show_options('quadratic_assignment') <show_options>`.
  
      Returns
      -------
      res : OptimizeResult
          `OptimizeResult` containing the following fields.
  
          col_ind : 1-D array
              Column indices corresponding to the best permutation found of the
              nodes of `B`.
          fun : float
              The objective value of the solution.
          nit : int
              The number of iterations performed during optimization.
  
      Notes
      -----
      The default method :ref:`'faq' <optimize.qap-faq>` uses the Fast
      Approximate QAP algorithm [1]_; it typically offers the best combination of
      speed and accuracy.
      Method :ref:`'2opt' <optimize.qap-2opt>` can be computationally expensive,
      but may be a useful alternative, or it can be used to refine the solution
      returned by another method.
  
      References
      ----------
      .. [1] J.T. Vogelstein, J.M. Conroy, V. Lyzinski, L.J. Podrazik,
             S.G. Kratzer, E.T. Harley, D.E. Fishkind, R.J. Vogelstein, and
             C.E. Priebe, "Fast approximate quadratic programming for graph
             matching," PLOS one, vol. 10, no. 4, p. e0121002, 2015,
             :doi:`10.1371/journal.pone.0121002`
  
      .. [2] D. Fishkind, S. Adali, H. Patsolic, L. Meng, D. Singh, V. Lyzinski,
             C. Priebe, "Seeded graph matching", Pattern Recognit. 87 (2019):
             203-215, :doi:`10.1016/j.patcog.2018.09.014`
  
      .. [3] "2-opt," Wikipedia.
             https://en.wikipedia.org/wiki/2-opt
  
      Examples
      --------
      >>> from scipy.optimize import quadratic_assignment
      >>> A = np.array([[0, 80, 150, 170], [80, 0, 130, 100],
      ...               [150, 130, 0, 120], [170, 100, 120, 0]])
      >>> B = np.array([[0, 5, 2, 7], [0, 0, 3, 8],
      ...               [0, 0, 0, 3], [0, 0, 0, 0]])
      >>> res = quadratic_assignment(A, B)
      >>> print(res)
       col_ind: array([0, 3, 2, 1])
           fun: 3260
           nit: 9
  
      The see the relationship between the returned ``col_ind`` and ``fun``,
      use ``col_ind`` to form the best permutation matrix found, then evaluate
      the objective function :math:`f(P) = trace(A^T P B P^T )`.
  
      >>> perm = res['col_ind']
      >>> P = np.eye(len(A), dtype=int)[perm]
      >>> fun = np.trace(A.T @ P @ B @ P.T)
      >>> print(fun)
      3260
  
      Alternatively, to avoid constructing the permutation matrix explicitly,
      directly permute the rows and columns of the distance matrix.
  
      >>> fun = np.trace(A.T @ B[perm][:, perm])
      >>> print(fun)
      3260
  
      Although not guaranteed in general, ``quadratic_assignment`` happens to
      have found the globally optimal solution.
  
      >>> from itertools import permutations
      >>> perm_opt, fun_opt = None, np.inf
      >>> for perm in permutations([0, 1, 2, 3]):
      ...     perm = np.array(perm)
      ...     fun = np.trace(A.T @ B[perm][:, perm])
      ...     if fun < fun_opt:
      ...         fun_opt, perm_opt = fun, perm
      >>> print(np.array_equal(perm_opt, res['col_ind']))
      True
  
      Here is an example for which the default method,
      :ref:`'faq' <optimize.qap-faq>`, does not find the global optimum.
  
      >>> A = np.array([[0, 5, 8, 6], [5, 0, 5, 1],
      ...               [8, 5, 0, 2], [6, 1, 2, 0]])
      >>> B = np.array([[0, 1, 8, 4], [1, 0, 5, 2],
      ...               [8, 5, 0, 5], [4, 2, 5, 0]])
      >>> res = quadratic_assignment(A, B)
      >>> print(res)
       col_ind: array([1, 0, 3, 2])
           fun: 178
           nit: 13
  
      If accuracy is important, consider using  :ref:`'2opt' <optimize.qap-2opt>`
      to refine the solution.
  
      >>> guess = np.array([np.arange(len(A)), res.col_ind]).T
      >>> res = quadratic_assignment(A, B, method="2opt",
      ...                            options = {'partial_guess': guess})
      >>> print(res)
       col_ind: array([1, 2, 3, 0])
           fun: 176
           nit: 17
  
      """
  
      if options is None:
          options = {}
  
      method = method.lower()
      methods = {
          "faq": _quadratic_assignment_faq,
          "2opt": _quadratic_assignment_2opt,
      }
      if method not in methods:
          raise ValueError(f"method {method} must be in {methods}.")
      res = methods[method](A, B, **options)
      return res
  
file_path: catboost/contrib/python/scipy/py3/scipy/optimize/_qap.py
imports: import numpy
  import operator
  from .None import linear_sum_assignment, OptimizeResult
  from .optimize import _check_unknown_options
  from scipy._lib._util import check_random_state
  import itertools
label_desc: Use image node_id 1 for calling a global function with example usage: quadratic_assignment(A, B, method, options) and returns: res