graphfind_rs/pattern_matching/
algorithm.rs

1use std::hash::Hash;
2
3use crate::{filter_map::FilterMap, graph::Graph};
4
5use super::{PatternElement, PatternGraph};
6/// The SubgraphAlgorithm trait specifies any algorithm that can solve the subgraph isomorphism problem.
7/// Solving this problem lies at the core of graph pattern matching.
8pub trait SubgraphAlgorithm<
9    'a,
10    NodeWeight,
11    EdgeWeight,
12    NRef,
13    ERef,
14    N2Ref,
15    E2Ref,
16    PatternGraphType,
17    BaseGraphType,
18> where
19    NRef: Copy + Eq + Hash,
20    N2Ref: Copy + Eq + Hash,
21    PatternGraphType: PatternGraph<NodeWeight, EdgeWeight, NodeRef = NRef, EdgeRef = ERef>,
22    BaseGraphType: Graph<NodeWeight, EdgeWeight, NodeRef = N2Ref, EdgeRef = E2Ref>,
23{
24    /// Creates and evaluates a query to find all subgraphs of `base_graph` that match `pattern_graph`.
25    ///
26    /// # Input:
27    /// Two graphs, `base_graph` (any Graph instance), and `pattern_graph` (a PatternGraph instance).
28    /// `base_graph` and `pattern_graph` share both node and edge types (NodeWeight/EdgeWeight).
29    ///
30    /// `pattern_graph` uses NRef and ERef for references over nodes and edges.
31    /// `base_graph` uses N2Ref and E2Ref respectively.
32    ///
33    /// Both `pattern_graph` and `base_graph` currently have the same lifetime 'a.
34    ///
35    /// # Output:
36    /// A reference to a vector of MatchedGraph, whose nodes and edges have NodeWeight/EdgeWeight types,
37    /// and its references NRef/ERef. We want to access matched elements of
38    /// the base graph by references we set in the pattern graph.
39    ///
40    /// An implementation find_subgraphs should guarantee set semantics, so that every found
41    /// graph pattern occurs only once.
42    ///
43    /// If `pattern_graph` is an empty graph without nodes (or edges), or if no subgraph of `base_graph`
44    /// can be matched to it, then we return an empty vector.
45    ///
46    /// # Panics:
47    /// `base_graph` is a directed graph, and `pattern_graph` is not, or vice versa.
48    fn eval(
49        pattern_graph: &'a PatternGraphType,
50        base_graph: &'a BaseGraphType,
51    ) -> Vec<MatchedGraph<'a, NodeWeight, EdgeWeight, PatternGraphType>>;
52}
53/// Type definition of MatchedGraph.
54pub type MatchedGraph<'a, N, E, P> =
55    FilterMap<'a, PatternElement<N>, PatternElement<E>, &'a N, &'a E, P>;
graphfind_rs/pattern_matching/algorithm.rs

graphfind_rs/pattern_matching/
algorithm.rs
