msokolov commented on code in PR #13566:
URL: https://github.com/apache/lucene/pull/13566#discussion_r1676192442
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswUtil.java:
##########
@@ -30,46 +30,83 @@
import org.apache.lucene.index.IndexReader;
import org.apache.lucene.index.LeafReaderContext;
import org.apache.lucene.util.FixedBitSet;
-import org.apache.lucene.util.hnsw.HnswGraph;
/** Utilities for use in tests involving HNSW graphs */
-public class HnswTestUtil {
+public class HnswUtil {
/**
* Returns true iff level 0 of the graph is fully connected - that is every
node is reachable from
* any entry point.
*/
public static boolean isFullyConnected(HnswGraph knnValues) throws
IOException {
- return componentSizes(knnValues).size() < 2;
+ for (int level = 0; level < knnValues.numLevels(); level++) {
+ if (components(knnValues, level).size() > 1) {
+ return false;
+ }
+ }
+ return true;
}
/**
* Returns the sizes of the distinct graph components on level 0. If the
graph is fully-connected
* there will only be a single component. If the graph is empty, the
returned list will be empty.
*/
public static List<Integer> componentSizes(HnswGraph hnsw) throws
IOException {
- List<Integer> sizes = new ArrayList<>();
+ return componentSizes(hnsw, 0);
+ }
+
+ /**
+ * Returns the sizes of the distinct graph components on the given level. If
the graph is
+ * fully-connected there will only be a single component. If the graph is
empty, the returned list
+ * will be empty.
+ */
+ public static List<Integer> componentSizes(HnswGraph hnsw, int level) throws
IOException {
+ return components(hnsw, level).stream().map(Component::size).toList();
+ }
+
+ // Finds all connected components of the graph
+ static List<Component> components(HnswGraph hnsw, int level) throws
IOException {
Review Comment:
OK, I have an idea how we can maybe compute strongly-connected efficiently
b/c our graphs are "mostly" undirected -- I think we can check back-links while
walking the graph? I'll noodle on it and see if I can come up with a stronger
test
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For additional commands, e-mail: issues-h...@lucene.apache.org
