pattern_core/graph/
graph_classifier.rs

1//! Graph classifier — structural classification of `Pattern<V>` values.
2//!
3//! Ported from `Pattern.Graph.GraphClassifier` in the Haskell reference implementation.
4
5use std::hash::Hash;
6
7use crate::pattern::Pattern;
8use crate::subject::{Subject, Symbol};
9
10// -----------------------------------------------------------------------------
11// GraphValue trait
12// -----------------------------------------------------------------------------
13
14/// Value types that can be used with `GraphClassifier` and `PatternGraph`.
15pub trait GraphValue {
16    type Id: Ord + Clone + Hash;
17    fn identify(&self) -> &Self::Id;
18}
19
20impl GraphValue for Subject {
21    type Id = Symbol;
22
23    fn identify(&self) -> &Symbol {
24        &self.identity
25    }
26}
27
28// -----------------------------------------------------------------------------
29// GraphClass enum
30// -----------------------------------------------------------------------------
31
32/// The five structural categories a pattern can belong to.
33#[derive(Debug, Clone, PartialEq, Eq)]
34pub enum GraphClass<Extra> {
35    GNode,
36    GRelationship,
37    GAnnotation,
38    GWalk,
39    GOther(Extra),
40}
41
42impl<Extra> GraphClass<Extra> {
43    /// Maps a function over the `Extra` payload of `GOther`, leaving other variants unchanged.
44    pub fn map_other<F, B>(self, f: F) -> GraphClass<B>
45    where
46        F: FnOnce(Extra) -> B,
47    {
48        match self {
49            GraphClass::GNode => GraphClass::GNode,
50            GraphClass::GRelationship => GraphClass::GRelationship,
51            GraphClass::GAnnotation => GraphClass::GAnnotation,
52            GraphClass::GWalk => GraphClass::GWalk,
53            GraphClass::GOther(e) => GraphClass::GOther(f(e)),
54        }
55    }
56}
57
58// -----------------------------------------------------------------------------
59// GraphClassifier struct
60// -----------------------------------------------------------------------------
61
62/// Injectable classification strategy wrapping a boxed closure.
63pub struct GraphClassifier<Extra, V> {
64    #[allow(clippy::type_complexity)]
65    pub classify: Box<dyn Fn(&Pattern<V>) -> GraphClass<Extra> + 'static>,
66}
67
68impl<Extra, V> GraphClassifier<Extra, V> {
69    /// Creates a new `GraphClassifier` from a classification function.
70    pub fn new<F>(f: F) -> Self
71    where
72        F: Fn(&Pattern<V>) -> GraphClass<Extra> + 'static,
73    {
74        GraphClassifier {
75            classify: Box::new(f),
76        }
77    }
78}
79
80// -----------------------------------------------------------------------------
81// Private shape helpers
82// -----------------------------------------------------------------------------
83
84fn is_node_like<V>(p: &Pattern<V>) -> bool {
85    p.elements.is_empty()
86}
87
88fn is_relationship_like<V>(p: &Pattern<V>) -> bool {
89    p.elements.len() == 2 && p.elements.iter().all(is_node_like)
90}
91
92/// Frontier-based walk validation. Direction-agnostic: either endpoint can match.
93fn is_valid_walk<V: GraphValue>(rels: &[Pattern<V>]) -> bool {
94    if rels.is_empty() {
95        return false;
96    }
97
98    // Seed the frontier with both endpoints of the first relationship.
99    let first = &rels[0];
100    if first.elements.len() != 2 {
101        return false;
102    }
103    let mut frontier: Vec<&Pattern<V>> = vec![&first.elements[0], &first.elements[1]];
104
105    for rel in &rels[1..] {
106        if rel.elements.len() != 2 {
107            return false;
108        }
109        let a = &rel.elements[0];
110        let b = &rel.elements[1];
111
112        let a_id = a.value.identify();
113        let b_id = b.value.identify();
114
115        let a_matches = frontier.iter().any(|x| x.value.identify() == a_id);
116        let b_matches = frontier.iter().any(|x| x.value.identify() == b_id);
117
118        frontier = match (a_matches, b_matches) {
119            (true, false) => vec![b],
120            (false, true) => vec![a],
121            (true, true) => vec![a, b],
122            (false, false) => return false,
123        };
124    }
125
126    !frontier.is_empty()
127}
128
129// -----------------------------------------------------------------------------
130// Public classification functions
131// -----------------------------------------------------------------------------
132
133/// Classifies a pattern by its structural shape.
134pub fn classify_by_shape<V: GraphValue>(pattern: &Pattern<V>) -> GraphClass<()> {
135    let els = &pattern.elements;
136
137    if els.is_empty() {
138        GraphClass::GNode
139    } else if els.len() == 1 {
140        GraphClass::GAnnotation
141    } else if els.len() == 2 && els.iter().all(is_node_like) {
142        GraphClass::GRelationship
143    } else if els.iter().all(is_relationship_like) && is_valid_walk(els) {
144        GraphClass::GWalk
145    } else {
146        GraphClass::GOther(())
147    }
148}
149
150/// Returns the standard shape-based classifier.
151pub fn canonical_classifier<V: GraphValue + 'static>() -> GraphClassifier<(), V> {
152    GraphClassifier::new(|p| classify_by_shape(p))
153}
154
155/// Wraps a node predicate into a two-category classifier (`GNode` vs `GOther(())`).
156pub fn from_test_node<V, F>(test_node: F) -> GraphClassifier<(), V>
157where
158    F: Fn(&Pattern<V>) -> bool + 'static,
159{
160    GraphClassifier::new(move |p| {
161        if test_node(p) {
162            GraphClass::GNode
163        } else {
164            GraphClass::GOther(())
165        }
166    })
167}
pattern_core/graph/graph_classifier.rs

pattern_core/graph/
graph_classifier.rs
