files: import numpy as np
  import numba
  import umap.distances as dist
  from umap.utils import tau_rand_int
  
  
  @numba.njit()
  def clip(val):
      """Standard clamping of a value into a fixed range (in this case -4.0 to
      4.0)
  
      Parameters
      ----------
      val: float
          The value to be clamped.
  
      Returns
      -------
      The clamped value, now fixed to be in the range -4.0 to 4.0.
      """
      if val > 4.0:
          return 4.0
      elif val < -4.0:
          return -4.0
      else:
          return val
  
  
  @numba.njit(
      "f4(f4[::1],f4[::1])",
      fastmath=True,
      cache=True,
      locals={
          "result": numba.types.float32,
          "diff": numba.types.float32,
          "dim": numba.types.intp,
      },
  )
  def rdist(x, y):
      """Reduced Euclidean distance.
  
      Parameters
      ----------
      x: array of shape (embedding_dim,)
      y: array of shape (embedding_dim,)
  
      Returns
      -------
      The squared euclidean distance between x and y
      """
      result = 0.0
      dim = x.shape[0]
      for i in range(dim):
          diff = x[i] - y[i]
          result += diff * diff
  
      return result
  
  
  def _optimize_layout_euclidean_single_epoch(
      head_embedding,
      tail_embedding,
      head,
      tail,
      n_vertices,
      epochs_per_sample,
      a,
      b,
      rng_state,
      gamma,
      dim,
      move_other,
      alpha,
      epochs_per_negative_sample,
      epoch_of_next_negative_sample,
      epoch_of_next_sample,
      n,
      densmap_flag,
      dens_phi_sum,
      dens_re_sum,
      dens_re_cov,
      dens_re_std,
      dens_re_mean,
      dens_lambda,
      dens_R,
      dens_mu,
      dens_mu_tot,
  ):
      for i in numba.prange(epochs_per_sample.shape[0]):
          if epoch_of_next_sample[i] <= n:
              j = head[i]
              k = tail[i]
  
              current = head_embedding[j]
              other = tail_embedding[k]
  
              dist_squared = rdist(current, other)
  
              if densmap_flag:
                  phi = 1.0 / (1.0 + a * pow(dist_squared, b))
                  dphi_term = (
                      a * b * pow(dist_squared, b - 1) / (1.0 + a * pow(dist_squared, b))
                  )
  
                  q_jk = phi / dens_phi_sum[k]
                  q_kj = phi / dens_phi_sum[j]
  
                  drk = q_jk * (
                      (1.0 - b * (1 - phi)) / np.exp(dens_re_sum[k]) + dphi_term
                  )
                  drj = q_kj * (
                      (1.0 - b * (1 - phi)) / np.exp(dens_re_sum[j]) + dphi_term
                  )
  
                  re_std_sq = dens_re_std * dens_re_std
                  weight_k = (
                      dens_R[k]
                      - dens_re_cov * (dens_re_sum[k] - dens_re_mean) / re_std_sq
                  )
                  weight_j = (
                      dens_R[j]
                      - dens_re_cov * (dens_re_sum[j] - dens_re_mean) / re_std_sq
                  )
  
                  grad_cor_coeff = (
                      dens_lambda
                      * dens_mu_tot
                      * (weight_k * drk + weight_j * drj)
                      / (dens_mu[i] * dens_re_std)
                      / n_vertices
                  )
  
              if dist_squared > 0.0:
                  grad_coeff = -2.0 * a * b * pow(dist_squared, b - 1.0)
                  grad_coeff /= a * pow(dist_squared, b) + 1.0
              else:
                  grad_coeff = 0.0
  
              for d in range(dim):
                  grad_d = clip(grad_coeff * (current[d] - other[d]))
  
                  if densmap_flag:
                      grad_d += clip(2 * grad_cor_coeff * (current[d] - other[d]))
  
                  current[d] += grad_d * alpha
                  if move_other:
                      other[d] += -grad_d * alpha
  
              epoch_of_next_sample[i] += epochs_per_sample[i]
  
              n_neg_samples = int(
                  (n - epoch_of_next_negative_sample[i]) / epochs_per_negative_sample[i]
              )
  
              for p in range(n_neg_samples):
                  k = tau_rand_int(rng_state) % n_vertices
  
                  other = tail_embedding[k]
  
                  dist_squared = rdist(current, other)
  
                  if dist_squared > 0.0:
                      grad_coeff = 2.0 * gamma * b
                      grad_coeff /= (0.001 + dist_squared) * (
                          a * pow(dist_squared, b) + 1
                      )
                  elif j == k:
                      continue
                  else:
                      grad_coeff = 0.0
  
                  for d in range(dim):
                      if grad_coeff > 0.0:
                          grad_d = clip(grad_coeff * (current[d] - other[d]))
                      else:
                          grad_d = 4.0
                      current[d] += grad_d * alpha
  
              epoch_of_next_negative_sample[i] += (
                  n_neg_samples * epochs_per_negative_sample[i]
              )
  
  
  def _optimize_layout_euclidean_densmap_epoch_init(
      head_embedding,
      tail_embedding,
      head,
      tail,
      a,
      b,
      re_sum,
      phi_sum,
  ):
      re_sum.fill(0)
      phi_sum.fill(0)
  
      for i in numba.prange(head.size):
          j = head[i]
          k = tail[i]
  
          current = head_embedding[j]
          other = tail_embedding[k]
          dist_squared = rdist(current, other)
  
          phi = 1.0 / (1.0 + a * pow(dist_squared, b))
  
          re_sum[j] += phi * dist_squared
          re_sum[k] += phi * dist_squared
          phi_sum[j] += phi
          phi_sum[k] += phi
  
      epsilon = 1e-8
      for i in range(re_sum.size):
          re_sum[i] = np.log(epsilon + (re_sum[i] / phi_sum[i]))
  
  
  def optimize_layout_euclidean(
      head_embedding,
      tail_embedding,
      head,
      tail,
      n_epochs,
      n_vertices,
      epochs_per_sample,
      a,
      b,
      rng_state,
      gamma=1.0,
      initial_alpha=1.0,
      negative_sample_rate=5.0,
      parallel=False,
      verbose=False,
      densmap=False,
      densmap_kwds={},
      move_other=False,
  ):
      """Improve an embedding using stochastic gradient descent to minimize the
      fuzzy set cross entropy between the 1-skeletons of the high dimensional
      and low dimensional fuzzy simplicial sets. In practice this is done by
      sampling edges based on their membership strength (with the (1-p) terms
      coming from negative sampling similar to word2vec).
      Parameters
      ----------
      head_embedding: array of shape (n_samples, n_components)
          The initial embedding to be improved by SGD.
      tail_embedding: array of shape (source_samples, n_components)
          The reference embedding of embedded points. If not embedding new
          previously unseen points with respect to an existing embedding this
          is simply the head_embedding (again); otherwise it provides the
          existing embedding to embed with respect to.
      head: array of shape (n_1_simplices)
          The indices of the heads of 1-simplices with non-zero membership.
      tail: array of shape (n_1_simplices)
          The indices of the tails of 1-simplices with non-zero membership.
      n_epochs: int, or list of int
          The number of training epochs to use in optimization, or a list of
          epochs at which to save the embedding. In case of a list, the optimization
          will use the maximum number of epochs in the list, and will return a list
          of embedding in the order of increasing epoch, regardless of the order in
          the epoch list.
      n_vertices: int
          The number of vertices (0-simplices) in the dataset.
      epochs_per_samples: array of shape (n_1_simplices)
          A float value of the number of epochs per 1-simplex. 1-simplices with
          weaker membership strength will have more epochs between being sampled.
      a: float
          Parameter of differentiable approximation of right adjoint
  
  [... the rest is omitted ...]
files: umap/layouts.py
files: import numpy as np
  import numba
  import umap.distances as dist
  from umap.utils import tau_rand_int
  
  
  @numba.njit()
  def clip(val):
      """Standard clamping of a value into a fixed range (in this case -4.0 to
      4.0)
  
      Parameters
      ----------
      val: float
          The value to be clamped.
  
      Returns
      -------
      The clamped value, now fixed to be in the range -4.0 to 4.0.
      """
      if val > 4.0:
          return 4.0
      elif val < -4.0:
          return -4.0
      else:
          return val
  
  
  @numba.njit(
      "f4(f4[::1],f4[::1])",
      fastmath=True,
      cache=True,
      locals={
          "result": numba.types.float32,
          "diff": numba.types.float32,
          "dim": numba.types.intp,
      },
  )
  def rdist(x, y):
      """Reduced Euclidean distance.
  
      Parameters
      ----------
      x: array of shape (embedding_dim,)
      y: array of shape (embedding_dim,)
  
      Returns
      -------
      The squared euclidean distance between x and y
      """
      result = 0.0
      dim = x.shape[0]
      for i in range(dim):
          diff = x[i] - y[i]
          result += diff * diff
  
      return result
  
  
  def _optimize_layout_euclidean_single_epoch(
      head_embedding,
      tail_embedding,
      head,
      tail,
      n_vertices,
      epochs_per_sample,
      a,
      b,
      rng_state,
      gamma,
      dim,
      move_other,
      alpha,
      epochs_per_negative_sample,
      epoch_of_next_negative_sample,
      epoch_of_next_sample,
      n,
      densmap_flag,
      dens_phi_sum,
      dens_re_sum,
      dens_re_cov,
      dens_re_std,
      dens_re_mean,
      dens_lambda,
      dens_R,
      dens_mu,
      dens_mu_tot,
  ):
      for i in numba.prange(epochs_per_sample.shape[0]):
          if epoch_of_next_sample[i] <= n:
              j = head[i]
              k = tail[i]
  
              current = head_embedding[j]
              other = tail_embedding[k]
  
              dist_squared = rdist(current, other)
  
              if densmap_flag:
                  phi = 1.0 / (1.0 + a * pow(dist_squared, b))
                  dphi_term = (
                      a * b * pow(dist_squared, b - 1) / (1.0 + a * pow(dist_squared, b))
                  )
  
                  q_jk = phi / dens_phi_sum[k]
                  q_kj = phi / dens_phi_sum[j]
  
                  drk = q_jk * (
                      (1.0 - b * (1 - phi)) / np.exp(dens_re_sum[k]) + dphi_term
                  )
                  drj = q_kj * (
                      (1.0 - b * (1 - phi)) / np.exp(dens_re_sum[j]) + dphi_term
                  )
  
                  re_std_sq = dens_re_std * dens_re_std
                  weight_k = (
                      dens_R[k]
                      - dens_re_cov * (dens_re_sum[k] - dens_re_mean) / re_std_sq
                  )
                  weight_j = (
                      dens_R[j]
                      - dens_re_cov * (dens_re_sum[j] - dens_re_mean) / re_std_sq
                  )
  
                  grad_cor_coeff = (
                      dens_lambda
                      * dens_mu_tot
                      * (weight_k * drk + weight_j * drj)
                      / (dens_mu[i] * dens_re_std)
                      / n_vertices
                  )
  
              if dist_squared > 0.0:
                  grad_coeff = -2.0 * a * b * pow(dist_squared, b - 1.0)
                  grad_coeff /= a * pow(dist_squared, b) + 1.0
              else:
                  grad_coeff = 0.0
  
              for d in range(dim):
                  grad_d = clip(grad_coeff * (current[d] - other[d]))
  
                  if densmap_flag:
                      grad_d += clip(2 * grad_cor_coeff * (current[d] - other[d]))
  
                  current[d] += grad_d * alpha
                  if move_other:
                      other[d] += -grad_d * alpha
  
              epoch_of_next_sample[i] += epochs_per_sample[i]
  
              n_neg_samples = int(
                  (n - epoch_of_next_negative_sample[i]) / epochs_per_negative_sample[i]
              )
  
              for p in range(n_neg_samples):
                  k = tau_rand_int(rng_state) % n_vertices
  
                  other = tail_embedding[k]
  
                  dist_squared = rdist(current, other)
  
                  if dist_squared > 0.0:
                      grad_coeff = 2.0 * gamma * b
                      grad_coeff /= (0.001 + dist_squared) * (
                          a * pow(dist_squared, b) + 1
                      )
                  elif j == k:
                      continue
                  else:
                      grad_coeff = 0.0
  
                  for d in range(dim):
                      if grad_coeff > 0.0:
                          grad_d = clip(grad_coeff * (current[d] - other[d]))
                      else:
                          grad_d = 4.0
                      current[d] += grad_d * alpha
  
              epoch_of_next_negative_sample[i] += (
                  n_neg_samples * epochs_per_negative_sample[i]
              )
  
  
  def _optimize_layout_euclidean_densmap_epoch_init(
      head_embedding,
      tail_embedding,
      head,
      tail,
      a,
      b,
      re_sum,
      phi_sum,
  ):
      re_sum.fill(0)
      phi_sum.fill(0)
  
      for i in numba.prange(head.size):
          j = head[i]
          k = tail[i]
  
          current = head_embedding[j]
          other = tail_embedding[k]
          dist_squared = rdist(current, other)
  
          phi = 1.0 / (1.0 + a * pow(dist_squared, b))
  
          re_sum[j] += phi * dist_squared
          re_sum[k] += phi * dist_squared
          phi_sum[j] += phi
          phi_sum[k] += phi
  
      epsilon = 1e-8
      for i in range(re_sum.size):
          re_sum[i] = np.log(epsilon + (re_sum[i] / phi_sum[i]))
  
  
  def optimize_layout_euclidean(
      head_embedding,
      tail_embedding,
      head,
      tail,
      n_epochs,
      n_vertices,
      epochs_per_sample,
      a,
      b,
      rng_state,
      gamma=1.0,
      initial_alpha=1.0,
      negative_sample_rate=5.0,
      parallel=False,
      verbose=False,
      densmap=False,
      densmap_kwds={},
      move_other=False,
  ):
      """Improve an embedding using stochastic gradient descent to minimize the
      fuzzy set cross entropy between the 1-skeletons of the high dimensional
      and low dimensional fuzzy simplicial sets. In practice this is done by
      sampling edges based on their membership strength (with the (1-p) terms
      coming from negative sampling similar to word2vec).
      Parameters
      ----------
      head_embedding: array of shape (n_samples, n_components)
          The initial embedding to be improved by SGD.
      tail_embedding: array of shape (source_samples, n_components)
          The reference embedding of embedded points. If not embedding new
          previously unseen points with respect to an existing embedding this
          is simply the head_embedding (again); otherwise it provides the
          existing embedding to embed with respect to.
      head: array of shape (n_1_simplices)
          The indices of the heads of 1-simplices with non-zero membership.
      tail: array of shape (n_1_simplices)
          The indices of the tails of 1-simplices with non-zero membership.
      n_epochs: int
          The number of training epochs to use in optimization.
      n_vertices: int
          The number of vertices (0-simplices) in the dataset.
      epochs_per_samples: array of shape (n_1_simplices)
          A float value of the number of epochs per 1-simplex. 1-simplices with
          weaker membership strength will have more epochs between being sampled.
      a: float
          Parameter of differentiable approximation of right adjoint functor
      b: float
          Parameter of differentiable approximation of right adjoint functor
      rng_state: array of int64, shape (3,)
          The internal state of the rng
      gamma: float (optional, default 1.0)
          Weight to apply to negative samples.
      initial
  
  [... the rest is omitted ...]
