vf3lib_rs/lib.rs
1//! Rust bindings to VF3/VF3L/VF3P subgraph isomorphism algorithms via CXX.
2//!
3//! This crate provides efficient subgraph isomorphism detection using the VF3 family of algorithms.
4//! The underlying implementation is a C++11 library from MIVIA Lab.
5//!
6//! # Examples
7//!
8//! Node-induced subgraph isomorphism:
9//! ```no_run
10//! use vf3lib_rs::{run_vf3, RunOptions};
11//! let result = run_vf3("pattern.grf", "target.grf", RunOptions::default())?;
12//! # Ok::<(), vf3lib_rs::VF3Error>(())
13//! ```
14//!
15//! Edge-induced (monomorphism):
16//! ```no_run
17//! use vf3lib_rs::{run_vf3, RunOptions};
18//! let opts = RunOptions { edge_induced: true, ..Default::default() };
19//! let result = run_vf3("pattern.grf", "target.grf", opts)?;
20//! # Ok::<(), vf3lib_rs::VF3Error>(())
21//! ```
22
23use thiserror::Error;
24
25/// Errors that can occur during VF3 algorithm execution.
26#[derive(Error, Debug)]
27pub enum VF3Error {
28 /// The VF3 algorithm execution failed with a non-zero status code.
29 #[error("VF3 execution failed with status code {code}")]
30 ExecutionFailed {
31 /// The status code returned by the C++ implementation.
32 code: i32,
33 },
34
35 /// An error occurred in the FFI layer.
36 #[error("FFI error: {message}")]
37 FfiError {
38 /// Description of the FFI error.
39 message: String,
40 },
41
42 /// The specified graph format is not supported.
43 #[error("Unsupported graph format: {format}")]
44 UnsupportedFormat {
45 /// The format string that was provided.
46 format: String,
47 },
48}
49
50// Skip C++ compilation on docs.rs to avoid build failures.
51#[cfg(not(docsrs))]
52#[cxx::bridge(namespace = "vf3ffi")]
53#[allow(clippy::too_many_arguments)]
54mod vf3ffi {
55 /// Execution result from C++ VF3 algorithms.
56 #[derive(Debug, Clone)]
57 pub struct VF3Result {
58 /// Status code: 0 on success, non-zero on error.
59 pub status: i32,
60 /// Number of isomorphic mappings found.
61 pub solutions: u64,
62 /// Time to first solution in seconds.
63 pub time_first: f64,
64 /// Average total execution time in seconds.
65 pub time_all: f64,
66 }
67
68 unsafe extern "C++" {
69 include!("vf3_bridge.hpp");
70
71 /// VF3 algorithm with all heuristics (best for medium/large dense graphs).
72 fn run_vf3(
73 pattern: &str,
74 target: &str,
75 format: &str,
76 undirected: bool,
77 store_solutions: bool,
78 first_only: bool,
79 verbose: bool,
80 repetition_time_limit: f32,
81 edge_induced: bool,
82 ) -> VF3Result;
83
84 /// VF3L lightweight variant without look-ahead (best for small/sparse graphs).
85 fn run_vf3l(
86 pattern: &str,
87 target: &str,
88 format: &str,
89 undirected: bool,
90 store_solutions: bool,
91 first_only: bool,
92 verbose: bool,
93 repetition_time_limit: f32,
94 edge_induced: bool,
95 ) -> VF3Result;
96
97 /// VF3P parallel variant for multi-threaded execution.
98 fn run_vf3p(
99 pattern: &str,
100 target: &str,
101 format: &str,
102 undirected: bool,
103 store_solutions: bool,
104 verbose: bool,
105 repetition_time_limit: f32,
106 edge_induced: bool,
107 algo: i8,
108 cpu: i16,
109 num_threads: i16,
110 lock_free: bool,
111 ssr_high_limit: i16,
112 ssr_local_stack_limit: i16,
113 ) -> VF3Result;
114 }
115}
116
117#[cfg(docsrs)]
118mod vf3ffi {
119 #[derive(Debug, Clone)]
120 pub struct VF3Result {
121 pub status: i32,
122 pub solutions: u64,
123 pub time_first: f64,
124 pub time_all: f64,
125 }
126}
127
128/// Graph file format for loading.
129#[derive(Debug, Clone, Copy, PartialEq, Eq)]
130pub enum GraphFormat {
131 /// VF text/binary format used by MIVIA datasets (.grf files).
132 VFLegacy,
133 /// Simple edge list format (one edge per line as "u v").
134 EdgeList,
135}
136
137impl GraphFormat {
138 fn as_str(self) -> &'static str {
139 match self {
140 GraphFormat::VFLegacy => "vf",
141 GraphFormat::EdgeList => "edge",
142 }
143 }
144}
145
146/// Configuration options for VF3 algorithm execution.
147#[derive(Debug, Clone)]
148pub struct RunOptions {
149 /// Graph file format.
150 pub format: GraphFormat,
151 /// Treat graphs as undirected.
152 pub undirected: bool,
153 /// Store all solution mappings in memory (may use significant memory for large result sets).
154 pub store_solutions: bool,
155 /// Stop after finding the first solution (sequential algorithms only).
156 pub first_only: bool,
157 /// Enable verbose output.
158 pub verbose: bool,
159 /// Minimum execution time in seconds for averaging multiple runs.
160 pub repetition_time_limit: f32,
161 /// Use edge-induced isomorphism (monomorphism) instead of node-induced.
162 pub edge_induced: bool,
163}
164
165impl Default for RunOptions {
166 fn default() -> Self {
167 Self {
168 format: GraphFormat::VFLegacy,
169 undirected: false,
170 store_solutions: false,
171 first_only: false,
172 verbose: false,
173 repetition_time_limit: 1.0,
174 edge_induced: false,
175 }
176 }
177}
178
179/// Configuration options for parallel VF3P execution.
180#[derive(Debug, Clone)]
181pub struct ParallelOptions {
182 /// Algorithm variant: 1 = GSS (Global State Stack), 2 = WLS (Work-stealing with Local Stack).
183 pub algo: i8,
184 /// Starting CPU for thread pinning (-1 disables pinning).
185 pub cpu: i16,
186 /// Number of worker threads (must be >= 1).
187 pub num_threads: i16,
188 /// Use lock-free stack implementation.
189 pub lock_free: bool,
190 /// Depth limit for forcing states into global stack (WLS only).
191 pub ssr_high_limit: i16,
192 /// Maximum size of thread-local stack (WLS only).
193 pub ssr_local_stack_limit: i16,
194}
195
196impl Default for ParallelOptions {
197 fn default() -> Self {
198 Self {
199 algo: 1,
200 cpu: -1,
201 num_threads: 1,
202 lock_free: false,
203 ssr_high_limit: 3,
204 ssr_local_stack_limit: 10,
205 }
206 }
207}
208
209/// Results from VF3 algorithm execution.
210#[derive(Debug, Clone)]
211pub struct ResultData {
212 /// Number of isomorphic mappings found.
213 pub solutions: u64,
214 /// Time to first solution in seconds.
215 pub time_first: f64,
216 /// Average total execution time in seconds.
217 pub time_all: f64,
218}
219
220#[cfg(not(docsrs))]
221fn convert_result(res: vf3ffi::VF3Result) -> Result<ResultData, VF3Error> {
222 if res.status == 0 {
223 Ok(ResultData {
224 solutions: res.solutions,
225 time_first: res.time_first,
226 time_all: res.time_all,
227 })
228 } else {
229 Err(VF3Error::ExecutionFailed { code: res.status })
230 }
231}
232
233/// Run VF3 algorithm with full heuristics.
234///
235/// Best suited for medium to large dense graphs.
236///
237/// # Errors
238///
239/// Returns [`VF3Error::ExecutionFailed`] if the C++ algorithm fails.
240pub fn run_vf3(pattern: &str, target: &str, opts: RunOptions) -> Result<ResultData, VF3Error> {
241 #[cfg(not(docsrs))]
242 {
243 let res = vf3ffi::run_vf3(
244 pattern,
245 target,
246 opts.format.as_str(),
247 opts.undirected,
248 opts.store_solutions,
249 opts.first_only,
250 opts.verbose,
251 opts.repetition_time_limit,
252 opts.edge_induced,
253 );
254 convert_result(res)
255 }
256 #[cfg(docsrs)]
257 {
258 let _ = (pattern, target, opts);
259 Err(VF3Error::FfiError {
260 message: "VF3 not available in docs.rs build".into(),
261 })
262 }
263}
264
265/// Run VF3L lightweight variant without look-ahead heuristic.
266///
267/// Best suited for small or sparse graphs.
268///
269/// # Errors
270///
271/// Returns [`VF3Error::ExecutionFailed`] if the C++ algorithm fails.
272pub fn run_vf3l(pattern: &str, target: &str, opts: RunOptions) -> Result<ResultData, VF3Error> {
273 #[cfg(not(docsrs))]
274 {
275 let res = vf3ffi::run_vf3l(
276 pattern,
277 target,
278 opts.format.as_str(),
279 opts.undirected,
280 opts.store_solutions,
281 opts.first_only,
282 opts.verbose,
283 opts.repetition_time_limit,
284 opts.edge_induced,
285 );
286 convert_result(res)
287 }
288 #[cfg(docsrs)]
289 {
290 let _ = (pattern, target, opts);
291 Err(VF3Error::FfiError {
292 message: "VF3L not available in docs.rs build".into(),
293 })
294 }
295}
296
297/// Run VF3P parallel variant with multi-threading support.
298///
299/// Best suited for computationally hard instances that benefit from parallelization.
300///
301/// # Errors
302///
303/// Returns [`VF3Error::ExecutionFailed`] if the C++ algorithm fails.
304pub fn run_vf3p(
305 pattern: &str,
306 target: &str,
307 opts: RunOptions,
308 par: ParallelOptions,
309) -> Result<ResultData, VF3Error> {
310 #[cfg(not(docsrs))]
311 {
312 let res = vf3ffi::run_vf3p(
313 pattern,
314 target,
315 opts.format.as_str(),
316 opts.undirected,
317 opts.store_solutions,
318 opts.verbose,
319 opts.repetition_time_limit,
320 opts.edge_induced,
321 par.algo,
322 par.cpu,
323 par.num_threads,
324 par.lock_free,
325 par.ssr_high_limit,
326 par.ssr_local_stack_limit,
327 );
328 convert_result(res)
329 }
330 #[cfg(docsrs)]
331 {
332 let _ = (pattern, target, opts, par);
333 Err(VF3Error::FfiError {
334 message: "VF3P not available in docs.rs build".into(),
335 })
336 }
337}
338
339/// Builder for configuring and executing VF3 subgraph isomorphism queries.
340///
341/// Provides a fluent API for setting options and choosing algorithm variants.
342///
343/// # Examples
344///
345/// ```no_run
346/// use vf3lib_rs::VF3Query;
347///
348/// // Simple usage with default settings
349/// let result = VF3Query::new("pattern.grf", "target.grf")
350/// .run()?;
351///
352/// // Edge-induced matching with VF3L variant
353/// let result = VF3Query::new("pattern.grf", "target.grf")
354/// .edge_induced()
355/// .undirected()
356/// .run_light()?;
357///
358/// // Parallel execution with custom thread count
359/// let result = VF3Query::new("pattern.grf", "target.grf")
360/// .with_threads(4)
361/// .run_parallel()?;
362/// # Ok::<(), vf3lib_rs::VF3Error>(())
363/// ```
364pub struct VF3Query<'a> {
365 pattern: &'a str,
366 target: &'a str,
367 options: RunOptions,
368 parallel: ParallelOptions,
369}
370
371impl<'a> VF3Query<'a> {
372 /// Create a new query with the given pattern and target graph files.
373 pub fn new(pattern: &'a str, target: &'a str) -> Self {
374 Self {
375 pattern,
376 target,
377 options: RunOptions::default(),
378 parallel: ParallelOptions::default(),
379 }
380 }
381
382 /// Set the graph file format.
383 pub fn format(mut self, format: GraphFormat) -> Self {
384 self.options.format = format;
385 self
386 }
387
388 /// Treat graphs as undirected.
389 pub fn undirected(mut self) -> Self {
390 self.options.undirected = true;
391 self
392 }
393
394 /// Treat graphs as directed (default).
395 pub fn directed(mut self) -> Self {
396 self.options.undirected = false;
397 self
398 }
399
400 /// Use edge-induced isomorphism (monomorphism) instead of node-induced.
401 pub fn edge_induced(mut self) -> Self {
402 self.options.edge_induced = true;
403 self
404 }
405
406 /// Use node-induced isomorphism (default).
407 pub fn node_induced(mut self) -> Self {
408 self.options.edge_induced = false;
409 self
410 }
411
412 /// Store all solution mappings in memory.
413 ///
414 /// Warning: This may use significant memory for large result sets.
415 pub fn store_solutions(mut self) -> Self {
416 self.options.store_solutions = true;
417 self
418 }
419
420 /// Stop after finding the first solution (sequential algorithms only).
421 pub fn first_only(mut self) -> Self {
422 self.options.first_only = true;
423 self
424 }
425
426 /// Enable verbose output.
427 pub fn verbose(mut self) -> Self {
428 self.options.verbose = true;
429 self
430 }
431
432 /// Set minimum execution time in seconds for averaging multiple runs.
433 pub fn repetition_time_limit(mut self, seconds: f32) -> Self {
434 self.options.repetition_time_limit = seconds;
435 self
436 }
437
438 /// Set the number of worker threads for parallel execution.
439 pub fn with_threads(mut self, num_threads: i16) -> Self {
440 self.parallel.num_threads = num_threads;
441 self
442 }
443
444 /// Set the parallel algorithm variant.
445 ///
446 /// * `1` - GSS (Global State Stack)
447 /// * `2` - WLS (Work-stealing with Local Stack)
448 pub fn parallel_algorithm(mut self, algo: i8) -> Self {
449 self.parallel.algo = algo;
450 self
451 }
452
453 /// Enable lock-free stack implementation for parallel execution.
454 pub fn lock_free(mut self) -> Self {
455 self.parallel.lock_free = true;
456 self
457 }
458
459 /// Run the VF3 algorithm with full heuristics.
460 ///
461 /// Best suited for medium to large dense graphs.
462 ///
463 /// # Errors
464 ///
465 /// Returns [`VF3Error::ExecutionFailed`] if the algorithm fails.
466 pub fn run(self) -> Result<ResultData, VF3Error> {
467 run_vf3(self.pattern, self.target, self.options)
468 }
469
470 /// Run the VF3L lightweight variant without look-ahead heuristic.
471 ///
472 /// Best suited for small or sparse graphs.
473 ///
474 /// # Errors
475 ///
476 /// Returns [`VF3Error::ExecutionFailed`] if the algorithm fails.
477 pub fn run_light(self) -> Result<ResultData, VF3Error> {
478 run_vf3l(self.pattern, self.target, self.options)
479 }
480
481 /// Run the VF3P parallel variant with multi-threading support.
482 ///
483 /// Best suited for computationally hard instances.
484 ///
485 /// # Errors
486 ///
487 /// Returns [`VF3Error::ExecutionFailed`] if the algorithm fails.
488 pub fn run_parallel(self) -> Result<ResultData, VF3Error> {
489 run_vf3p(self.pattern, self.target, self.options, self.parallel)
490 }
491}