Repository navigation
Expand file tree
/
Copy pathgraph.py
More file actions
722 lines (592 loc) · 30.7 KB
/
Copy pathgraph.py
File metadata and controls
722 lines (592 loc) · 30.7 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
import os
import multiprocessing
from typing import List, Optional, Tuple, Self
from abc import ABC, abstractmethod
import numpy as np
import deglib_cpp
import pathlib
from .distances import FloatSpace, Metric, SpaceInterface
from .search import ResultSet, ObjectDistance
from .utils import assure_array, InvalidShapeException
# TODO: safety checks
class SearchGraph(ABC):
@abstractmethod
def size(self) -> int:
"""
:return: the number of vertices in the graph
"""
raise NotImplementedError()
@abstractmethod
def get_edges_per_vertex(self) -> int:
"""
:return: the number of edges of each vertex
"""
raise NotImplementedError()
@abstractmethod
def get_feature_space(self) -> SpaceInterface:
"""
:return: the feature space
"""
raise NotImplementedError()
@abstractmethod
def get_external_label(self, internal_index: int) -> int:
"""
Translates external labels to internal index
:param internal_index: The internal index to translate
:returns: The external label
"""
raise NotImplementedError()
@abstractmethod
def get_internal_index(self, external_label: int) -> int:
"""
Translates internal index to external label
:param external_label: The external label to translate
:returns: The internal index
"""
raise NotImplementedError()
@abstractmethod
def get_neighbor_indices(self, internal_index: int, copy: bool = False) -> np.ndarray:
"""
Get the indices (internal index) of the given vertex.
:param internal_index: The internal index to get the neighbors of
:param copy: If True the returned neighbor indices are a copy, otherwise they reference internal graph data.
:returns: The internal index
"""
raise NotImplementedError()
@abstractmethod
def get_feature_vector(self, internal_index: int, copy: bool = False) -> np.ndarray:
"""
Get the feature vector of the given internal index.
:param internal_index: The internal index to get the feature vector of.
:param 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
"""
raise NotImplementedError()
@abstractmethod
def has_vertex(self, external_label: int) -> bool:
"""
:returns: whether the given external label is present in the graph.
"""
raise NotImplementedError()
@abstractmethod
def has_edge(self, internal_index: int, neighbor_index: int) -> bool:
"""
:returns: whether the vertex at internal_index has an edge to the vertex at neighbor_index.
"""
raise NotImplementedError()
def get_entry_vertex_indices(self) -> List[int]:
"""
Creates a list of internal indices that can be used as starting point for an anns search.
"""
return [self.get_internal_index(0)]
@abstractmethod
def has_path(self, 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.
"""
raise NotImplementedError()
@abstractmethod
def search(
self, query: np.ndarray, eps: float, k: int, max_distance_computation_count: int = 0,
entry_vertex_indices: Optional[List[int]] = None, threads: int = 1, thread_batch_size: int = 0
) -> Tuple[np.ndarray, np.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.
:param query: A feature vector for which similar feature vectors should searched.
:param eps: TODO
:param k: The number of results that will be returned
:param max_distance_computation_count: Limit the number of distance calculations. If set to 0 this is ignored.
:param entry_vertex_indices: Start point for exploratory search. If None, a reasonable default is used.
:param 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.
:param thread_batch_size: If threads != 1, the number of queries to search in the same thread.
:returns: TODO
"""
raise NotImplementedError()
@abstractmethod
def explore(self, entry_vertex_index: int, k: int, max_distance_computation_count: int) -> ResultSet:
"""
A exploration for similar element, limited by max_distance_computation_count
:param entry_vertex_index: The start point for which similar feature vectors should be searched
:param k: The number of similar feature vectors to return
:param max_distance_computation_count: TODO
"""
raise NotImplementedError()
@abstractmethod
def to_cpp(self):
raise NotImplementedError()
class ReadOnlyGraph(SearchGraph):
def __init__(self, graph_cpp: deglib_cpp.ReadOnlyGraph):
if not isinstance(graph_cpp, deglib_cpp.ReadOnlyGraph):
raise TypeError("expected ReadOnlyGraph but got {}".format(type(graph_cpp)))
self.graph_cpp = graph_cpp
@classmethod
def from_graph(
cls, input_graph: SearchGraph, max_vertex_count: int = -1, feature_space: FloatSpace | None = None,
edges_per_vertex: int = -1
) -> Self:
"""
Create a read only graph from the given graph by only keeping information that is useful for searching.
:param input_graph: The graph to build from
:param max_vertex_count: If given the new size of the returned graph, otherwise will be taken from input graph
:param feature_space: If given the feature space for the graph, otherwise the same as the feature space of the
input graph
:param edges_per_vertex: The number of edges for the new graph. Should not be smaller than the edges of the
input graph
"""
if max_vertex_count == -1:
max_vertex_count = input_graph.size()
if feature_space is None:
feature_space = input_graph.get_feature_space()
if edges_per_vertex == -1:
edges_per_vertex = input_graph.get_edges_per_vertex()
return ReadOnlyGraph(deglib_cpp.read_only_graph_from_graph(
input_graph.to_cpp(), max_vertex_count, feature_space.to_cpp(), edges_per_vertex
))
def size(self) -> int:
"""
:return: the number of vertices in the graph
"""
return self.graph_cpp.size()
def get_feature_space(self) -> FloatSpace:
"""
:return: the feature space
"""
# first two parameters get ignored
return FloatSpace(0, Metric.L2, float_space_cpp=self.graph_cpp.get_feature_space())
def get_feature_vector(self, index: int, copy: bool = False) -> np.ndarray:
"""
Get the feature vector of the given internal index.
:param index: The internal index to get the feature vector of
:param 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
"""
if index < 0 or index >= self.size():
raise IndexError("Index {} out of range for size {}".format(index, self.size()))
memory_view = self.graph_cpp.get_feature_vector(index)
feature_vector = np.asarray(memory_view)
if copy:
feature_vector = np.copy(feature_vector)
return feature_vector
def get_internal_index(self, external_label: int) -> int:
"""
Translates internal index to external label
:param external_label: The external label to translate
:returns: The internal index
"""
return self.graph_cpp.get_internal_index(external_label)
def search(
self, query: np.ndarray, eps: float, k: int, max_distance_computation_count: int = 0,
entry_vertex_indices: Optional[List[int]] = None, threads: int = 1, thread_batch_size: int = 0
) -> Tuple[np.ndarray, np.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.
:param query: A feature vector for which similar feature vectors should searched.
:param eps: TODO
:param k: The number of results that will be returned
:param max_distance_computation_count: Limit the number of distance calculations. If set to 0 this is ignored.
:param entry_vertex_indices: Start point for exploratory search. If None, a reasonable default is used.
:param 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.
:param thread_batch_size: If threads != 1, the number of queries to search in the same thread. If set <= 0, will
be set to a reasonable value.
:returns: TODO
"""
# handle query shapes
if len(query.shape) == 1:
query = query.reshape(1, -1)
if len(query.shape) != 2:
raise InvalidShapeException('invalid query shape: {}'.format(query.shape))
query = assure_array(query, 'query', np.float32)
threads = get_num_useful_threads(threads, query.shape[0])
if entry_vertex_indices is None:
entry_vertex_indices = self.get_entry_vertex_indices()
if thread_batch_size <= 0:
thread_batch_size = max(query.shape[0] // (threads * 4), 1)
return self.graph_cpp.search(
entry_vertex_indices, query, eps, k, max_distance_computation_count, threads, thread_batch_size
)
def has_path(self, 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.
:param entry_vertex_indices: List of start vertices
:param to_vertex: The vertex to find a path to
:param eps: TODO
:param k: TODO
"""
return [ObjectDistance(od) for od in self.graph_cpp.has_path(entry_vertex_indices, to_vertex, eps, k)]
def get_entry_vertex_indices(self) -> List[int]:
"""
Creates a list of internal indices that can be used as starting point for an anns search.
"""
return self.graph_cpp.get_entry_vertex_indices()
def get_external_label(self, internal_index: int) -> int:
"""
Translates external labels to internal index
:param internal_index: The internal index to translate
:returns: The external label
"""
return self.graph_cpp.get_external_label(internal_index)
def explore(self, entry_vertex_index: int, k: int, max_distance_computation_count: int) -> ResultSet:
"""
An exploration for similar element, limited by max_distance_computation_count
:param entry_vertex_index: The start point for which similar feature vectors should be searched
:param k: The number of similar feature vectors to return
:param max_distance_computation_count: Limit the number of distance calculations. If set to 0 this is ignored.
"""
return ResultSet(self.graph_cpp.explore(entry_vertex_index, k, max_distance_computation_count))
def get_edges_per_vertex(self) -> int:
"""
:return: the number of edges of each vertex
"""
return self.graph_cpp.get_edges_per_vertex()
def get_neighbor_indices(self, internal_index: int, copy: bool = False) -> np.ndarray:
"""
Get the neighbor indices (internal index) of the given vertex.
:param internal_index: The internal index to get the neighbors of
:param copy: If True the returned neighbor indices are a copy, otherwise they reference internal graph data.
"""
if internal_index < 0 or internal_index >= self.size():
raise IndexError("Index {} out of range for size {}".format(internal_index, self.size()))
memory_view = self.graph_cpp.get_neighbor_indices(internal_index)
neighbors = np.asarray(memory_view)
if copy:
neighbors = np.copy(neighbors)
return neighbors
def has_vertex(self, external_label: int) -> bool:
"""
:returns: whether the given external label is present in the graph.
"""
return self.graph_cpp.has_vertex(external_label)
def has_edge(self, internal_index: int, neighbor_index: int) -> bool:
"""
:returns: whether the vertex at internal_index has an edge to the vertex at neighbor_index.
"""
return self.graph_cpp.has_edge(internal_index, neighbor_index)
def to_cpp(self) -> deglib_cpp.ReadOnlyGraph:
return self.graph_cpp
def __repr__(self) -> str:
return (f'ReadOnlyGraph(size={self.size()} edges_per_vertex={self.get_edges_per_vertex()} '
f'dim={self.get_feature_space().dim()})')
def load_readonly_graph(path: pathlib.Path | str) -> ReadOnlyGraph:
"""
Read a saved ReadOnlyGraph from given file. The file can be created by calling SizeBoundedGraph.save_graph().
:param path: The path where to look for the file
:raises FileNotFoundError: If the given file does not exist
"""
if not os.path.isfile(path):
raise FileNotFoundError('File "{}" could not be found'.format(path))
return ReadOnlyGraph(deglib_cpp.load_readonly_graph(str(path)))
class MutableGraph(SearchGraph, ABC):
@abstractmethod
def add_vertex(self, external_label: int, feature_vector: np.ndarray) -> int:
"""
Add a new vertex. The neighbor indices will be prefilled with a self-loop, the weights will be 0.
:param external_label: The label for the new vertex
:param feature_vector: The feature vector to add. This numpy array should be c-contiguous, otherwise it has to
be reallocated.
:return: the internal index of the new vertex
"""
raise NotImplementedError()
@abstractmethod
def remove_vertex(self, external_label: int):
"""
Remove an existing vertex.
:param external_label: The external label of the vertex that should be removed.
"""
raise NotImplementedError()
@abstractmethod
def change_edge(self, 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.
:param internal_index: vertex index which neighbors should be changed
:param from_neighbor_index: neighbor index to remove
:param to_neighbor_index: neighbor index to add
:param to_neighbor_weight: weight of the neighbor to add
:return: True if the from_neighbor_index was found and changed
"""
raise NotImplementedError()
@abstractmethod
def change_edges(self, internal_index: int, neighbor_indices: np.ndarray, neighbor_weights: np.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.
:param internal_index: The index of the vertex for which edges should change
:param neighbor_indices: These neighbors will be set as the new neighbors of the specified vertex
:param neighbor_weights: These weights will be set as the new weights for the neighbors.
"""
raise NotImplementedError()
@abstractmethod
def get_neighbor_weights(self, internal_index: int, copy: bool = False) -> np.ndarray:
"""
Get weights for each neighbor of the vertex defined by the given index.
:param internal_index: The index that specifies the vertex
:param copy: If True the returned neighbor weights are copied, otherwise they reference internal graph data.
:returns: The weights of the neighbors
"""
raise NotImplementedError()
@abstractmethod
def get_edge_weight(self, 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.
:param from_neighbor_index: Internal index of the start vertex
:param to_neighbor_index: Internal index of the target vertex
:returns: If present the weight between start and target vertex, -1.0 otherwise
"""
raise NotImplementedError()
@abstractmethod
def save_graph(self, path: str | pathlib.Path) -> bool:
"""
Save graph to specified file. Creates necessary directories.
:param path: The path where to save the file.
"""
raise NotImplementedError()
@abstractmethod
def to_cpp(self):
raise NotImplementedError()
def remove_non_mrng_edges(self):
"""
Remove all edges which are not MRNG conform.
"""
deglib_cpp.remove_non_mrng_edges(self.to_cpp())
class SizeBoundedGraph(MutableGraph):
def __init__(
self, max_vertex_count: int, edges_per_vertex: int, feature_space: FloatSpace,
graph_cpp: Optional[deglib_cpp.SizeBoundedGraph] = None
):
"""
Create a new SizeBoundedGraph. This can be used to fit a graph to a dataset and save it for later use.
:param max_vertex_count: The maximum number of vertices, that can be added to this graph
:param edges_per_vertex: The number of neighbors for each vertex
:param feature_space: The space definition for all feature vectors
:param graph_cpp: For internal use, do not use except you know what you are doing
"""
if graph_cpp is None:
graph_cpp = deglib_cpp.SizeBoundedGraph(max_vertex_count, edges_per_vertex, feature_space.to_cpp())
self.graph_cpp = graph_cpp
self.feature_space = feature_space
@staticmethod
def create_empty(capacity: int, dims: int, edges_per_vertex: int = 32, metric: Metric = Metric.L2):
"""
Create an empty SizeBoundedGraph.
:param capacity: The maximal number of vertices of this graph.
:param dims: The number of dimensions of each feature vector
:param edges_per_vertex: Number of neighbors for each vertex. Defaults to 32.
:param metric: The metric to measure distances between features. Defaults to L2-Metric.
"""
return SizeBoundedGraph(capacity, edges_per_vertex, FloatSpace(dims, metric))
def size(self) -> int:
"""
:return: the number of vertices in the graph
"""
return self.graph_cpp.size()
def get_feature_space(self) -> FloatSpace:
"""
:return: the feature space
"""
# first two parameters get ignored
return FloatSpace(0, Metric.L2, float_space_cpp=self.graph_cpp.get_feature_space())
def get_feature_vector(self, index: int, copy: bool = False) -> np.ndarray:
"""
Get the feature vector of the given internal index.
:param index: The internal index to get the feature vector of
:param 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
"""
memory_view = self.graph_cpp.get_feature_vector(index)
feature_vector = np.asarray(memory_view)
if copy:
feature_vector = np.copy(feature_vector)
return feature_vector
def get_internal_index(self, external_label: int) -> int:
"""
Translates internal index to external label
:param external_label: The external label to translate
:returns: The internal index
"""
return self.graph_cpp.get_internal_index(external_label)
def has_path(self, 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.
:param entry_vertex_indices: List of start vertices
:param to_vertex: The vertex to find a path to
:param eps: TODO
:param k: TODO
"""
return [ObjectDistance(od) for od in self.graph_cpp.has_path(entry_vertex_indices, to_vertex, eps, k)]
def get_entry_vertex_indices(self) -> List[int]:
"""
Creates a list of internal indices that can be used as starting point for an anns search.
"""
return self.graph_cpp.get_entry_vertex_indices()
def get_external_label(self, internal_index: int) -> int:
"""
Translates external labels to internal index
:param internal_index: The internal index to translate
:returns: The external label
"""
return self.graph_cpp.get_external_label(internal_index)
def save_graph(self, path: pathlib.Path | str):
"""
Save graph to specified file. Creates necessary directories.
:param path: The path where to save the file.
"""
self.graph_cpp.save_graph(str(path))
def get_edges_per_vertex(self) -> int:
"""
:return: the number of edges of each vertex
"""
return self.graph_cpp.get_edges_per_vertex()
def add_vertex(self, external_label: int, feature_vector: np.ndarray) -> int:
"""
Add a new vertex. The neighbor indices will be prefilled with a self-loop, the weights will be 0.
:param external_label: The label for the new vertex
:param feature_vector: The feature vector to add. This numpy array should be c-contiguous, otherwise it has to
be reallocated.
:return: the internal index of the new vertex
"""
feature_vector = assure_array(feature_vector, 'feature_vector', np.float32)
return self.graph_cpp.add_vertex(external_label, feature_vector)
def remove_vertex(self, external_label: int):
"""
Remove an existing vertex.
:param external_label: The external label of the vertex that should be removed.
"""
self.graph_cpp.remove_vertex(external_label)
def change_edge(
self, 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.
:param internal_index: vertex index which neighbors should be changed
:param from_neighbor_index: neighbor index to remove
:param to_neighbor_index: neighbor index to add
:param to_neighbor_weight: weight of the neighbor to add
:return: True if the from_neighbor_index was found and changed
"""
return self.graph_cpp.change_edge(internal_index, from_neighbor_index, to_neighbor_index, to_neighbor_weight)
def change_edges(self, internal_index: int, neighbor_indices: np.ndarray, neighbor_weights: np.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.
:param internal_index: The index of the vertex for which edges should change
:param neighbor_indices: These neighbors will be set as the new neighbors of the specified vertex
:param neighbor_weights: These weights will be set as the new weights for the neighbors.
"""
neighbor_indices = assure_array(neighbor_indices, 'neighbor_indices', np.uint32)
neighbor_weights = assure_array(neighbor_weights, 'neighbor_weights', np.float32)
return self.graph_cpp.change_edges(internal_index, neighbor_indices, neighbor_weights)
def get_neighbor_weights(self, internal_index: int, copy: bool = False) -> np.ndarray:
"""
Get weights for each neighbor of the vertex defined by the given index.
:param internal_index: The index that specifies the vertex
:param copy: If True the returned neighbor weights are copied, otherwise they reference internal graph data.
:returns: The weights of the neighbors
"""
if internal_index < 0 or internal_index >= self.size():
raise IndexError("Index {} out of range for size {}".format(internal_index, self.size()))
memory_view = self.graph_cpp.get_neighbor_weights(internal_index)
weights = np.asarray(memory_view)
if copy:
weights = np.copy(weights)
return weights
def get_edge_weight(self, 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.
:param from_neighbor_index: Internal index of the start vertex
:param to_neighbor_index: Internal index of the target vertex
:returns: If present the weight between start and target vertex, -1.0 otherwise
"""
return self.graph_cpp.get_edge_weight(from_neighbor_index, to_neighbor_index)
def get_neighbor_indices(self, internal_index: int, copy: bool = False) -> np.ndarray:
"""
Get the indices (internal index) of the given vertex.
:param internal_index: The internal index to get the neighbors of
:param copy: If True the returned neighbor indices are a copy, otherwise they reference internal graph data.
:returns: The internal index
"""
if internal_index < 0 or internal_index >= self.size():
raise IndexError("Index {} out of range for size {}".format(internal_index, self.size()))
memory_view = self.graph_cpp.get_neighbor_indices(internal_index)
indices = np.asarray(memory_view)
if copy:
indices = np.copy(indices)
return indices
def has_vertex(self, external_label: int) -> bool:
"""
:returns: whether the given external label is present in the graph.
"""
return self.graph_cpp.has_vertex(external_label)
def has_edge(self, internal_index: int, neighbor_index: int) -> bool:
"""
:returns: whether the vertex at internal_index has an edge to the vertex at neighbor_index.
"""
return self.graph_cpp.has_edge(internal_index, neighbor_index)
def search(
self, query: np.ndarray, eps: float, k: int, max_distance_computation_count: int = 0,
entry_vertex_indices: Optional[List[int]] = None, threads: int = 1, thread_batch_size: int = 0
) -> Tuple[np.ndarray, np.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.
:param query: A feature vector for which similar feature vectors should searched.
:param eps: TODO
:param k: The number of results that will be returned
:param max_distance_computation_count: Limit the number of distance calculations. If set to 0 this is ignored.
:param entry_vertex_indices: Start point for exploratory search. If None, a reasonable default is used.
:param 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.
:param thread_batch_size: If threads != 1, the number of queries to search in the same thread.
:returns: TODO
"""
# handle query shapes
if len(query.shape) == 1:
query = query.reshape(1, -1)
if len(query.shape) != 2:
raise InvalidShapeException('invalid query shape: {}'.format(query.shape))
query = assure_array(query, 'query', np.float32)
if entry_vertex_indices is None:
entry_vertex_indices = self.get_entry_vertex_indices()
threads = get_num_useful_threads(threads, query.shape[0])
if thread_batch_size <= 0:
thread_batch_size = max(query.shape[0] // (threads * 4), 1)
return self.graph_cpp.search(
entry_vertex_indices, query, eps, k, max_distance_computation_count, threads, thread_batch_size
)
def explore(self, entry_vertex_index: int, k: int, max_distance_computation_count: int) -> ResultSet:
"""
An exploration for similar element, limited by max_distance_computation_count
:param entry_vertex_index: The start point for which similar feature vectors should be searched
:param k: The number of similar feature vectors to return
:param max_distance_computation_count: Limit the number of distance calculations. If set to 0 this is ignored.
"""
return ResultSet(self.graph_cpp.explore(entry_vertex_index, k, max_distance_computation_count))
def to_cpp(self) -> deglib_cpp.SizeBoundedGraph:
return self.graph_cpp
def __repr__(self) -> str:
return (f'SizeBoundedGraph(size={self.size()} edges_per_vertex={self.get_edges_per_vertex()} '
f'dim={self.get_feature_space().dim()})')
def get_num_useful_threads(requested: int, max_limit: int):
if requested == 0:
requested = multiprocessing.cpu_count()
return min(requested, max_limit) # dont use more threads than queries
__all__ = ['load_readonly_graph', 'ReadOnlyGraph', 'SizeBoundedGraph', 'MutableGraph', 'SearchGraph']