files: umap/layouts.py
files: # Author: Leland McInnes <leland.mcinnes@gmail.com>
  #
  # License: BSD 3 clause
  from __future__ import print_function
  
  import locale
  from warnings import warn
  import time
  
  from scipy.optimize import curve_fit
  from sklearn.base import BaseEstimator
  from sklearn.utils import check_random_state, check_array
  from sklearn.utils.validation import check_is_fitted
  from sklearn.metrics import pairwise_distances
  from sklearn.preprocessing import normalize
  from sklearn.neighbors import KDTree
  
  try:
      import joblib
  except ImportError:
      # sklearn.externals.joblib is deprecated in 0.21, will be removed in 0.23
      from sklearn.externals import joblib
  
  import numpy as np
  import scipy.sparse
  from scipy.sparse import tril as sparse_tril, triu as sparse_triu
  import scipy.sparse.csgraph
  import numba
  
  import umap.distances as dist
  
  import umap.sparse as sparse
  
  from umap.utils import (
      submatrix,
      ts,
      csr_unique,
      fast_knn_indices,
  )
  from umap.spectral import spectral_layout
  from umap.layouts import (
      optimize_layout_euclidean,
      optimize_layout_generic,
      optimize_layout_inverse,
  )
  
  from pynndescent import NNDescent
  from pynndescent.distances import named_distances as pynn_named_distances
  from pynndescent.sparse import sparse_named_distances as pynn_sparse_named_distances
  
  locale.setlocale(locale.LC_NUMERIC, "C")
  
  INT32_MIN = np.iinfo(np.int32).min + 1
  INT32_MAX = np.iinfo(np.int32).max - 1
  
  SMOOTH_K_TOLERANCE = 1e-5
  MIN_K_DIST_SCALE = 1e-3
  NPY_INFINITY = np.inf
  
  DISCONNECTION_DISTANCES = {
      "correlation": 2,
      "cosine": 2,
      "hellinger": 1,
      "jaccard": 1,
      "dice": 1,
  }
  
  
  def flatten_iter(container):
      for i in container:
          if isinstance(i, (list, tuple)):
              for j in flatten_iter(i):
                  yield j
          else:
              yield i
  
  
  def flattened(container):
      return tuple(flatten_iter(container))
  
  
  def breadth_first_search(adjmat, start, min_vertices):
      explored = []
      queue = [start]
      levels = {}
      levels[start] = 0
      max_level = np.inf
      visited = [start]
  
      while queue:
          node = queue.pop(0)
          explored.append(node)
          if max_level == np.inf and len(explored) > min_vertices:
              max_level = max(levels.values())
  
          if levels[node] + 1 < max_level:
              neighbors = adjmat[node].indices
              for neighbour in neighbors:
                  if neighbour not in visited:
                      queue.append(neighbour)
                      visited.append(neighbour)
  
                      levels[neighbour] = levels[node] + 1
  
      return np.array(explored)
  
  
  def raise_disconnected_warning(
      edges_removed,
      vertices_disconnected,
      disconnection_distance,
      total_rows,
      threshold=0.1,
      verbose=False,
  ):
      """A simple wrapper function to avoid large amounts of code repetition."""
      if verbose & (vertices_disconnected == 0) & (edges_removed > 0):
          print(
              f"Disconnection_distance = {disconnection_distance} has removed {edges_removed} edges.  "
              f"This is not a problem as no vertices were disconnected."
          )
      elif (vertices_disconnected > 0) & (
          vertices_disconnected <= threshold * total_rows
      ):
          warn(
              f"A few of your vertices were disconnected from the manifold.  This shouldn't cause problems.\n"
              f"Disconnection_distance = {disconnection_distance} has removed {edges_removed} edges.\n"
              f"It has only fully disconnected {vertices_disconnected} vertices.\n"
              f"Use umap.utils.disconnected_vertices() to identify them.",
          )
      elif vertices_disconnected > threshold * total_rows:
          warn(
              f"A large number of your vertices were disconnected from the manifold.\n"
              f"Disconnection_distance = {disconnection_distance} has removed {edges_removed} edges.\n"
              f"It has fully disconnected {vertices_disconnected} vertices.\n"
              f"You might consider using find_disconnected_points() to find and remove these points from your data.\n"
              f"Use umap.utils.disconnected_vertices() to identify them.",
          )
  
  
  @numba.njit(
      locals={
          "psum": numba.types.float32,
          "lo": numba.types.float32,
          "mid": numba.types.float32,
          "hi": numba.types.float32,
      },
      fastmath=True,
  )  # benchmarking `parallel=True` shows it to *decrease* performance
  def smooth_knn_dist(distances, k, n_iter=64, local_connectivity=1.0, bandwidth=1.0):
      """Compute a continuous version of the distance to the kth nearest
      neighbor. That is, this is similar to knn-distance but allows continuous
      k values rather than requiring an integral k. In essence we are simply
      computing the distance such that the cardinality of fuzzy set we generate
      is k.
  
      Parameters
      ----------
      distances: array of shape (n_samples, n_neighbors)
          Distances to nearest neighbors for each samples. Each row should be a
          sorted list of distances to a given samples nearest neighbors.
  
      k: float
          The number of nearest neighbors to approximate for.
  
      n_iter: int (optional, default 64)
          We need to binary search for the correct distance value. This is the
          max number of iterations to use in such a search.
  
      local_connectivity: int (optional, default 1)
          The local connectivity required -- i.e. the number of nearest
          neighbors that should be assumed to be connected at a local level.
          The higher this value the more connected the manifold becomes
          locally. In practice this should be not more than the local intrinsic
          dimension of the manifold.
  
      bandwidth: float (optional, default 1)
          The target bandwidth of the kernel, larger values will produce
          larger return values.
  
      Returns
      -------
      knn_dist: array of shape (n_samples,)
          The distance to kth nearest neighbor, as suitably approximated.
  
      nn_dist: array of shape (n_samples,)
          The distance to the 1st nearest neighbor for each point.
      """
      target = np.log2(k) * bandwidth
      rho = np.zeros(distances.shape[0], dtype=np.float32)
      result = np.zeros(distances.shape[0], dtype=np.float32)
  
      mean_distances = np.mean(distances)
  
      for i in range(distances.shape[0]):
          lo = 0.0
          hi = NPY_INFINITY
          mid = 1.0
  
          # TODO: This is very inefficient, but will do for now. FIXME
          ith_distances = distances[i]
          non_zero_dists = ith_distances[ith_distances > 0.0]
          if non_zero_dists.shape[0] >= local_connectivity:
              index = int(np.floor(local_connectivity))
              interpolation = local_connectivity - index
              if index > 0:
                  rho[i] = non_zero_dists[index - 1]
                  if interpolation > SMOOTH_K_TOLERANCE:
                      rho[i] += interpolation * (
                          non_zero_dists[index] - non_zero_dists[index - 1]
                      )
              else:
                  rho[i] = interpolation * non_zero_dists[0]
          elif non_zero_dists.shape[0] > 0:
              rho[i] = np.max(non_zero_dists)
  
          for n in range(n_iter):
  
              psum = 0.0
              for j in range(1, distances.shape[1]):
                  d = distances[i, j] - rho[i]
                  if d > 0:
                      psum += np.exp(-(d / mid))
                  else:
                      psum += 1.0
  
              if np.fabs(psum - target) < SMOOTH_K_TOLERANCE:
                  break
  
              if psum > target:
                  hi = mid
                  mid = (lo + hi) / 2.0
              else:
                  lo = mid
                  if hi == NPY_INFINITY:
                      mid *= 2
                  else:
                      mid = (lo + hi) / 2.0
  
          result[i] = mid
  
          # TODO: This is very inefficient, but will do for now. FIXME
          if rho[i] > 0.0:
              mean_ith_distances = np.mean(ith_distances)
              if result[i] < MIN_K_DIST_SCALE * mean_ith_distances:
                  result[i] = MIN_K_DIST_SCALE * mean_ith_dist
  
  [... the rest is omitted ...]
