SizeBoundedGraph

The SizeBoundedGraph class is an implementation for MutableGraph and is used to build graphs.

class deglib.graph.SizeBoundedGraph(max_vertex_count: int, edges_per_vertex: int, feature_space: FloatSpace, graph_cpp: SizeBoundedGraph | None = None)

Bases: MutableGraph

static create_empty(capacity: int, dims: int, edges_per_vertex: int = 32, metric: Metric = Metric.L2)

Create an empty SizeBoundedGraph.

Parameters:

  • capacity – The maximal number of vertices of this graph.

  • dims – The number of dimensions of each feature vector

  • edges_per_vertex – Number of neighbors for each vertex. Defaults to 32.

  • metric – The metric to measure distances between features. Defaults to L2-Metric.

size() → int
Returns:

the number of vertices in the graph

get_feature_space() → FloatSpace
Returns:

the feature space

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

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

get_entry_vertex_indices() → List[int]

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

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

save_graph(path: Path | str)

Save graph to specified file. Creates necessary directories.

Parameters:

path – The path where to save the file.

get_edges_per_vertex() → int
Returns:

the number of edges of each vertex

add_vertex(external_label: int, feature_vector: ndarray) → int

Add a new vertex. The neighbor indices will be prefilled with a self-loop, the weights will be 0.

Parameters:

  • external_label – The label for the new vertex

  • feature_vector – The feature vector to add. This numpy array should be c-contiguous, otherwise it has to be reallocated.

Returns:

the internal index of the new vertex

remove_vertex(external_label: int)

Remove an existing vertex.

Parameters:

external_label – The external label of the vertex that should be removed.

change_edge(internal_index: int, from_neighbor_index: int, to_neighbor_index: int, to_neighbor_weight: float) → bool

Swap a neighbor with another neighbor and its weight.

Parameters:

  • internal_index – vertex index which neighbors should be changed

  • from_neighbor_index – neighbor index to remove

  • to_neighbor_index – neighbor index to add

  • to_neighbor_weight – weight of the neighbor to add

Returns:

True if the from_neighbor_index was found and changed

change_edges(internal_index: int, neighbor_indices: ndarray, neighbor_weights: ndarray)

Change all edges of a vertex. The neighbor indices/weights and feature vectors will be copied. The neighbor array need to have enough neighbors to match the edge-per-vertex count of the graph. The indices in the neighbor_indices array must be sorted.

Parameters:

  • internal_index – The index of the vertex for which edges should change

  • neighbor_indices – These neighbors will be set as the new neighbors of the specified vertex

  • neighbor_weights – These weights will be set as the new weights for the neighbors.

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

Get weights for each neighbor of the vertex defined by the given index.

Parameters:

  • internal_index – The index that specifies the vertex

  • copy – If True the returned neighbor weights are copied, otherwise they reference internal graph data.

Returns:

The weights of the neighbors

get_edge_weight(from_neighbor_index: int, to_neighbor_index: int) → float

Get the weight from vertex to another vertex. If start vertex is not a neighbor of end vertex, -1.0 is returned.

Parameters:

  • from_neighbor_index – Internal index of the start vertex

  • to_neighbor_index – Internal index of the target vertex

Returns:

If present the weight between start and target vertex, -1.0 otherwise

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

has_vertex(external_label: int) → bool
Returns:

whether the given external label is present in the graph.

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.

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.