zawgl_core/matcher/vf2/
state.rs

1// MIT License
2// Copyright (c) 2022 Alexandre RICCIARDI
3// Permission is hereby granted, free of charge, to any person obtaining a copy
4// of this software and associated documentation files (the "Software"), to deal
5// in the Software without restriction, including without limitation the rights
6// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
7// copies of the Software, and to permit persons to whom the Software is
8// furnished to do so, subject to the following conditions:
9//
10// The above copyright notice and this permission notice shall be included in all
11// copies or substantial portions of the Software.
12//
13// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
18// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
19// SOFTWARE.
20
21use std::collections::HashSet;
22use std::collections::HashMap;
23use std::collections::hash_map::Entry;
24use log::trace;
25
26use crate::graph_engine::model::GraphProxy;
27use crate::graph_engine::model::ProxyNodeId;
28use crate::graph_engine::model::ProxyRelationshipId;
29use crate::model::Node;
30use crate::model::PropertyGraph;
31use crate::model::Relationship;
32
33use super::base_state::*;
34use super::super::super::graph::traits::*;
35use super::super::super::graph::*;
36
37fn inc_in<NID0, NID1>(base_state: &mut BaseState<NID0, NID1>, v0: &NID0)  where NID0: std::hash::Hash + Eq + Copy, NID1: std::hash::Hash + Eq + Copy {
38    base_state.term_in_count += 1;
39    if base_state.out_map.contains_key(v0) {
40        base_state.term_both_count += 1;
41    }
42}
43fn inc_out<NID0, NID1>(base_state: &mut BaseState<NID0, NID1>, v0: &NID0)  where NID0: std::hash::Hash + Eq + Copy, NID1: std::hash::Hash + Eq + Copy {
44    base_state.term_out_count += 1;
45    if base_state.in_map.contains_key(v0) {
46        base_state.term_both_count += 1;
47    }
48}
49
50
51fn inc_term<NID0, NID1>(base_state: &mut BaseState<NID0, NID1>, v0: &NID0)  where NID0: std::hash::Hash + Eq + Copy, NID1: std::hash::Hash + Eq + Copy {
52    if !base_state.in_map.contains_key(v0) {
53        base_state.in_map.insert(*v0, base_state.core_count);
54        inc_in(base_state, v0);
55    }
56    if !base_state.out_map.contains_key(v0) {
57        base_state.out_map.insert(*v0, base_state.core_count);
58        inc_out(base_state, v0);
59    }
60}
61
62fn dec_in<NID0, NID1>(base_state: &mut BaseState<NID0, NID1>, v0: &NID0)  where NID0: std::hash::Hash + Eq + Copy, NID1: std::hash::Hash + Eq + Copy {
63    base_state.term_in_count -= 1;
64    if base_state.out_map.contains_key(v0) && base_state.term_both_count > 0 {
65        base_state.term_both_count -= 1;
66    }
67}
68fn dec_out<NID0, NID1>(base_state: &mut BaseState<NID0, NID1>, v0: &NID0)  where NID0: std::hash::Hash + Eq + Copy, NID1: std::hash::Hash + Eq + Copy {
69    base_state.term_out_count -= 1;
70    if base_state.in_map.contains_key(v0) && base_state.term_both_count > 0 {
71        base_state.term_both_count -= 1;
72    }
73}
74fn dec_in_term<NID0, NID1>(base_state: &mut BaseState<NID0, NID1>, v0: &NID0)  where NID0: std::hash::Hash + Eq + Copy, NID1: std::hash::Hash + Eq + Copy {
75    if let Some(in_count) = base_state.in_map.get(v0) {
76        if *in_count == base_state.core_count {
77            base_state.in_map.remove(v0);
78            dec_in(base_state, v0);
79        }
80    }
81}
82
83fn dec_out_term<NID0, NID1>(base_state: &mut BaseState<NID0, NID1>, v0: &NID0)  where NID0: std::hash::Hash + Eq + Copy, NID1: std::hash::Hash + Eq + Copy {
84    if let Some(out_count) = base_state.out_map.get(v0) {
85        if *out_count == base_state.core_count {
86            base_state.out_map.remove(v0);
87            dec_out(base_state, v0);
88        }
89    }
90}
91
92fn inc_source<NID0, NID1>(base_state: &mut BaseState<NID0, NID1>, ancestor: NID0)  where NID0: std::hash::Hash + Eq + Copy, NID1: std::hash::Hash + Eq + Copy {
93    if let Entry::Vacant(e) = base_state.in_map.entry(ancestor) {
94        e.insert(base_state.core_count);
95        inc_in(base_state, &ancestor);
96    }
97}
98
99fn inc_target<NID0, NID1>(base_state: &mut BaseState<NID0, NID1>, successor: NID0)  where NID0: std::hash::Hash + Eq + Copy, NID1: std::hash::Hash + Eq + Copy {
100    if let Entry::Vacant(e) = base_state.out_map.entry(successor) {
101        e.insert(base_state.core_count);
102        inc_out(base_state, &successor);
103    }
104}
105
106fn dec_source<NID0, NID1>(base_state: &mut BaseState<NID0, NID1>, source: &NID0)  where NID0: std::hash::Hash + Eq + Copy, NID1: std::hash::Hash + Eq + Copy {
107    if let Some(in_count) = base_state.in_map.get(source) {
108        if *in_count == base_state.core_count {
109            base_state.in_map.remove(source);
110            dec_in(base_state, source);
111        }
112    }
113}
114
115fn dec_target<NID0, NID1>(base_state: &mut BaseState<NID0, NID1>, target: &NID0)  where NID0: std::hash::Hash + Eq + Copy, NID1: std::hash::Hash + Eq + Copy {
116    if let Some(out_count) = base_state.out_map.get(target) {
117        if *out_count == base_state.core_count {
118            base_state.out_map.remove(target);
119            dec_out(base_state, target);
120        }
121    }
122}
123
124pub fn push_state_0(base_state: &mut BaseState<NodeIndex, ProxyNodeId>, graph: &PropertyGraph, v0: &NodeIndex, v1: &ProxyNodeId) {  
125    base_state.core_map.insert(*v0, *v1);
126    base_state.core_count += 1;
127
128    inc_term(base_state, v0);
129
130    for edge_index in graph.in_edges(v0) {
131        let ancestor = graph.get_source_index(&edge_index);
132        inc_source(base_state, ancestor);
133    }
134    for edge_index in graph.out_edges(v0) {
135        let successor = graph.get_target_index(&edge_index);
136        inc_target(base_state, successor);
137    }
138}
139
140pub fn pop_state_0(base_state: &mut BaseState<NodeIndex, ProxyNodeId>, graph: &PropertyGraph, v0: &NodeIndex) {  
141    if base_state.core_count == 0 {
142        return;
143    }
144
145    dec_in_term(base_state, v0);
146    for in_edge in graph.in_edges(v0) {
147        let source = graph.get_source_index(&in_edge);
148        dec_source(base_state, &source);
149    }
150
151    dec_out_term(base_state, v0);
152
153    for out_edge in graph.out_edges(v0) {
154        let target = graph.get_target_index(&out_edge);
155        dec_target(base_state, &target);
156    }
157
158    base_state.core_count -= 1;
159
160    base_state.core_map.remove(v0);
161}
162
163
164pub fn push_state_1(base_state: &mut BaseState<ProxyNodeId, NodeIndex>, graph: & mut GraphProxy, v0: &ProxyNodeId, v1: &NodeIndex) -> Option<()> {  
165    base_state.core_count += 1;
166    base_state.core_map.insert(*v0, *v1);
167    inc_term(base_state, v0);
168    for (_edge_index, ancestor, _rel) in graph.in_edges(v0)? {
169        inc_source(base_state, ancestor);
170    }
171    for (_edge_index, successor, _rel) in graph.out_edges(v0)? {
172        inc_target(base_state, successor);
173    }
174    Some(())
175}
176
177pub fn pop_state_1(base_state: &mut BaseState<ProxyNodeId, NodeIndex>, graph: &mut GraphProxy, v0: &ProxyNodeId) -> Option<()> {  
178    if base_state.core_count == 0 {
179        return Some(());
180    }
181
182    dec_in_term(base_state, v0);
183
184    for (_in_edge, source, _rel) in graph.in_edges(v0)? {
185        dec_source(base_state, &source);
186    }
187
188    dec_out_term(base_state, v0);
189
190    for (_out_edge, target, _rel) in graph.out_edges(v0)? {
191        dec_target(base_state, &target);
192    }
193
194    base_state.core_map.remove(v0);
195
196    base_state.core_count -= 1;
197    Some(())
198}
199
200pub struct State<'g0, VCOMP, ECOMP>
201    where VCOMP: Fn(&Node, &Node) -> bool, ECOMP: Fn(&Relationship, &Relationship) -> bool {
202    graph_0: &'g0 PropertyGraph,
203    vertex_comp: VCOMP,
204    edge_comp: ECOMP,
205    base_state_0: BaseState<NodeIndex, ProxyNodeId>,
206    base_state_1: BaseState<ProxyNodeId, NodeIndex>,
207
208}
209
210impl <'g0, VCOMP, ECOMP> State<'g0, VCOMP, ECOMP>
211    where VCOMP: Fn(&Node, &Node) -> bool, ECOMP: Fn(&Relationship, &Relationship) -> bool {
212
213
214        pub fn new(graph_0: &'g0 PropertyGraph, vcomp: VCOMP, ecomp: ECOMP) -> Self {
215            State {
216                graph_0,
217                vertex_comp: vcomp,
218                edge_comp: ecomp,
219                base_state_0: BaseState::new(),
220                base_state_1: BaseState::new(),
221            }
222        }
223
224        pub fn push(&mut self, v0: &NodeIndex, v1: &ProxyNodeId, graph_1: &mut GraphProxy<'_>) {
225            push_state_0(&mut self.base_state_0, self.graph_0, v0, v1);
226            push_state_1(&mut self.base_state_1, graph_1, v1, v0);
227        }
228
229        pub fn pop(&mut self, v0: &NodeIndex, _v1: &ProxyNodeId, graph_1: &mut GraphProxy<'_>) -> Option<()> {
230            if let Some(&w) = self.base_state_0.core(v0) {
231                pop_state_0(&mut self.base_state_0, self.graph_0, v0);
232                pop_state_1(&mut self.base_state_1, graph_1, &w);
233            }
234            Some(())
235        }
236
237        pub fn feasible(&mut self, v_new: &NodeIndex, w_new: &ProxyNodeId, graph_1: &mut GraphProxy<'_>) -> Option<bool> {
238            trace!("feasible ids: {:?} {:?}", v_new, w_new);
239            let v = self.graph_0.get_node_ref(v_new);
240            let w = graph_1.get_node_ref(w_new)?;
241            trace!("feasible nodes: {:?} {:?}", v, w);
242            if !(self.vertex_comp)(v, w) {
243                trace!("nodes mismatch: {:?} {:?}", v, w);
244                Some(false)
245            } else {
246                trace!("vertex match: {:?} {:?}", v, w);
247                let mut term_in0_count = 0;
248                let mut term_out0_count = 0;
249                let mut rest0_count = 0;
250
251                {
252                    let mut matched_edge_set = HashSet::new();
253                    for edge_index in self.graph_0.in_edges(v_new) {
254                        let source_index = self.graph_0.get_source_index(&edge_index);
255                        if !self.inc_counters_match_edge_0(true, &mut term_in0_count, &mut term_out0_count, &mut rest0_count, v_new, &source_index, w_new, &edge_index, 
256                            &mut matched_edge_set, graph_1)? {
257                            return Some(false);
258                        }
259                    }
260                }
261                {
262                    let mut matched_edge_set = HashSet::new();
263                    for edge_index in self.graph_0.out_edges(v_new) {
264                        let target_index = self.graph_0.get_target_index(&edge_index);
265                        if !self.inc_counters_match_edge_0(false, &mut term_in0_count, &mut term_out0_count, &mut rest0_count, v_new, &target_index, w_new, &edge_index, 
266                            &mut matched_edge_set, graph_1)? {
267                            return Some(false);
268                        }
269                    }
270                }
271
272
273                let mut term_in1_count = 0;
274                let mut term_out1_count = 0;
275                let mut rest1_count = 0;
276                {
277                    let mut matched_edge_set = HashSet::new();
278                    for (edge_index, source_index, _rel) in graph_1.in_edges(w_new)? {
279                        if !self.inc_counters_match_edge_1(true, &mut term_in1_count, &mut term_out1_count, &mut rest1_count, w_new, &source_index, v_new, &edge_index, 
280                            &mut matched_edge_set)? {
281                            return Some(false);
282                        }
283                    }
284                }
285                {
286                    let mut matched_edge_set = HashSet::new();
287                    for (edge_index, target_index, _rel) in graph_1.out_edges(w_new)? {
288                        if !self.inc_counters_match_edge_1(false, &mut term_in1_count, &mut term_out1_count, &mut rest1_count, w_new, &target_index, v_new, &edge_index, 
289                            &mut matched_edge_set)? {
290                            return Some(false);
291                        }
292                    }
293                }
294                Some(term_in0_count <= term_in1_count && term_out0_count <= term_out1_count && rest0_count <= rest1_count)
295            }
296        }
297
298        fn inc_counters_match_edge_0(&mut self, is_inbound: bool, term_in: &mut i32, term_out: &mut i32, rest: &mut i32, v_new: &NodeIndex, v_adj: &NodeIndex, w_new: &ProxyNodeId, edge_index: &EdgeIndex, matched_edge_set: &mut HashSet<ProxyRelationshipId>, graph_1: &mut GraphProxy<'_>) -> Option<bool> {
299            let r0 = self.graph_0.get_relationship_ref(edge_index);
300            if self.base_state_0.in_core(v_adj) || v_new == v_adj {
301                let mut w = *w_new;
302                if v_adj != v_new {
303                    if let Some(ws) = self.base_state_0.core(v_adj) {
304                        w =  *ws;
305                    }
306                }
307
308                if is_inbound {
309                    if !self.edge_exists_1(&w, w_new, r0, matched_edge_set, graph_1)? {
310                        return Some(false);
311                    }
312                } else if !self.edge_exists_1(w_new, &w, r0, matched_edge_set, graph_1)? {
313                    return Some(false);
314                }
315            } else {
316                if  self.base_state_0.in_depth(v_adj) > 0 {
317                    *term_in += 1;
318                }
319                if  self.base_state_0.out_depth(v_adj) > 0 {
320                    *term_out += 1;
321                }
322                if  self.base_state_0.in_depth(v_adj) == 0 &&  self.base_state_0.out_depth(v_adj) == 0 {
323                    *rest += 1;
324                }
325            }
326            Some(true)
327        }
328
329        fn edge_exists_0(&mut self, source: &NodeIndex, target: &NodeIndex, r1: &Relationship, matched_edge_set: &mut HashSet<EdgeIndex>) -> Option<bool> {
330            for out_edge_index in self.graph_0.out_edges(source) {
331                let curr_target = self.graph_0.get_target_index(&out_edge_index);
332                if curr_target == *target && !matched_edge_set.contains(&out_edge_index) {
333                    let r = self.graph_0.get_relationship_ref(&out_edge_index);
334                    if (self.edge_comp)(r, r1) {
335                        matched_edge_set.insert(out_edge_index);
336                        return Some(true);
337                    }
338                }
339            }
340            Some(false)
341        }
342
343        fn edge_exists_1(&mut self, source: &ProxyNodeId, target: &ProxyNodeId, r0: &Relationship, matched_edge_set: &mut HashSet<ProxyRelationshipId>, graph_1: &mut GraphProxy<'_>) -> Option<bool> {
344            for (out_edge_index, curr_target, r) in graph_1.out_edges(source)? {
345                if curr_target == *target && !matched_edge_set.contains(&out_edge_index) && (self.edge_comp)(r0, &r){
346                    matched_edge_set.insert(out_edge_index);
347                    return Some(true);
348                }
349            }
350            Some(false)
351        }
352
353        fn inc_counters_match_edge_1(&self, _is_inbound: bool, term_in: &mut i32, term_out: &mut i32, rest: &mut i32, w_new: &ProxyNodeId, w_adj: &ProxyNodeId, _v_new: &NodeIndex, _edge_index: &ProxyRelationshipId, _matched_edge_set: &mut HashSet<EdgeIndex>) -> Option<bool> {
354            if self.base_state_1.in_core(w_adj) || w_new == w_adj {
355                
356            } else {
357                if self.base_state_1.in_depth(w_adj) > 0 {
358                    *term_in += 1;
359                }
360                if self.base_state_1.out_depth(w_adj) > 0 {
361                    *term_out += 1;
362                }
363                if self.base_state_1.in_depth(w_adj) == 0 && self.base_state_1.out_depth(w_adj) == 0 {
364                    *rest += 1;
365                }
366            }
367            Some(true)
368        }
369
370        pub fn possible_candidate_0(&self, v0: &NodeIndex) -> bool {
371            if self.base_state_0.term_both() && self.base_state_1.term_both() {
372                self.base_state_0.term_both_vertex(v0)
373            } else if self.base_state_0.term_out() && self.base_state_1.term_out() {
374                self.base_state_0.term_out_vertex(v0)
375            } else if self.base_state_0.term_in() && self.base_state_1.term_in() {
376                self.base_state_0.term_in_vertex(v0)
377            } else {
378                !self.base_state_0.in_core(v0)
379            }
380        }
381
382        pub fn possible_candidate_1(&self, v1: &ProxyNodeId) -> bool {
383            trace!("possible candidate: {:?}", v1);
384            if self.base_state_0.term_both() && self.base_state_1.term_both() {
385                self.base_state_1.term_both_vertex(v1)
386            } else if self.base_state_0.term_out() && self.base_state_1.term_out() {
387                self.base_state_1.term_out_vertex(v1)
388            } else if self.base_state_0.term_in() && self.base_state_1.term_in() {
389                self.base_state_1.term_in_vertex(v1)
390            } else {
391                !self.base_state_1.in_core(v1)
392            }
393        }
394
395        pub fn success(&self) -> bool {
396            self.base_state_0.count() == self.graph_0.nodes_len()
397        }
398
399        pub fn valid(&self) -> bool {
400            let term_set_0 = self.base_state_0.term_set();
401            let term_set_1 = self.base_state_1.term_set();
402            term_set_0.0 <= term_set_1.0 && term_set_0.1 <= term_set_1.1 && term_set_0.2 <= term_set_1.2
403        }
404
405        pub fn call_back<CALLBACK>(&mut self, callback: &mut CALLBACK, graph_1: &mut GraphProxy<'_>) -> Option<bool>
406        where CALLBACK: FnMut(&HashMap<NodeIndex, ProxyNodeId>, &HashMap<ProxyNodeId, NodeIndex>, &PropertyGraph, &mut GraphProxy<'_>) -> Option<bool>
407        {
408            callback(self.base_state_0.get_map(), self.base_state_1.get_map(), self.graph_0, graph_1)
409        }
410
411}
zawgl_core/matcher/vf2/state.rs

zawgl_core/matcher/vf2/
state.rs