files: umap/umap_.py
files: # Author: Leland McInnes <leland.mcinnes@gmail.com>
  #
  # License: BSD 3 clause
  from __future__ import print_function
  
  import locale
  from warnings import warn
  import time
  
  from scipy.optimize import curve_fit
  from sklearn.base import BaseEstimator
  from sklearn.utils import check_random_state, check_array
  from sklearn.utils.validation import check_is_fitted
  from sklearn.metrics import pairwise_distances
  from sklearn.preprocessing import normalize
  from sklearn.neighbors import KDTree
  
  try:
      import joblib
  except ImportError:
      # sklearn.externals.joblib is deprecated in 0.21, will be removed in 0.23
      from sklearn.externals import joblib
  
  import numpy as np
  import scipy.sparse
  from scipy.sparse import tril as sparse_tril, triu as sparse_triu
  import scipy.sparse.csgraph
  import numba
  
  import umap.distances as dist
  
  import umap.sparse as sparse
  
  from umap.utils import (
      submatrix,
      ts,
      csr_unique,
      fast_knn_indices,
  )
  from umap.spectral import spectral_layout
  from umap.layouts import (
      optimize_layout_euclidean,
      optimize_layout_generic,
      optimize_layout_inverse,
  )
  
  from pynndescent import NNDescent
  from pynndescent.distances import named_distances as pynn_named_distances
  from pynndescent.sparse import sparse_named_distances as pynn_sparse_named_distances
  
  locale.setlocale(locale.LC_NUMERIC, "C")
  
  INT32_MIN = np.iinfo(np.int32).min + 1
  INT32_MAX = np.iinfo(np.int32).max - 1
  
  SMOOTH_K_TOLERANCE = 1e-5
  MIN_K_DIST_SCALE = 1e-3
  NPY_INFINITY = np.inf
  
  DISCONNECTION_DISTANCES = {
      "correlation": 2,
      "cosine": 2,
      "hellinger": 1,
      "jaccard": 1,
      "dice": 1,
  }
  
  
  def flatten_iter(container):
      for i in container:
          if isinstance(i, (list, tuple)):
              for j in flatten_iter(i):
                  yield j
          else:
              yield i
  
  
  def flattened(container):
      return tuple(flatten_iter(container))
  
  
  def breadth_first_search(adjmat, start, min_vertices):
      explored = []
      queue = [start]
      levels = {}
      levels[start] = 0
      max_level = np.inf
      visited = [start]
  
      while queue:
          node = queue.pop(0)
          explored.append(node)
          if max_level == np.inf and len(explored) > min_vertices:
              max_level = max(levels.values())
  
          if levels[node] + 1 < max_level:
              neighbors = adjmat[node].indices
              for neighbour in neighbors:
                  if neighbour not in visited:
                      queue.append(neighbour)
                      visited.append(neighbour)
  
                      levels[neighbour] = levels[node] + 1
  
      return np.array(explored)
  
  
  def raise_disconnected_warning(
      edges_removed,
      vertices_disconnected,
      disconnection_distance,
      total_rows,
      threshold=0.1,
      verbose=False,
  ):
      """A simple wrapper function to avoid large amounts of code repetition."""
      if verbose & (vertices_disconnected == 0) & (edges_removed > 0):
          print(
              f"Disconnection_distance = {disconnection_distance} has removed {edges_removed} edges.  "
              f"This is not a problem as no vertices were disconnected."
          )
      elif (vertices_disconnected > 0) & (
          vertices_disconnected <= threshold * total_rows
      ):
          warn(
              f"A few of your vertices were disconnected from the manifold.  This shouldn't cause problems.\n"
              f"Disconnection_distance = {disconnection_distance} has removed {edges_removed} edges.\n"
              f"It has only fully disconnected {vertices_disconnected} vertices.\n"
              f"Use umap.utils.disconnected_vertices() to identify them.",
          )
      elif vertices_disconnected > threshold * total_rows:
          warn(
              f"A large number of your vertices were disconnected from the manifold.\n"
              f"Disconnection_distance = {disconnection_distance} has removed {edges_removed} edges.\n"
              f"It has fully disconnected {vertices_disconnected} vertices.\n"
              f"You might consider using find_disconnected_points() to find and remove these points from your data.\n"
              f"Use umap.utils.disconnected_vertices() to identify them.",
          )
  
  
  @numba.njit(
      locals={
          "psum": numba.types.float32,
          "lo": numba.types.float32,
          "mid": numba.types.float32,
          "hi": numba.types.float32,
      },
      fastmath=True,
  )  # benchmarking `parallel=True` shows it to *decrease* performance
  def smooth_knn_dist(distances, k, n_iter=64, local_connectivity=1.0, bandwidth=1.0):
      """Compute a continuous version of the distance to the kth nearest
      neighbor. That is, this is similar to knn-distance but allows continuous
      k values rather than requiring an integral k. In essence we are simply
      computing the distance such that the cardinality of fuzzy set we generate
      is k.
  
      Parameters
      ----------
      distances: array of shape (n_samples, n_neighbors)
          Distances to nearest neighbors for each samples. Each row should be a
          sorted list of distances to a given samples nearest neighbors.
  
      k: float
          The number of nearest neighbors to approximate for.
  
      n_iter: int (optional, default 64)
          We need to binary search for the correct distance value. This is the
          max number of iterations to use in such a search.
  
      local_connectivity: int (optional, default 1)
          The local connectivity required -- i.e. the number of nearest
          neighbors that should be assumed to be connected at a local level.
          The higher this value the more connected the manifold becomes
          locally. In practice this should be not more than the local intrinsic
          dimension of the manifold.
  
      bandwidth: float (optional, default 1)
          The target bandwidth of the kernel, larger values will produce
          larger return values.
  
      Returns
      -------
      knn_dist: array of shape (n_samples,)
          The distance to kth nearest neighbor, as suitably approximated.
  
      nn_dist: array of shape (n_samples,)
          The distance to the 1st nearest neighbor for each point.
      """
      target = np.log2(k) * bandwidth
      rho = np.zeros(distances.shape[0], dtype=np.float32)
      result = np.zeros(distances.shape[0], dtype=np.float32)
  
      mean_distances = np.mean(distances)
  
      for i in range(distances.shape[0]):
          lo = 0.0
          hi = NPY_INFINITY
          mid = 1.0
  
          # TODO: This is very inefficient, but will do for now. FIXME
          ith_distances = distances[i]
          non_zero_dists = ith_distances[ith_distances > 0.0]
          if non_zero_dists.shape[0] >= local_connectivity:
              index = int(np.floor(local_connectivity))
              interpolation = local_connectivity - index
              if index > 0:
                  rho[i] = non_zero_dists[index - 1]
                  if interpolation > SMOOTH_K_TOLERANCE:
                      rho[i] += interpolation * (
                          non_zero_dists[index] - non_zero_dists[index - 1]
                      )
              else:
                  rho[i] = interpolation * non_zero_dists[0]
          elif non_zero_dists.shape[0] > 0:
              rho[i] = np.max(non_zero_dists)
  
          for n in range(n_iter):
  
              psum = 0.0
              for j in range(1, distances.shape[1]):
                  d = distances[i, j] - rho[i]
                  if d > 0:
                      psum += np.exp(-(d / mid))
                  else:
                      psum += 1.0
  
              if np.fabs(psum - target) < SMOOTH_K_TOLERANCE:
                  break
  
              if psum > target:
                  hi = mid
                  mid = (lo + hi) / 2.0
              else:
                  lo = mid
                  if hi == NPY_INFINITY:
                      mid *= 2
                  else:
                      mid = (lo + hi) / 2.0
  
          result[i] = mid
  
          # TODO: This is very inefficient, but will do for now. FIXME
          if rho[i] > 0.0:
              mean_ith_distances = np.mean(ith_distances)
              if result[i] < MIN_K_DIST_SCALE * mean_ith_distances:
                  result[i] = MIN_K_DIST_SCALE * mean_ith_dist
  
  [... the rest is omitted ...]
files: umap/umap_.py