class_docstr: Find closest anchors using :mod:`scipy.sparse`.
class_docstr_tok: ["Find","closest","anchors","using",":","mod",":","`","scipy.sparse","`","."]
docstr: Determine the candidate pool using breadth-first search.
  
  :param anchors: shape: (a,)
      the anchor node IDs
  :param adjacency: shape: (n, n)
      the adjacency matrix
  :param max_iter:
      the maximum number of hops to consider
  :param k:
      the minimum number of anchor nodes to reach
  
  :return: shape: (n, a)
      a boolean array indicating whether anchor $j$ is in the set of $k$ closest anchors for node $i$
docstr_tok: ["Determine","the","candidate","pool","using","breadth-first","search",".",":","param","anchors",":","shape",":","(","a",",",")","the","anchor","node","IDs",":","param","adjacency",":","shape",":","(","n",",","n",")","the","adjacency","matrix",":","param","max_iter",":","the","maximum","number","of","hops","to","consider",":","param","k",":","the","minimum","number","of","anchor","nodes","to","reach",":","return",":","shape",":","(","n",",","a",")","a","boolean","array","indicating","whether","anchor","$","j","$","is","in","the","set","of","$","k","$","closest","anchors","for","node","$","i","$"]
code: def bfs(
      anchors: numpy.ndarray,
      adjacency: scipy.sparse.spmatrix,
      max_iter: int,
      k: int,
  ) -> numpy.ndarray:
      """
      Determine the candidate pool using breadth-first search.
  
      :param anchors: shape: (a,)
          the anchor node IDs
      :param adjacency: shape: (n, n)
          the adjacency matrix
      :param max_iter:
          the maximum number of hops to consider
      :param k:
          the minimum number of anchor nodes to reach
  
      :return: shape: (n, a)
          a boolean array indicating whether anchor $j$ is in the set of $k$ closest anchors for node $i$
      """
      num_entities = adjacency.shape[0]
      # for each entity, determine anchor pool by BFS
      num_anchors = len(anchors)
  
      # an array storing whether node i is reachable by anchor j
      reachable = numpy.zeros(
          shape=(num_entities, num_anchors), dtype=bool
      )
      reachable[anchors] = numpy.eye(num_anchors, dtype=bool)
  
      # an array indicating whether a node is closed, i.e., has found at least $k$ anchors
      final = numpy.zeros(shape=(num_entities,), dtype=bool)
  
      # the output
      pool = numpy.zeros(shape=(num_entities, num_anchors), dtype=bool)
      # anchor nodes have themselves as a starting found anchor
      pool[anchors] = numpy.eye(num_anchors, dtype=bool)
  
      # TODO: take all (q-1) hop neighbors before selecting from q-hop
      old_reachable = reachable
      for i in range(max_iter):
          # propagate one hop
          reachable = adjacency.dot(reachable)
          # convergence check
          if (reachable == old_reachable).all():
              logger.warning(
                  f"Search converged after iteration {i} without all nodes being reachable."
              )
              break
          old_reachable = reachable
          # copy pool if we have seen enough anchors and have not yet stopped
          num_reachable = reachable.sum(axis=1)
          enough = num_reachable >= k
          mask = enough & ~final
          logger.debug(
              f"Iteration {i}: {format_relative_comparison(enough.sum(), total=num_entities)} closed nodes.",
          )
          pool[mask] = reachable[mask]
          # stop once we have enough
          final |= enough
          if final.all():
              break
      return pool
  
imports: import logging
  from abc import ABC, abstractmethod
  from typing import Iterable, Optional
  import numpy
  import scipy.sparse
  import torch
  from class_resolver import ClassResolver, OptionalKwargs
  from torch_ppr import page_rank
  from torch_ppr.utils import edge_index_to_sparse_matrix, prepare_page_rank_adjacency, prepare_x0
  from tqdm.auto import tqdm
  from .utils import ensure_num_entities
  from ...typing import DeviceHint
  from ...utils import ExtraReprMixin, format_relative_comparison, resolve_device
label_desc: Use image node_id 4 for calling the ScipySparseAnchorSearcher obj's underlying member method code with example usage: obj.bfs(anchors, adjacency, max_iter, k) and returns: pool