Crate vf2

This crate implements the VF2 subgraph isomorphism algorithm. It can find graph isomorphisms, subgraph isomorphisms, and induced subgraph isomorphisms. Graphs can be directed or undirected.

See the repository for more information.

Usage

Add vf2 to your dependencies in Cargo.toml.

[dependencies]
vf2 = "1.0"

Create your query and data graphs with petgraph or any library that implements the Graph trait. Then, call one of the following functions based on the problem type.

Problem type	Call
Graph isomorphisms	vf2::isomorphisms
Subgraph isomorphisms	vf2::subgraph_isomorphisms
Induced subgraph isomorphisms	vf2::induced_subgraph_isomorphisms

These return a Vf2Builder with the algorithm configured. Next, call one of the following on the builder to enumerate the isomorphisms.

Desired output	Call
First isomorphism	first
Vector of isomorphisms	vec
Iterator of isomorphisms	iter

Filling a vector can consume a significant amount of memory. Use the iterator to inspect isomorphisms as they are found. For the best performance, call next_ref on the iterator instead of next to avoid cloning each isomorphism.

You can configure the node and edge equality functions on the builder with node_eq and edge_eq, respectively.

Example

This example shows how to find subgraph isomorphisms.

use petgraph::data::{Element, FromElements};
use petgraph::graph::DiGraph;

// Create query graph.
let query = DiGraph::<i32, ()>::from_elements([
    Element::Node { weight: 0, },
    Element::Node { weight: 1, },
    Element::Edge { source: 0, target: 1, weight: () },
]);

// Create data graph.
let data = DiGraph::<i32, ()>::from_elements([
    Element::Node { weight: 0, },
    Element::Node { weight: 1, },
    Element::Node { weight: 2, },
    Element::Edge { source: 0, target: 1, weight: () },
    Element::Edge { source: 1, target: 2, weight: () },
]);

// Find subgraph isomorphisms.
let isomorphisms = vf2::subgraph_isomorphisms(&query, &data).vec();
assert_eq!(isomorphisms, vec![vec![0, 1], vec![1, 2]]);

Structs

IsomorphismIter

An isomorphism iterator.

Vf2Builder

A VF2 builder used to configure the algorithm.

Enums

Direction

Edge direction, either outgoing or incoming.

Problem

Problem type.

Traits

Graph

A graph.

Functions

induced_subgraph_isomorphisms

Creates a new Vf2Builder to find induced subgraph isomorphisms from query to data.

isomorphisms

Creates a new Vf2Builder to find isomorphisms from query to data.

subgraph_isomorphisms

Creates a new Vf2Builder to find subgraph isomorphisms from query to data.

Type Aliases

DefaultVf2Builder

Default VF2 builder type.

Isomorphism

An isomorphism mapping query nodes to data nodes.

NodeIndex

A node index.