vf3 0.1.0

Rust implementation of VF3/VF3L subgraph isomorphism algorithms
Documentation

vf3 — Pure Rust VF3/VF3L Implementation

Crates.io Documentation CI License

A pure Rust implementation of the VF3/VF3L subgraph isomorphism algorithms, inspired by the canonical C++ implementation from MIVIA Lab.

Features

  • Pure Rust: No C++ dependencies for the core algorithm
  • VF3L Algorithm: Lightweight variant without look-ahead heuristics
  • Flexible Matching: Both node-induced and edge-induced (monomorphism) modes
  • Graph Labels: Optional node and edge label matching
  • Undirected Support: Can treat directed graphs as undirected
  • Incremental Terminal Sets: Core VF3 pruning mechanism with in/out/union sets

Status

This is a functional implementation that works well on small to medium graphs. It implements:

  • Edge-induced (monomorphism) and node-induced subgraph isomorphism
  • Incremental terminal sets with VF3L pruning
  • Degree/signature-based pattern ordering heuristic
  • Node and edge label support

Not yet implemented:

  • Full VF3 look-ahead pruning
  • VF3P parallel variant

Installation

Add this to your Cargo.toml:

[dependencies]
vf3 = "0.1"

Quick Start

use vf3::{Graph, VF3Options, find_subgraph_matches_with_options};

// Create a pattern graph (triangle)
let mut pattern = Graph::new(3);
pattern.add_edge(0, 1)?;
pattern.add_edge(1, 2)?;
pattern.add_edge(2, 0)?;

// Create a target graph (square)
let mut target = Graph::new(4);
target.add_edge(0, 1)?;
target.add_edge(1, 2)?;
target.add_edge(2, 3)?;
target.add_edge(3, 0)?;

// Find all matches (node-induced by default)
let opts = VF3Options::default();
let matches = find_subgraph_matches_with_options(&pattern, &target, None, &opts);
println!("Found {} matches", matches.len());

Options

pub struct VF3Options {
    /// Use node-induced subgraph isomorphism (true) or edge-induced/monomorphism (false)
    pub node_induced: bool,

    /// Treat graphs as undirected (ignores edge direction)
    pub undirected: bool,

    /// Require matching node labels
    pub use_node_labels: bool,

    /// Require matching edge labels
    pub use_edge_labels: bool,
}

Working with Labels

// Node labels
let mut g = Graph::new(3);
g.set_label(0, 1);  // Node 0 has label 1
g.set_label(1, 2);  // Node 1 has label 2

// Edge labels
g.add_edge_with_label(0, 1, 42)?;  // Edge with label 42
g.add_edge(1, 2)?;                  // Edge with default label 0

// Enable label matching
let opts = VF3Options {
    use_node_labels: true,
    use_edge_labels: true,
    ..Default::default()
};

Performance

For best performance, compile with release optimizations:

cargo build --release

# With CPU-specific optimizations
RUSTFLAGS="-C target-cpu=native" cargo build --release

Performance and Safety

This crate uses unsafe code in performance-critical sections to achieve competitive performance with C++ implementations. The unsafe code is:

  • Limited to hot paths: Primarily in the lookahead_neighbor_capacity function which is called millions of times during graph matching
  • Well-documented: Every unsafe block includes SAFETY comments explaining the invariants
  • Bounds-check elimination: Removes redundant bounds checks where indices are already validated by the algorithm's invariants
  • Performance-justified: Subgraph isomorphism is NP-complete; these optimizations provide significant speedup (typically 2-3x) on real workloads

The unsafe optimizations include:

  • Using get_unchecked for array access where bounds are guaranteed by construction
  • Stack-allocated arrays for small label domains to avoid heap allocation
  • Direct bitset access for O(1) edge existence checks

All unsafe code follows Rust's safety guidelines and the invariants are maintained by the VF3State structure. The codebase has been thoroughly tested and follows patterns used in other high-performance Rust graph libraries.

Comparison with C++ Implementation

This crate includes an optional feature to compare against the C++ VF3 implementation via FFI:

# Run comparison tests
cargo test --features compare-cpp

# Run benchmarks comparing both implementations
cargo bench vf3_vs_cpp --features compare-cpp

Examples

# Basic usage example
cargo run --example basic

# Performance testing harness
cargo run --example bench-harness --release

CLI Tool

The crate includes a command-line tool for running VF3 on JSON graph files:

# Install the CLI tool
cargo install --path .

# Run on graph files
vf3 --pattern pattern.json --target target.json

# With options
vf3 --pattern p.json --target t.json --node-induced --use-node-labels

Algorithm Details

This implementation follows the VF3L (lightweight) variant which:

  1. Uses terminal sets (Tin, Tout, Tunion) for pruning the search space
  2. Orders pattern nodes by rarity (degree and optional label frequency)
  3. Performs feasibility checks for each candidate mapping
  4. Backtracks efficiently when no valid mapping exists

The algorithm is particularly effective on sparse graphs and when the pattern is much smaller than the target.

License

MIT OR Apache-2.0

References