class_docstr: NNDescent for fast approximate nearest neighbor queries. NNDescent is
  very flexible and supports a wide variety of distances, including
  non-metric distances. NNDescent also scales well against high dimensional
  graph_data in many cases. This implementation provides a straightfoward
  interface, with access to some tuning parameters.
  
  Parameters
  ----------
  data: array of shape (n_samples, n_features)
      The training graph_data set to find nearest neighbors in.
  
  metric: string or callable (optional, default='euclidean')
      The metric to use for computing nearest neighbors. If a callable is
      used it must be a numba njit compiled function. Supported metrics
      include:
          * euclidean
          * manhattan
          * chebyshev
          * minkowski
          * canberra
          * braycurtis
          * mahalanobis
          * wminkowski
          * seuclidean
          * cosine
          * correlation
          * haversine
          * hamming
          * jaccard
          * dice
          * russelrao
          * kulsinski
          * rogerstanimoto
          * sokalmichener
          * sokalsneath
          * yule
          * hellinger
          * wasserstein-1d
      Metrics that take arguments (such as minkowski, mahalanobis etc.)
      can have arguments passed via the metric_kwds dictionary. At this
      time care must be taken and dictionary elements must be ordered
      appropriately; this will hopefully be fixed in the future.
  
  metric_kwds: dict (optional, default {})
      Arguments to pass on to the metric, such as the ``p`` value for
      Minkowski distance.
  
  n_neighbors: int (optional, default=30)
      The number of neighbors to use in k-neighbor graph graph_data structure
      used for fast approximate nearest neighbor search. Larger values
      will result in more accurate search results at the cost of
      computation time.
  
  n_trees: int (optional, default=None)
      This implementation uses random projection forests for initializing the index
      build process. This parameter controls the number of trees in that forest. A
      larger number will result in more accurate neighbor computation at the cost
      of performance. The default of None means a value will be chosen based on the
      size of the graph_data.
  
  leaf_size: int (optional, default=None)
      The maximum number of points in a leaf for the random projection trees.
      The default of None means a value will be chosen based on n_neighbors.
  
  pruning_degree_multiplier: float (optional, default=1.5)
      How aggressively to prune the graph. Since the search graph is undirected
      (and thus includes nearest neighbors and reverse nearest neighbors) vertices
      can have very high degree -- the graph will be pruned such that no
      vertex has degree greater than
      ``pruning_degree_multiplier * n_neighbors``.
  
  diversify_prob: float (optional, default=1.0)
      The search graph get "diversified" by removing potentially unnecessary
      edges. This controls the volume of edges removed. A value of 0.0 ensures
      that no edges get removed, and larger values result in significantly more
      aggressive edge removal. A value of 1.0 will prune all edges that it can.
  
  n_search_trees: int (optional, default=1)
      The number of random projection trees to use in initializing searching or
      querying.
  
      .. deprecated:: 0.5.5
  
  tree_init: bool (optional, default=True)
      Whether to use random projection trees for initialization.
  
  init_graph: np.ndarray (optional, default=None)
      2D array of indices of candidate neighbours of the shape
      (data.shape[0], n_neighbours). If the j-th neighbour of the i-th
      instances is unknown, use init_graph[i, j] = -1
  
  init_dist: np.ndarray (optional, default=None)
      2D array with the same shape as init_graph,
      such that metric(data[i], data[init_graph[i, j]]) equals
      init_dist[i, j]
  
  random_state: int, RandomState instance or None, optional (default: None)
      If int, random_state is the seed used by the random number generator;
      If RandomState instance, random_state is the random number generator;
      If None, the random number generator is the RandomState instance used
      by `np.random`.
  
  algorithm: string (optional, default='standard')
      This implementation provides an alternative algorithm for
      construction of the k-neighbors graph used as a search index. The
      alternative algorithm can be fast for large ``n_neighbors`` values.
      The``'alternative'`` algorithm has been deprecated and is no longer
      available.
  
  low_memory: boolean (optional, default=True)
      Whether to use a lower memory, but more computationally expensive
      approach to index construction.
  
  max_candidates: int (optional, default=None)
      Internally each "self-join" keeps a maximum number of candidates (
      nearest neighbors and reverse nearest neighbors) to be considered.
      This value controls this aspect of the algorithm. Larger values will
      provide more accurate search results later, but potentially at
      non-negligible computation cost in building the index. Don't tweak
      this value unless you know what you're doing.
  
  max_rptree_depth: int (optional, default=100)
      Maximum depth of random projection trees. Increasing this may result in a
      richer, deeper random projection forest, but it may be composed of many
      degenerate branches. Increase leaf_size in order to keep shallower, wider
      nondegenerate trees. Such wide trees, however, may yield poor performance
      of the preparation of the NN descent.
  
  n_iters: int (optional, default=None)
      The maximum number of NN-descent iterations to perform. The
      NN-descent algorithm can abort early if limited progress is being
      made, so this only controls the worst case. Don't tweak
      this value unless you know what you're doing. The default of None means
      a value will be chosen based on the size of the graph_data.
  
  delta: float (optional, default=0.001)
      Controls the early abort due to limited progress. Larger values
      will result in earlier aborts, providing less accurate indexes,
      and less accurate searching. Don't tweak this value unless you know
      what you're doing.
  
  n_jobs: int or None, optional (default=None)
      The number of parallel jobs to run for neighbors index construction.
      ``None`` means 1 unless in a :obj:`joblib.parallel_backend` context.
      ``-1`` means using all processors.
  
  compressed: bool (optional, default=False)
      Whether to prune out data not needed for searching the index. This will
      result in a significantly smaller index, particularly useful for saving,
      but will remove information that might otherwise be useful.
  
  parallel_batch_queries: bool (optional, default=False)
      Whether to use parallelism of batched queries. This can be useful for large
      batches of queries on multicore machines, but results in performance degradation
      for single queries, so is poor for streaming use.
  
  verbose: bool (optional, default=False)
      Whether to print status graph_data during the computation.
