Skip to content

search_graph

Jump to bottom
Bluemi edited this page Sep 5, 2025 · 1 revision

SearchGraph

The SearchGraph class defines an abstract interface for all graph classes.

class deglib.graph.SearchGraph(graph_cpp: SearchGraph)

Bases: ABC

search(query: ndarray, eps: float, k: int, filter_labels: None | ndarray | Filter = None, max_distance_computation_count: int = 0, entry_vertex_indices: List[int] | None = None, threads: int = 1, thread_batch_size: int = 0) → Tuple[ndarray, ndarray]

Approximate nearest neighbor search based on yahoo’s range search algorithm for graphs.

Eps greater 0 extends the search range and takes additional graph vertices into account.

It is possible to limit the amount of work by specifying a maximal number of distances to be calculated. For lower numbers it is recommended to set eps to 0 since its very unlikely the method can make use of the extended the search range.

  • Parameters:
    • query – A feature vector for which similar feature vectors should searched.
    • eps – Controls how many nodes are checked during search. Lower eps values like 0.001 are faster but less accurate. Higher eps values like 0.1 are slower but more accurate. Should always be greater 0.
    • k – The number of results that will be returned. If k is smaller than the number of vertices in the graph, k is set to the number of vertices in the graph.
    • filter_labels – A numpy array with dtype int32, that contains all labels that can be returned or an object of type Filter, that limits the possible results to a given set. All other labels will not be included in the result set.
    • max_distance_computation_count – Limit the number of distance calculations. If set to 0 this is ignored.
    • entry_vertex_indices – Start point for exploratory search. If None, a reasonable default is used.
    • threads – The number of threads to use for parallel processing. It should not excel the number of queries. If set to 0, the minimum of the number of cores of this machine and the number of queries is used.
    • thread_batch_size – If threads != 1, the number of queries to search in the same thread.
  • Returns: A tuple containing (indices, distances) where indices is a numpy-array of shape [n_queries, k] containing the indices to the closest found neighbors to the queries. Distances is a numpy-array of shape [n_queries, k] containing the distances to the closest found neighbors.

abstractmethod size() → int

  • Returns: the number of vertices in the graph

abstractmethod get_edges_per_vertex() → int

  • Returns: the number of edges of each vertex

abstractmethod get_feature_space() → SpaceInterface

  • Returns: the feature space

abstractmethod get_external_label(internal_index: int) → int

Translates external labels to internal index

  • Parameters: internal_index – The internal index to translate
  • Returns: The external label

abstractmethod get_internal_index(external_label: int) → int

Translates internal index to external label

  • Parameters: external_label – The external label to translate
  • Returns: The internal index

abstractmethod get_neighbor_indices(internal_index: int, copy: bool = False) → ndarray

Get the indices (internal index) of the given vertex.

  • Parameters:
    • internal_index – The internal index to get the neighbors of
    • copy – If True the returned neighbor indices are a copy, otherwise they reference internal graph data.
  • Returns: The internal index

get_feature_vector(index: int, copy: bool = False) → ndarray

Get the feature vector of the given internal index.

  • Parameters:
    • index – The internal index to get the feature vector of
    • copy – If True the returned feature vector is a copy, otherwise a reference to the graph data is returned.
  • Returns: The feature vector of the given index

abstractmethod has_vertex(external_label: int) → bool

  • Returns: whether the given external label is present in the graph.

abstractmethod has_edge(internal_index: int, neighbor_index: int) → bool

  • Returns: whether the vertex at internal_index has an edge to the vertex at neighbor_index.

get_entry_vertex_indices() → List[int]

Creates a list of internal indices that can be used as starting point for an anns search.

abstractmethod has_path(entry_vertex_indices: List[int], to_vertex: int, eps: float, k: int) → List[ObjectDistance]

Returns a path from one of the entry vertex indices to the given to_vertex.

  • Parameters:
    • entry_vertex_indices – List of start vertices
    • to_vertex – The vertex to find a path to
    • eps – Controls how many nodes are checked during search. Lower eps values like 0.001 are faster but less accurate. Higher eps values like 0.1 are slower but more accurate. Should always be greater 0.
    • k – TODO

abstractmethod explore(entry_vertex_index: int, k: int, include_entry: bool, max_distance_computation_count: int) → ResultSet

An exploration for similar element, limited by max_distance_computation_count

  • Parameters:
    • entry_vertex_index – The start point for which similar feature vectors should be searched
    • k – The number of similar feature vectors to return
    • include_entry – If True, the entry vertex is included in the result set.
    • max_distance_computation_count – Limit the number of distance calculations. If set to 0 this is ignored.

Clone this wiki locally