ruvector_mincut_node/
lib.rs

1//! Node.js bindings for RuVector MinCut
2//!
3//! Provides native Node.js API for dynamic minimum cut operations,
4//! including paper algorithms from arXiv:2512.13105.
5//!
6//! ## Features
7//!
8//! - **MinCut**: Basic dynamic minimum cut (insert/delete/query)
9//! - **ThreeLevelHierarchy**: 3-level decomposition (Expander→Precluster→Cluster)
10//! - **LocalKCut**: Deterministic local k-cut discovery with 4-color coding
11//! - **MinCutWrapper**: Full API with connectivity curve analysis
12
13use napi::bindgen_prelude::*;
14use napi_derive::napi;
15use ruvector_mincut::cluster::hierarchy::{HierarchyConfig, ThreeLevelHierarchy as RustHierarchy};
16use ruvector_mincut::localkcut::deterministic::DeterministicLocalKCut;
17use ruvector_mincut::{
18    DynamicGraph, DynamicMinCut, MinCutBuilder, MinCutWrapper as RustMinCutWrapper,
19};
20use std::sync::{Arc, Mutex};
21
22/// Edge representation for JavaScript
23#[napi(object)]
24pub struct JsEdge {
25    pub id: u32,
26    pub source: u32,
27    pub target: u32,
28    pub weight: f64,
29}
30
31/// Statistics about the algorithm
32#[napi(object)]
33pub struct JsStats {
34    pub insertions: u32,
35    pub deletions: u32,
36    pub queries: u32,
37    pub avg_update_time_us: f64,
38}
39
40/// Minimum cut result
41#[napi(object)]
42pub struct JsMinCutResult {
43    pub value: f64,
44    pub is_exact: bool,
45    pub approximation_ratio: f64,
46}
47
48/// Configuration for minimum cut
49#[napi(object)]
50pub struct JsMinCutConfig {
51    pub approximate: Option<bool>,
52    pub epsilon: Option<f64>,
53    pub max_exact_cut_size: Option<u32>,
54}
55
56/// Partition result
57#[napi(object)]
58pub struct JsPartition {
59    pub s: Vec<u32>,
60    pub t: Vec<u32>,
61}
62
63/// Node.js wrapper for DynamicMinCut
64#[napi]
65pub struct MinCut {
66    inner: Arc<Mutex<DynamicMinCut>>,
67}
68
69#[napi]
70impl MinCut {
71    /// Create a new empty minimum cut structure
72    #[napi(constructor)]
73    pub fn new(config: Option<JsMinCutConfig>) -> Result<Self> {
74        let mut builder = MinCutBuilder::new();
75
76        if let Some(cfg) = config {
77            if cfg.approximate.unwrap_or(false) {
78                builder = builder.approximate(cfg.epsilon.unwrap_or(0.1));
79            }
80            if let Some(max_size) = cfg.max_exact_cut_size {
81                builder = builder.max_cut_size(max_size as usize);
82            }
83        }
84
85        let mincut = builder
86            .build()
87            .map_err(|e| Error::from_reason(format!("Failed to create MinCut: {}", e)))?;
88
89        Ok(Self {
90            inner: Arc::new(Mutex::new(mincut)),
91        })
92    }
93
94    /// Create from edges array
95    #[napi(factory)]
96    pub fn from_edges(edges: Vec<(u32, u32, f64)>, config: Option<JsMinCutConfig>) -> Result<Self> {
97        let mut builder = MinCutBuilder::new();
98
99        if let Some(cfg) = config {
100            if cfg.approximate.unwrap_or(false) {
101                builder = builder.approximate(cfg.epsilon.unwrap_or(0.1));
102            }
103            if let Some(max_size) = cfg.max_exact_cut_size {
104                builder = builder.max_cut_size(max_size as usize);
105            }
106        }
107
108        // Convert edges to the expected format
109        let edge_tuples: Vec<(u64, u64, f64)> = edges
110            .into_iter()
111            .map(|(u, v, w)| (u as u64, v as u64, w))
112            .collect();
113
114        let mincut = builder.with_edges(edge_tuples).build().map_err(|e| {
115            Error::from_reason(format!("Failed to create MinCut from edges: {}", e))
116        })?;
117
118        Ok(Self {
119            inner: Arc::new(Mutex::new(mincut)),
120        })
121    }
122
123    /// Insert an edge (returns new min cut value)
124    #[napi]
125    pub fn insert_edge(&self, u: u32, v: u32, weight: f64) -> Result<f64> {
126        let mut mincut = self
127            .inner
128            .lock()
129            .map_err(|e| Error::from_reason(format!("Lock error: {}", e)))?;
130
131        mincut
132            .insert_edge(u as u64, v as u64, weight)
133            .map_err(|e| Error::from_reason(format!("Failed to insert edge: {}", e)))
134    }
135
136    /// Delete an edge (returns new min cut value)
137    #[napi]
138    pub fn delete_edge(&self, u: u32, v: u32) -> Result<f64> {
139        let mut mincut = self
140            .inner
141            .lock()
142            .map_err(|e| Error::from_reason(format!("Lock error: {}", e)))?;
143
144        mincut
145            .delete_edge(u as u64, v as u64)
146            .map_err(|e| Error::from_reason(format!("Failed to delete edge: {}", e)))
147    }
148
149    /// Get minimum cut value
150    #[napi(getter)]
151    pub fn min_cut_value(&self) -> f64 {
152        let mincut = self.inner.lock().unwrap();
153        mincut.min_cut_value()
154    }
155
156    /// Get detailed minimum cut result
157    #[napi]
158    pub fn min_cut(&self) -> JsMinCutResult {
159        let mincut = self.inner.lock().unwrap();
160        let result = mincut.min_cut();
161
162        JsMinCutResult {
163            value: result.value,
164            is_exact: result.is_exact,
165            approximation_ratio: result.approximation_ratio,
166        }
167    }
168
169    /// Get partition: returns { s: number[], t: number[] }
170    #[napi]
171    pub fn partition(&self) -> Result<JsPartition> {
172        let mincut = self
173            .inner
174            .lock()
175            .map_err(|e| Error::from_reason(format!("Lock error: {}", e)))?;
176
177        let (s, t) = mincut.partition();
178
179        Ok(JsPartition {
180            s: s.into_iter().map(|v| v as u32).collect(),
181            t: t.into_iter().map(|v| v as u32).collect(),
182        })
183    }
184
185    /// Get cut edges
186    #[napi]
187    pub fn cut_edges(&self) -> Vec<JsEdge> {
188        let mincut = self.inner.lock().unwrap();
189        let edges = mincut.cut_edges();
190
191        edges
192            .into_iter()
193            .map(|e| JsEdge {
194                id: e.id as u32,
195                source: e.source as u32,
196                target: e.target as u32,
197                weight: e.weight,
198            })
199            .collect()
200    }
201
202    /// Get number of vertices
203    #[napi(getter)]
204    pub fn num_vertices(&self) -> u32 {
205        let mincut = self.inner.lock().unwrap();
206        mincut.num_vertices() as u32
207    }
208
209    /// Get number of edges
210    #[napi(getter)]
211    pub fn num_edges(&self) -> u32 {
212        let mincut = self.inner.lock().unwrap();
213        mincut.num_edges() as u32
214    }
215
216    /// Check if graph is connected
217    #[napi]
218    pub fn is_connected(&self) -> bool {
219        let mincut = self.inner.lock().unwrap();
220        mincut.is_connected()
221    }
222
223    /// Get algorithm statistics
224    #[napi(getter)]
225    pub fn stats(&self) -> JsStats {
226        let mincut = self.inner.lock().unwrap();
227        let stats = mincut.stats();
228
229        JsStats {
230            insertions: stats.insertions as u32,
231            deletions: stats.deletions as u32,
232            queries: stats.queries as u32,
233            avg_update_time_us: stats.avg_update_time_us,
234        }
235    }
236
237    /// Reset statistics
238    #[napi]
239    pub fn reset_stats(&self) {
240        let mut mincut = self.inner.lock().unwrap();
241        mincut.reset_stats();
242    }
243}
244
245// ============================================================================
246// ThreeLevelHierarchy - Paper Section 3: Expander → Precluster → Cluster
247// ============================================================================
248
249/// Hierarchy statistics
250#[napi(object)]
251pub struct JsHierarchyStats {
252    pub num_expanders: u32,
253    pub num_preclusters: u32,
254    pub num_clusters: u32,
255    pub num_vertices: u32,
256    pub num_edges: u32,
257    pub global_min_cut: f64,
258    pub avg_expander_size: f64,
259}
260
261/// Three-level hierarchy decomposition from the paper
262#[napi]
263pub struct ThreeLevelHierarchy {
264    inner: RustHierarchy,
265}
266
267#[napi]
268impl ThreeLevelHierarchy {
269    /// Create with default configuration
270    #[napi(constructor)]
271    pub fn new() -> Self {
272        ThreeLevelHierarchy {
273            inner: RustHierarchy::with_defaults(),
274        }
275    }
276
277    /// Create with custom expansion parameter φ
278    #[napi(factory)]
279    pub fn with_phi(phi: f64) -> Self {
280        ThreeLevelHierarchy {
281            inner: RustHierarchy::new(HierarchyConfig {
282                phi,
283                ..Default::default()
284            }),
285        }
286    }
287
288    /// Insert an edge
289    #[napi]
290    pub fn insert_edge(&mut self, u: u32, v: u32, weight: f64) {
291        self.inner.insert_edge(u as u64, v as u64, weight);
292    }
293
294    /// Delete an edge
295    #[napi]
296    pub fn delete_edge(&mut self, u: u32, v: u32) {
297        self.inner.delete_edge(u as u64, v as u64);
298    }
299
300    /// Build the 3-level decomposition
301    #[napi]
302    pub fn build(&mut self) {
303        self.inner.build();
304    }
305
306    /// Get hierarchy statistics
307    #[napi(getter)]
308    pub fn stats(&self) -> JsHierarchyStats {
309        let s = self.inner.stats();
310        JsHierarchyStats {
311            num_expanders: s.num_expanders as u32,
312            num_preclusters: s.num_preclusters as u32,
313            num_clusters: s.num_clusters as u32,
314            num_vertices: s.num_vertices as u32,
315            num_edges: s.num_edges as u32,
316            global_min_cut: s.global_min_cut,
317            avg_expander_size: s.avg_expander_size,
318        }
319    }
320
321    /// Get global minimum cut estimate
322    #[napi(getter)]
323    pub fn global_min_cut(&self) -> f64 {
324        self.inner.global_min_cut
325    }
326
327    /// Get all vertices
328    #[napi]
329    pub fn vertices(&self) -> Vec<u32> {
330        self.inner
331            .vertices()
332            .into_iter()
333            .map(|v| v as u32)
334            .collect()
335    }
336}
337
338// ============================================================================
339// LocalKCut - Paper Theorem 4.1: Color-coded DFS
340// ============================================================================
341
342/// Local cut result
343#[napi(object)]
344pub struct JsLocalCut {
345    pub cut_value: f64,
346    pub vertices: Vec<u32>,
347}
348
349/// Deterministic local k-cut algorithm
350#[napi]
351pub struct LocalKCut {
352    inner: DeterministicLocalKCut,
353    num_vertices: usize,
354    num_edges: usize,
355}
356
357#[napi]
358impl LocalKCut {
359    /// Create new LocalKCut structure
360    ///
361    /// # Arguments
362    /// * `lambda_max` - Maximum cut value
363    /// * `volume_bound` - Maximum volume (nu parameter)
364    /// * `beta` - Cut depth parameter
365    #[napi(constructor)]
366    pub fn new(lambda_max: i64, volume_bound: u32, beta: u32) -> Self {
367        LocalKCut {
368            inner: DeterministicLocalKCut::new(
369                lambda_max as u64,
370                volume_bound as usize,
371                beta as usize,
372            ),
373            num_vertices: 0,
374            num_edges: 0,
375        }
376    }
377
378    /// Insert an edge
379    #[napi]
380    pub fn insert_edge(&mut self, u: u32, v: u32, weight: f64) {
381        self.inner.insert_edge(u as u64, v as u64, weight);
382        self.num_edges += 1;
383        self.num_vertices = self.num_vertices.max((u.max(v) + 1) as usize);
384    }
385
386    /// Delete an edge
387    #[napi]
388    pub fn delete_edge(&mut self, u: u32, v: u32) {
389        self.inner.delete_edge(u as u64, v as u64);
390        self.num_edges = self.num_edges.saturating_sub(1);
391    }
392
393    /// Query local cuts from a source
394    #[napi]
395    pub fn query(&self, source: u32) -> Vec<JsLocalCut> {
396        self.inner
397            .query(source as u64)
398            .into_iter()
399            .map(|c| JsLocalCut {
400                cut_value: c.cut_value,
401                vertices: c.vertices.into_iter().map(|v| v as u32).collect(),
402            })
403            .collect()
404    }
405
406    /// Get number of vertices
407    #[napi(getter)]
408    pub fn num_vertices(&self) -> u32 {
409        self.num_vertices as u32
410    }
411
412    /// Get number of edges
413    #[napi(getter)]
414    pub fn num_edges(&self) -> u32 {
415        self.num_edges as u32
416    }
417}
418
419// ============================================================================
420// MinCutWrapper - Full API with Connectivity Curve Analysis
421// ============================================================================
422
423/// Connectivity curve point
424#[napi(object)]
425pub struct JsCurvePoint {
426    pub k: u32,
427    pub min_cut: i64,
428}
429
430/// Elbow detection result
431#[napi(object)]
432pub struct JsElbowResult {
433    pub k: u32,
434    pub drop: i64,
435}
436
437/// Full MinCutWrapper with paper algorithms
438#[napi]
439pub struct MinCutWrapperNode {
440    inner: RustMinCutWrapper,
441}
442
443#[napi]
444impl MinCutWrapperNode {
445    /// Create new wrapper
446    #[napi(constructor)]
447    pub fn new() -> Self {
448        let graph = Arc::new(DynamicGraph::new());
449        MinCutWrapperNode {
450            inner: RustMinCutWrapper::new(graph),
451        }
452    }
453
454    /// Insert an edge
455    #[napi]
456    pub fn insert_edge(&mut self, u: u32, v: u32) {
457        let time = self.inner.current_time() + 1;
458        self.inner.insert_edge(time, u as u64, v as u64);
459    }
460
461    /// Delete an edge
462    #[napi]
463    pub fn delete_edge(&mut self, u: u32, v: u32) {
464        let time = self.inner.current_time() + 1;
465        self.inner.delete_edge(time, u as u64, v as u64);
466    }
467
468    /// Query minimum cut
469    #[napi]
470    pub fn query(&mut self) -> i64 {
471        self.inner.min_cut_value() as i64
472    }
473
474    /// Get number of instances
475    #[napi(getter)]
476    pub fn num_instances(&self) -> u32 {
477        self.inner.num_instances() as u32
478    }
479
480    /// Get current time
481    #[napi(getter)]
482    pub fn current_time(&self) -> i64 {
483        self.inner.current_time() as i64
484    }
485
486    /// Get local cuts from source
487    #[napi]
488    pub fn local_cuts(&self, source: u32, lambda_max: i64) -> Vec<JsLocalCut> {
489        self.inner
490            .local_cuts(source as u64, lambda_max as u64)
491            .into_iter()
492            .map(|(value, verts)| JsLocalCut {
493                cut_value: value,
494                vertices: verts.into_iter().map(|v| v as u32).collect(),
495            })
496            .collect()
497    }
498
499    /// Compute connectivity curve
500    #[napi]
501    pub fn connectivity_curve(
502        &self,
503        ranked_edges: Vec<(u32, u32, f64)>,
504        k_max: u32,
505    ) -> Vec<JsCurvePoint> {
506        let ranked: Vec<(u64, u64, f64)> = ranked_edges
507            .into_iter()
508            .map(|(u, v, s)| (u as u64, v as u64, s))
509            .collect();
510
511        self.inner
512            .connectivity_curve(&ranked, k_max as usize)
513            .into_iter()
514            .map(|(k, min_cut)| JsCurvePoint {
515                k: k as u32,
516                min_cut: min_cut as i64,
517            })
518            .collect()
519    }
520
521    /// Find elbow in curve
522    #[napi]
523    pub fn find_elbow(curve: Vec<JsCurvePoint>) -> Option<JsElbowResult> {
524        let curve_data: Vec<(usize, u64)> = curve
525            .into_iter()
526            .map(|p| (p.k as usize, p.min_cut as u64))
527            .collect();
528
529        RustMinCutWrapper::find_elbow(&curve_data).map(|(k, drop)| JsElbowResult {
530            k: k as u32,
531            drop: drop as i64,
532        })
533    }
534
535    /// Compute detector quality
536    #[napi]
537    pub fn detector_quality(&self, ranked_edges: Vec<(u32, u32, f64)>, true_cut_size: u32) -> f64 {
538        let ranked: Vec<(u64, u64, f64)> = ranked_edges
539            .into_iter()
540            .map(|(u, v, s)| (u as u64, v as u64, s))
541            .collect();
542
543        self.inner.detector_quality(&ranked, true_cut_size as usize)
544    }
545}
ruvector_mincut_node/lib.rs

ruvector_mincut_node/
lib.rs
