| 368 | |
| 369 | #[test] |
| 370 | fn build_graph_has_connectivity() { |
| 371 | let dim = 8; |
| 372 | let n = 100; |
| 373 | let codec = L2Codec; |
| 374 | |
| 375 | let vecs = rand_vecs(n, dim, 1234); |
| 376 | let ids: Vec<u64> = (0..n as u64).collect(); |
| 377 | let quantized: Vec<L2Q> = vecs.iter().map(|v| codec.encode(v)).collect(); |
| 378 | |
| 379 | let graph = build_vamana(&vecs, &ids, &codec, &quantized, 8, 1.2, 20); |
| 380 | |
| 381 | assert_eq!(graph.len(), n); |
| 382 | |
| 383 | // Every node should have at least one neighbor (the graph is connected |
| 384 | // for n=100 with r=8). |
| 385 | let isolated: usize = (0..n).filter(|&i| graph.neighbors(i).is_empty()).count(); |
| 386 | assert!( |
| 387 | isolated < n / 2, |
| 388 | "more than half the nodes are isolated; graph has poor connectivity" |
| 389 | ); |
| 390 | |
| 391 | // Entry point must be a valid index. |
| 392 | assert!(graph.entry < n); |
| 393 | } |
| 394 | |
| 395 | #[test] |
| 396 | fn build_respects_degree_bound() { |