graphfind_rs/pattern_matching/
pattern.rs

1use crate::graph::Graph;
2
3use super::Matcher;
4
5/// Struct that holds all relevant matching information for a single node/edge.
6pub struct PatternElement<Weight> {
7    /// The matching function.
8    ///
9    condition: Box<Matcher<Weight>>,
10    ///
11    /// A flag that tells us if we should include the matched element in the result, or not.
12    ignore: bool,
13}
14
15/// Holds the constructor for Matcher.
16impl<Weight> PatternElement<Weight> {
17    /// Creates a new Matcher struct. If `ignore` is true, the node/edge will be hidden from the result graph.
18    pub fn new(condition: Box<Matcher<Weight>>, ignore: bool) -> Self {
19        Self { condition, ignore }
20    }
21
22    /// Checks the matched node should appear in the result graph.
23    pub fn should_appear(&self) -> bool {
24        !self.ignore
25    }
26
27    /// Tests if the given element matches the condition this matcher.
28    pub fn may_match(&self, element: &Weight) -> bool {
29        (self.condition)(element)
30    }
31}
32
33/// Defines a pattern graph, i.e. a specification for subgraphs that we want to find. This trait
34/// extends the Graph trait, to allow for navigation & getting subgraph info.
35///
36/// A pattern graph uses matcher functions as weights.
37/// With matcher functions, we can test if an element semantically fits to a subgraph to be found,
38/// for example, if it matches a given Rust pattern.
39///
40/// PatternGraph is generic with regards to node and edge weights of the graphs it should match on.
41pub trait PatternGraph<NodeWeight, EdgeWeight>:
42    Graph<PatternElement<NodeWeight>, PatternElement<EdgeWeight>>
43{
44    /// Adds a new node to the pattern.
45    ///
46    /// A matched node appears in the result graph.
47    ///
48    /// ## Input:
49    /// `condition`, a [Matcher] that holds a function to test if a node in a base graph matches what we want in the pattern graph.
50    ///
51    /// ## Output:
52    /// A node reference.
53    fn add_node<C>(&mut self, condition: C) -> Self::NodeRef
54    where
55        C: Fn(&NodeWeight) -> bool + 'static;
56    /// Adds a new hidden node to the pattern.
57    /// A node that matches does not appear in the result graph, but is required to exist in the searched graph.
58    ///
59    /// ## Input:
60    /// condition, a `Matcher` that holds a function to test if a node in a base graph matches.
61    /// what we want in the pattern graph.
62    ///
63    /// ## Output:
64    /// A node reference.
65    fn add_hidden_node<C>(&mut self, condition: C) -> Self::NodeRef
66    where
67        C: Fn(&NodeWeight) -> bool + 'static;
68
69    /// Adds a new edge to the pattern. This edge will appear in the result graphs.
70    ///
71    /// ## Input:
72    /// 1. `from`, the source node of the new edge.
73    /// 2. `to`, the destination node.
74    /// 3. `condition`, a function to test if an edge in a base graph matches
75    /// what we want in the pattern graph.
76    ///
77    /// ## Output:
78    /// An edge reference.
79    ///
80    /// ## Panics:
81    /// Panics if one of the adjacent nodes is a hidden node.
82    fn add_edge<C>(
83        &mut self,
84        from: Self::NodeRef,
85        to: Self::NodeRef,
86        condition: C,
87    ) -> Self::EdgeRef
88    where
89        C: Fn(&EdgeWeight) -> bool + 'static;
90    /// Adds a new, directed, hidden edge to the pattern.
91    ///
92    /// An edge that matches does not appear in the result graph, but is required to exist in the searched graph.
93    ///
94    /// ## Input:
95    /// 1. `from`, the source node of the new edge.
96    /// 2. `to`, the destination node.
97    /// 3. `condition`, a function to test if an edge in a base graph matches
98    /// what we want in the pattern graph.
99    ///
100    /// ## Output:
101    /// An edge reference.
102    fn add_hidden_edge<C>(
103        &mut self,
104        from: Self::NodeRef,
105        to: Self::NodeRef,
106        condition: C,
107    ) -> Self::EdgeRef
108    where
109        C: Fn(&EdgeWeight) -> bool + 'static;
110}
graphfind_rs/pattern_matching/pattern.rs

graphfind_rs/pattern_matching/
pattern.rs