class_docstr_tok: ["NNDescent","for","fast","approximate","nearest","neighbor","queries",".","NNDescent","is","very","flexible","and","supports","a","wide","variety","of","distances",",","including","non-metric","distances",".","NNDescent","also","scales","well","against","high","dimensional","graph_data","in","many","cases",".","This","implementation","provides","a","straightfoward","interface",",","with","access","to","some","tuning","parameters",".","Parameters","--","--","--","--","--","data",":","array","of","shape","(","n_samples",",","n_features",")","The","training","graph_data","set","to","find","nearest","neighbors","in",".","metric",":","string","or","callable","(","optional",",","default='euclidean","'",")","The","metric","to","use","for","computing","nearest","neighbors",".","If","a","callable","is","used","it","must","be","a","numba","njit","compiled","function",".","Supported","metrics","include",":","*","euclidean","*","manhattan","*","chebyshev","*","minkowski","*","canberra","*","braycurtis","*","mahalanobis","*","wminkowski","*","seuclidean","*","cosine","*","correlation","*","haversine","*","hamming","*","jaccard","*","dice","*","russelrao","*","kulsinski","*","rogerstanimoto","*","sokalmichener","*","sokalsneath","*","yule","*","hellinger","*","wasserstein-1d","Metrics","that","take","arguments","(","such","as","minkowski",",","mahalanobis","etc",".",")","can","have","arguments","passed","via","the","metric_kwds","dictionary",".","At","this","time","care","must","be","taken","and","dictionary","elements","must","be","ordered","appropriately",";","this","will","hopefully","be","fixed","in","the","future",".","metric_kwds",":","dict","(","optional",",","default","{","}",")","Arguments","to","pass","on","to","the","metric",",","such","as","the","``","p","``","value","for","Minkowski","distance",".","n_neighbors",":","int","(","optional",",","default=30",")","The","number","of","neighbors","to","use","in","k-neighbor","graph","graph_data","structure","used","for","fast","approximate","nearest","neighbor","search",".","Larger","values","will","result","in","more","accurate","search","results","at","the","cost","of","computation","time",".","n_trees",":","int","(","optional",",","default=None",")","This","implementation","uses","random","projection","forests","for","initializing","the","index","build","process",".","This","parameter","controls","the","number","of","trees","in","that","forest",".","A","larger","number","will","result","in","more","accurate","neighbor","computation","at","the","cost","of","performance",".","The","default","of","None","means","a","value","will","be","chosen","based","on","the","size","of","the","graph_data",".","leaf_size",":","int","(","optional",",","default=None",")","The","maximum","number","of","points","in","a","leaf","for","the","random","projection","trees",".","The","default","of","None","means","a","value","will","be","chosen","based","on","n_neighbors",".","pruning_degree_multiplier",":","float","(","optional",",","default=1.5",")","How","aggressively","to","prune","the","graph",".","Since","the","search","graph","is","undirected","(","and","thus","includes","nearest","neighbors","and","reverse","nearest","neighbors",")","vertices","can","have","very","high","degree","--","the","graph","will","be","pruned","such","that","no","vertex","has","degree","greater","than","``","pruning_degree_multiplier","*","n_neighbors","``",".","diversify_prob",":","float","(","optional",",","default=1.0",")","The","search","graph","get","``","diversified","''","by","removing","potentially","unnecessary","edges",".","This","controls","the","volume","of","edges","removed",".","A","value","of","0.0","ensures","that","no","edges","get","removed",",","and","larger","values","result","in","significantly","more","aggressive","edge","removal",".","A","value","of","1.0","will","prune","all","edges","that","it","can",".","n_search_trees",":","int","(","optional",",","default=1",")","The","number","of","random","projection","trees","to","use","in","initializing","searching","or","querying",".","..","deprecated",":",":","0.5.5","tree_init",":","bool","(","optional",",","default=True",")","Whether","to","use","random","projection","trees","for","initialization",".","init_graph",":","np.ndarray","(","optional",",","default=None",")","2D","array","of","indices","of","candidate","neighbours","of","the","shape","(","data.shape","[","0","]",",","n_neighbours",")",".","If","the","j-th","neighbour","of","the","i-th","instances","is","unknown",",","use","init_graph","[","i",",","j","]","=","-1","init_dist",":","np.ndarray","(","optional",",","default=None",")","2D","array","with","the","same","shape","as","init_graph",",","such","that","metric","(","data","[","i","]",",","data","[","init_graph","[","i",",","j","]","]",")","equals","init_dist","[","i",",","j","]","random_state",":","int",",","RandomState","instance","or","None",",","optional","(","default",":","None",")","If","int",",","random_state","is","the","seed","used","by","the","random","number","generator",";","If","RandomState","instance",",","random_state","is","the","random","number","generator",";","If","None",",","the","random","number","generator","is","the","RandomState","instance","used","by","`","np.random","`",".","algorithm",":","string","(","optional",",","default='standard","'",")","This","implementation","provides","an","alternative","algorithm","for","construction","of","the","k-neighbors","graph","used","as","a","search","index",".","The","alternative","algorithm","can","be","fast","for","large","``","n_neighbors","``","values",".","The","``","'alternative","'","``","algorithm","has","been","deprecated","and","is","no","longer","available",".","low_memory",":","boolean","(","optional",",","default=True",")","Whether","to","use","a","lower","memory",",","but","more","computationally","expensive","approach","to","index","construction",".","max_candidates",":","int","(","optional",",","default=None",")","Internally","each","``","self-join","''","keeps","a","maximum","number","of","candidates","(","nearest","neighbors","and","reverse","nearest","neighbors",")","to","be","considered",".","This","value","controls","this","aspect","of","the","algorithm",".","Larger","values","will","provide","more","accurate","search","results","later",",","but","potentially","at","non-negligible","computation","cost","in","building","the","index",".","Do","n't","tweak","this","value","unless","you","know","what","you","'re","doing",".","max_rptree_depth",":","int","(","optional",",","default=100",")","Maximum","depth","of","random","projection","trees",".","Increasing","this","may","result","in","a","richer",",","deeper","random","projection","forest",",","but","it","may","be","composed","of","many","degenerate","branches",".","Increase","leaf_size","in","order","to","keep","shallower",",","wider","nondegenerate","trees",".","Such","wide","trees",",","however",",","may","yield","poor","performance","of","the","preparation","of","the","NN","descent",".","n_iters",":","int","(","optional",",","default=None",")","The","maximum","number","of","NN-descent","iterations","to","perform",".","The","NN-descent","algorithm","can","abort","early","if","limited","progress","is","being","made",",","so","this","only","controls","the","worst","case",".","Do","n't","tweak","this","value","unless","you","know","what","you","'re","doing",".","The","default","of","None","means","a","value","will","be","chosen","based","on","the","size","of","the","graph_data",".","delta",":","float","(","optional",",","default=0.001",")","Controls","the","early","abort","due","to","limited","progress",".","Larger","values","will","result","in","earlier","aborts",",","providing","less","accurate","indexes",",","and","less","accurate","searching",".","Do","n't","tweak","this","value","unless","you","know","what","you","'re","doing",".","n_jobs",":","int","or","None",",","optional","(","default=None",")","The","number","of","parallel","jobs","to","run","for","neighbors","index","construction",".","``","None","``","means","1","unless","in","a",":","obj",":","`","joblib.parallel_backend","`","context",".","``","-1","``","means","using","all","processors",".","compressed",":","bool","(","optional",",","default=False",")","Whether","to","prune","out","data","not","needed","for","searching","the","index",".","This","will","result","in","a","significantly","smaller","index",",","particularly","useful","for","saving",",","but","will","remove","information","that","might","otherwise","be","useful",".","parallel_batch_queries",":","bool","(","optional",",","default=False",")","Whether","to","use","parallelism","of","batched","queries",".","This","can","be","useful","for","large","batches","of","queries","on","multicore","machines",",","but","results","in","performance","degradation","for","single","queries",",","so","is","poor","for","streaming","use",".","verbose",":","bool","(","optional",",","default=False",")","Whether","to","print","status","graph_data","during","the","computation","."]
code: def __init__(
      self,
      data,
      metric="euclidean",
      metric_kwds=None,
      n_neighbors=30,
      n_trees=None,
      leaf_size=None,
      pruning_degree_multiplier=1.5,
      diversify_prob=1.0,
      n_search_trees=1,
      tree_init=True,
      init_graph=None,
      init_dist=None,
      random_state=None,
      low_memory=True,
      max_candidates=None,
      max_rptree_depth=200,
      n_iters=None,
      delta=0.001,
      n_jobs=None,
      compressed=False,
      parallel_batch_queries=False,
      verbose=False,
  ):
      if n_trees is None:
          n_trees = 5 + int(round((data.shape[0]) ** 0.25))
          n_trees = min(32, n_trees)  # Only so many trees are useful
      if n_iters is None:
          n_iters = max(5, int(round(np.log2(data.shape[0]))))
  
      self.n_trees = n_trees
      self.n_trees_after_update = max(
          1, int(np.round(self.n_trees / 3))
      )
      self.n_neighbors = n_neighbors
      self.metric = metric
      self.metric_kwds = metric_kwds
      self.leaf_size = leaf_size
      self.prune_degree_multiplier = pruning_degree_multiplier
      self.diversify_prob = diversify_prob
      self.n_search_trees = n_search_trees
      self.max_rptree_depth = max_rptree_depth
      self.max_candidates = max_candidates
      self.low_memory = low_memory
      self.n_iters = n_iters
      self.delta = delta
      self.dim = data.shape[1]
      self.n_jobs = n_jobs
      self.compressed = compressed
      self.parallel_batch_queries = parallel_batch_queries
      self.verbose = verbose
  
      if getattr(data, "dtype", None) == np.float32 and (
          issparse(data) or is_c_contiguous(data)
      ):
          copy_on_normalize = True
      else:
          copy_on_normalize = False
  
      data = check_array(
          data, dtype=np.float32, accept_sparse="csr", order="C"
      )
      self._raw_data = data
  
      if not tree_init or n_trees == 0 or init_graph is not None:
          self.tree_init = False
      else:
          self.tree_init = True
  
      metric_kwds = metric_kwds or {}
      self._dist_args = tuple(metric_kwds.values())
  
      self.random_state = random_state
  
      current_random_state = check_random_state(self.random_state)
  
      self._distance_correction = None
  
      if callable(metric):
          _distance_func = metric
      elif metric in pynnd_dist.named_distances:
          if metric in pynnd_dist.fast_distance_alternatives:
              _distance_func = pynnd_dist.fast_distance_alternatives[
                  metric
              ]["dist"]
              self._distance_correction = (
                  pynnd_dist.fast_distance_alternatives[metric][
                      "correction"
                  ]
              )
          else:
              _distance_func = pynnd_dist.named_distances[metric]
      else:
          raise ValueError(
              "Metric is neither callable, " + "nor a recognised string"
          )
  
      # Create a partial function for distances with arguments
      if len(self._dist_args) > 0:
          dist_args = self._dist_args
  
          @numba.njit()
          def _partial_dist_func(x, y):
              return _distance_func(x, y, *dist_args)
  
          self._distance_func = _partial_dist_func
      else:
          self._distance_func = _distance_func
  
      if metric in (
          "cosine",
          "dot",
          "correlation",
          "dice",
          "jaccard",
          "hellinger",
          "hamming",
      ):
          self._angular_trees = True
      else:
          self._angular_trees = False
  
      if metric == "dot":
          data = normalize(data, norm="l2", copy=copy_on_normalize)
          self._raw_data = data
  
      self.rng_state = current_random_state.randint(
          INT32_MIN, INT32_MAX, 3
      ).astype(np.int64)
      self.search_rng_state = current_random_state.randint(
          INT32_MIN, INT32_MAX, 3
      ).astype(np.int64)
      # Warm up the rng state
      for i in range(10):
          _ = tau_rand_int(self.search_rng_state)
  
      if self.tree_init:
          if verbose:
              print(
                  ts(), "Building RP forest with", str(n_trees), "trees"
              )
          self._rp_forest = make_forest(
              data,
              n_neighbors,
              n_trees,
              leaf_size,
              self.rng_state,
              current_random_state,
              self.n_jobs,
              self._angular_trees,
              max_depth=self.max_rptree_depth,
          )
          leaf_array = rptree_leaf_array(self._rp_forest)
      else:
          self._rp_forest = None
          leaf_array = np.array([[-1]])
  
      if self.max_candidates is None:
          effective_max_candidates = min(60, self.n_neighbors)
      else:
          effective_max_candidates = self.max_candidates
  
      # Set threading constraints
      self._original_num_threads = numba.get_num_threads()
      if self.n_jobs != -1 and self.n_jobs is not None:
          numba.set_num_threads(self.n_jobs)
  
      if isspmatrix_csr(self._raw_data):
          self._is_sparse = True
  
          if not self._raw_data.has_sorted_indices:
              self._raw_data.sort_indices()
  
          if metric in sparse.sparse_named_distances:
              if metric in sparse.sparse_fast_distance_alternatives:
                  _distance_func = (
                      sparse.sparse_fast_distance_alternatives[metric][
                          "dist"
                      ]
                  )
                  self._distance_correction = (
                      sparse.sparse_fast_distance_alternatives[metric][
                          "correction"
                      ]
                  )
              else:
                  _distance_func = sparse.sparse_named_distances[metric]
          elif callable(metric):
              _distance_func = metric
          else:
              raise ValueError(
                  "Metric {} not supported for sparse data".format(
                      metric
                  )
              )
  
          if metric in sparse.sparse_need_n_features:
              metric_kwds["n_features"] = self._raw_data.shape[1]
          self._dist_args = tuple(metric_kwds.values())
  
          # Create a partial function for distances with arguments
          if len(self._dist_args) > 0:
              dist_args = self._dist_args
  
              @numba.njit()
              def _partial_dist_func(ind1, data1, ind2, data2):
                  return _distance_func(
                      ind1, data1, ind2, data2, *dist_args
                  )
  
              self._distance_func = _partial_dist_func
          else:
              self._distance_func = _distance_func
  
          if init_graph is None:
              _init_graph = EMPTY_GRAPH
          else:
              if init_graph.shape[0] != self._raw_data.shape[0]:
                  raise ValueError(
                      "Init graph size does not match dataset size!"
                  )
              _init_graph = make_heap(
                  init_graph.shape[0], self.n_neighbors
              )
              _init_graph = sparse_initalize_heap_from_graph_indices(
                  _init_graph,
                  init_graph,
                  self._raw_data.indptr,
                  self._raw_data.indices,
                  self._raw_data.data,
                  self._distance_func,
              )
  
          if verbose:
              print(
                  ts(),
                  "metric NN descent for",
                  str(n_iters),
                  "iterations",
              )
  
          self._neighbor_graph = sparse_nnd.nn_descent(
              self._raw_data.indices,
              self._raw_data.indptr,
              self._raw_data.data,
              self.n_neighbors,
              self.rng_state,
              max_candidates=effective_max_candidates,
              dist=self._distance_func,
              n_iters=self.n_iters,
              delta=self.delta,
              rp_tree_init=True,
              leaf_array=leaf_array,
              init_graph=_init_graph,
              low_memory=self.low_memory,
              verbose=verbose,
          )
  
      else:
          self._is_sparse = False
  
          if init_graph is None:
              _init_graph = EMPTY_GRAPH
          else:
              if init_graph.shape[0] != self._raw_data.shape[0]:
                  raise ValueError(
                      "Init graph size does not match dataset size!"
                  )
              _init_graph = make_heap(
                  init_graph.shape[0], self.n_neighbors
              )
              if init_dist is None:
                  _init_graph = initalize_heap_from_graph_indices(
                      _init_graph, init_graph, data, self._distance_func
                  )
              elif init_graph.shape != init_dist.shape:
                  raise ValueError(
                      "The shapes of init graph and init distances do not match!"
                  )
              else:
                  _init_graph = (
                      initalize_heap_from_graph_indices_and_distances(
                          _init_graph, init_graph, init_dist
                      )
                  )
  
          if verbose:
              print(ts(), "NN descent for", str(n_iters), "iterations")
  
          self._neighbor_graph = nn_descent(
              self._raw_data,
              self.n_neighbors,
              self.rng_state,
              effective_max_candidates,
              self._distance_func,
              self.n_iters,
              self.delta,
              low_memory=self.low_memory,
              rp_tree_init=True,
              init_graph=_init_graph,
              leaf_array=leaf_array,
              verbose=verbose,
          )
  
      if np.any(self._neighbor_graph[0] < 0):
          warn(
              "Failed to correctly find n_neighbors for some samples."
              " Results may be less than ideal. Try re-running with"
              " different parameters."
          )
  
      numba.set_num_threads(self._original_num_threads)
  
