graphfind_rs/pattern_matching/
mod.rs

1//!
2//! The problem being solved here is finding subgraphs matching
3//! a given subgraph pattern in a larger base graph. The subgraph
4//! pattern is a graph where each element weight is a condition on a base graph element.
5//!  A valid match is a subgraph of the base graph that is isomorphic to the
6//! pattern where each element fulfils the condition of the corresponding
7//! pattern element.
8//!
9//! It is also possible to add hidden subgraph elements, that are removed from the matches before returning them to the caller.
10//!
11//! While the architecture is designed to eventually support multiple matching
12//! implementations, currently only one VF based algorithm is implemented. The
13//! easiest way to use it is creating a new pattern with
14//! [pattern_matching::new_pattern] and passing that pattern to
15//! [pattern_matching::solve_vf]. Conditions in the pattern graph can be either constructed as function closures or with the [matcher] macro.
16//!
17//! For examples see the unit tests for this module (located in the `tests` folder of the crate source).
18
19use vf_algorithms::VfState;
20
21use crate::graph::Graph;
22
23/// Module that contains an implementation for subgraph algorithms.
24///
25/// Goal: Contain Subgraph Isomorphism Algorithms based on the VF family (VF2, VF2+, VF3...).
26pub mod vf_algorithms;
27
28/// Definition of matcher types.
29mod matcher;
30pub use matcher::*;
31
32/// Definition of pattern types.
33mod pattern;
34pub use pattern::*;
35
36/// trait specifying a generic algorithm for solving subgraph matching
37mod algorithm;
38pub use algorithm::*;
39
40/// Creates an empty new graph pattern.
41pub fn new_pattern<NodeWeight, EdgeWeight>() -> impl PatternGraph<NodeWeight, EdgeWeight> {
42    petgraph::Graph::new()
43}
44
45/// Solve a graph matching problem instance using an approach based the VF algorithms.
46///
47/// The algorithm implementation used is provided by the [vf_algorithms] module.
48///
49/// See the [SubgraphAlgorithm::eval] documentation on how to use it.
50pub fn solve_vf<'a, N, E, Pattern>(
51    pattern_graph: &'a Pattern,
52    base_graph: &'a impl Graph<N, E>,
53) -> Vec<MatchedGraph<'a, N, E, Pattern>>
54where
55    Pattern: PatternGraph<N, E>,
56{
57    VfState::eval(pattern_graph, base_graph)
58}
graphfind_rs/pattern_matching/mod.rs

graphfind_rs/pattern_matching/
mod.rs