imports: from warnings import warn
  import numba
  import numpy
  from sklearn.utils import check_random_state, check_array
  from sklearn.preprocessing import normalize
  from sklearn.base import BaseEstimator, TransformerMixin
  from scipy.sparse import csr_matrix, coo_matrix, isspmatrix_csr, vstack, issparse
  import heapq
  import pynndescent.sparse
  import pynndescent.sparse_nndescent
  import pynndescent.distances
  from pynndescent.utils import tau_rand_int, tau_rand, make_heap, deheap_sort, new_build_candidates, ts, simple_heap_push, checked_flagged_heap_push, has_been_visited, mark_visited, apply_graph_updates_high_memory, apply_graph_updates_low_memory, initalize_heap_from_graph_indices, initalize_heap_from_graph_indices_and_distances, sparse_initalize_heap_from_graph_indices
  from pynndescent.rp_trees import make_forest, rptree_leaf_array, convert_tree_format, FlatTree, denumbaify_tree, renumbaify_tree, select_side, sparse_select_side, score_linked_tree
label_desc: Use image node_id 1 to create a new NNDescent object  with example: obj = NNDescent(data, metric, metric_kwds, n_neighbors, n_trees, leaf_size, pruning_degree_multiplier, diversify_prob, n_search_trees, tree_init, init_graph, init_dist, random_state, low_memory, max_candidates, max_rptree_depth, n_iters, delta, n_jobs, compressed, parallel_batch_queries, verbose)