graph_simulation/algorithm/
hyper_simulation.rs

1use std::collections::{HashMap, HashSet};
2use log::{info, warn};
3// use std::fs::File;
4// use std::io::{self, Write};
5use crate::{algorithm::simulation, utils::logger::init_global_logger_once};
6
7use graph_base::interfaces::{edge::{DirectedHyperedge, Hyperedge}, graph::SingleId, hypergraph::{ContainedDirectedHyperedge, ContainedHyperedge, DirectedHypergraph, Hypergraph}, typed::{Type, Typed}};
8
9pub trait LMatch {
10    type Edge;
11    // fn l_match(&'a self, e: &'a Self::Edge, e_prime: &'a Self::Edge) -> HashMap<&'a Self::Node, &'a HashSet<&'a Self::Node>>;
12    fn new() -> Self;
13    fn l_match_with_node_mut(&mut self, e: &Self::Edge, e_prime: &Self::Edge, u: usize) -> &HashSet<usize>;
14    fn l_match_with_node(&self, e: &Self::Edge, e_prime: &Self::Edge, u: usize) -> &HashSet<usize>;
15    fn dom(&self, e: &Self::Edge, e_prime: &Self::Edge) -> impl Iterator<Item = &usize>;
16}
17
18pub struct SematicCluster<'a, E: Hyperedge> {
19    id: usize,
20    hyperedges: Vec<&'a E>,
21}
22
23impl<'a, E: Hyperedge> SematicCluster<'a, E> {
24    pub fn id(&self) -> usize {
25        self.id
26    }
27
28    pub fn hyperedges(&self) -> &Vec<&'a E> {
29        &self.hyperedges
30    }
31}
32
33pub trait Delta<'a> {
34    type Node;
35    type Edge: Hyperedge;
36    fn get_sematic_clusters(&self, u: &'a Self::Node, v: &'a Self::Node) -> &'a Vec<(SematicCluster<'a, Self::Edge>, SematicCluster<'a, Self::Edge>)>;
37}
38
39pub trait DMatch<'a> {
40    type Edge: Hyperedge;
41    fn d_match_mut(&mut self, e: &SematicCluster<'a, Self::Edge>, e_prime: &SematicCluster<'a, Self::Edge>) -> &HashSet<(usize, usize)>;
42    fn d_match(&self, e: &SematicCluster<'a, Self::Edge>, e_prime: &SematicCluster<'a, Self::Edge>) -> &HashSet<(usize, usize)>;
43}
44
45pub trait LPredicate<'a>: Hypergraph<'a> {
46    fn l_predicate_node(&'a self, u: &'a Self::Node, v: &'a Self::Node) -> bool;
47    fn l_predicate_edge(&'a self, e: &'a Self::Edge, e_prime: &'a Self::Edge) -> bool;
48    fn l_predicate_set(&'a self, x: &HashSet<&'a Self::Node>, y: &HashSet<&'a Self::Node>) -> bool;
49}
50
51pub trait HyperSimulation<'a>: Hypergraph<'a> {
52    fn get_simulation_fixpoint(&'a self, other: &'a Self, l_match: &mut impl LMatch<Edge = Self::Edge>) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
53    fn get_simulation_recursive(&'a self, other: &'a Self, l_match: &mut impl LMatch<Edge = Self::Edge>) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
54    fn get_simulation_naive(&'a self, other: &'a Self, l_match: &mut impl LMatch<Edge = Self::Edge>) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
55    fn get_soft_simulation_naive(&'a self, other: &'a Self, l_match: &mut impl LMatch<Edge = Self::Edge>) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
56    fn get_hyper_simulation_naive(&'a self, other: &'a Self, delta: &impl Delta<'a, Node = Self::Node, Edge = Self::Edge>, d_match: &mut impl DMatch<'a, Edge = Self::Edge>) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
57}
58
59// struct MultiWriter<W1: Write, W2: Write> {
60//     w1: W1,
61//     w2: W2,
62// }
63
64// impl<W1: Write, W2: Write> Write for MultiWriter<W1, W2> {
65//     fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
66//         self.w1.write_all(buf)?;
67//         self.w2.write_all(buf)?;
68//         Ok(buf.len())
69//     }
70//     fn flush(&mut self) -> io::Result<()> {
71//         self.w1.flush()?;
72//         self.w2.flush()
73//     }
74// }
75
76
77impl<'a, H> HyperSimulation<'a> for H 
78where H: Hypergraph<'a> + Typed<'a> + LPredicate<'a> + ContainedHyperedge<'a> {
79    fn get_simulation_fixpoint(&'a self, other: &'a Self, l_match: &mut impl LMatch<Edge = Self::Edge>) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
80        todo!()
81    }
82
83    fn get_simulation_recursive(&'a self, other: &'a Self, l_match: &mut impl LMatch<Edge = Self::Edge>) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
84        todo!()
85    }
86
87    fn get_simulation_naive(&'a self, other: &'a Self, l_match: &mut impl LMatch<Edge = Self::Edge>) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
88        
89        // let log_file = File::create("hyper-simulation.log")
90        //     .expect("Failed to create log file");
91        // let multi_writer = MultiWriter {
92        //     w1: log_file,
93        //     w2: io::stdout(),
94        // };
95        
96        // env_logger::Builder::new()
97        //     .target(env_logger::Target::Pipe(Box::new(multi_writer)))
98        //     .init();
99
100        init_global_logger_once("hyper-simulation.log");
101
102        info!("Start Naive Hyper Simulation");
103
104        let self_contained_hyperedge = self.get_hyperedges_list();
105        let other_contained_hyperedge = other.get_hyperedges_list();
106
107        let mut simulation: HashMap<&Self::Node, HashSet<&Self::Node>> = self.nodes().map(|u| {
108            let res = other.nodes().filter(|v| {
109                if self.type_same(u, *v) {
110                    // For each e, compute the union of l_match(u) over all matching e_prime,
111                    // then take the intersection across all e.
112                    let mut l_match_intersection: Option<HashSet<usize>> = None;
113                    for e in self.contained_hyperedges(&self_contained_hyperedge, u) {
114                        let mut l_match_union: HashSet<usize> = HashSet::new();
115                        for e_prime in other.contained_hyperedges(&other_contained_hyperedge, v) {
116                            if self.l_predicate_edge(e, e_prime) {
117                                // let l_match = self.l_match(e, e_prime);
118                                let id_set = l_match.l_match_with_node_mut(e, e_prime, u.id());
119                                l_match_union = l_match_union.union(&id_set).copied().collect();
120                            }
121                        }
122                        l_match_intersection = match l_match_intersection {
123                            Some(ref acc) => Some(acc.intersection(&l_match_union).copied().collect()),
124                            None => Some(l_match_union),
125                        };
126                    }
127                    if let Some(l_match_intersection) = l_match_intersection {
128                        if l_match_intersection.contains(&v.id()){
129                            return true;
130                        }
131                    }
132                }
133                false
134            }).collect();
135            (u, res)
136        }).collect();
137
138        info!("END Initial, sim: is ");
139        for (u, v_set) in &simulation {
140            info!("\tsim({}) = {:?}", u.id(), v_set.iter().map(|v| v.id()).collect::<Vec<_>>());
141        }
142        
143
144        let mut changed = true;
145        while changed {
146            changed = false;
147            for u in self.nodes() {
148                let mut need_delete = Vec::new();
149                for v in simulation.get(u).unwrap() {
150                    info!("Checking {} -> {}", u.id(), v.id());
151                    let mut _delete = true;
152                    for e in self.contained_hyperedges(&self_contained_hyperedge, u) {
153                        if !_delete {
154                            break;
155                        }
156                        for e_prime in other.contained_hyperedges(&other_contained_hyperedge, v) {
157                            if self.l_predicate_edge(e, e_prime) {
158                                if l_match.dom(e, e_prime).all(|u_prime| {
159                                    l_match.l_match_with_node(e, e_prime, u_prime.clone()).iter().map(|id| {other.get_node_by_id(*id)}).any(|v_prime| {
160                                        if let Some(v_prime) = v_prime {
161                                            return simulation.get(u).unwrap().contains(v_prime);
162                                        } else {
163                                            return false;
164                                        }
165                                    })
166                                }) {
167                                    info!("Keeping {} -> {}", u.id(), v.id());
168                                    _delete = false;
169                                    break;
170                                }
171                            }
172                        }
173                    }
174                    if _delete {
175                        info!("Deleting {} -> {}", u.id(), v.id());
176                        need_delete.push(v.clone());
177                    }
178                }
179                for v in need_delete {
180                    simulation.get_mut(u).unwrap().remove(v);
181                    changed = true;
182                }
183            }
184        }
185
186        simulation
187    }
188
189    fn get_soft_simulation_naive(&'a self, other: &'a Self, l_match: &mut impl LMatch<Edge = Self::Edge>) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
190        init_global_logger_once("hyper-simulation.log");
191
192        info!("Start Naive Hyper Simulation");
193
194        // let self_contained_hyperedge = self.get_hyperedges_list();
195        // let other_contained_hyperedge = other.get_hyperedges_list();
196
197        let mut l_predicate_edges: HashMap<(usize, usize), Vec<(&Self::Edge, &Self::Edge)>> = HashMap::new();
198        for e in self.hyperedges() {
199            for e_prime in other.hyperedges() {
200                if self.l_predicate_edge(e, e_prime) {
201                    for u in e.id_set() {
202                        for v in e_prime.id_set() {
203                            l_predicate_edges.entry((u, v)).or_default().push((e, e_prime));
204                        }
205                    }
206                }
207            }
208        }
209
210        let mut simulation: HashMap<&'a Self::Node, HashSet<&'a Self::Node>> = self.nodes().map(|u| {
211            let res = other.nodes().filter(|v| {
212                if self.type_same(u, *v) {
213                    if let Some(edge_pairs) = l_predicate_edges.get(&(u.id(), v.id())) {
214                        for (e, e_prime) in edge_pairs {
215                            let id_set = l_match.l_match_with_node(e, e_prime, u.id());
216                            if !id_set.contains(&v.id()) {
217                                return false;
218                            }
219                        }
220                        return true;
221                    } else {
222                        return true;
223                    }
224                }
225                false
226            }).collect();
227            (u, res)
228        }).collect();
229
230        info!("END Initial, sim: is ");
231        for (u, v_set) in &simulation {
232            info!("\tsim({}) = {:?}", u.id(), v_set.iter().map(|v| v.id()).collect::<Vec<_>>());
233        }
234        
235
236        let mut changed = true;
237        while changed {
238            changed = false;
239            for u in self.nodes() {
240                let mut need_delete = Vec::new();
241                for v in simulation.get(u).unwrap() {
242                    info!("Checking {} -> {}", u.id(), v.id());
243                    let mut _delete = false;
244
245                    if let Some(edge_pairs) = l_predicate_edges.get(&(u.id(), v.id())) {
246                        for (e, e_prime) in edge_pairs {
247                            if l_match.dom(e, e_prime).all(|u_prime| {
248                                l_match.l_match_with_node(e, e_prime, u_prime.clone()).iter().map(|id| {other.get_node_by_id(*id)}).any(|v_prime| {
249                                    if let Some(v_prime) = v_prime {
250                                        return simulation.get(u).unwrap().contains(v_prime);
251                                    } else {
252                                        return false;
253                                    }
254                                })
255                            }) {
256                                info!("Keeping {} -> {}", u.id(), v.id());
257                                _delete = true;
258                                break;
259                            }
260                        }
261                    }
262
263                    if _delete {
264                        info!("Deleting {} -> {}", u.id(), v.id());
265                        need_delete.push(v.clone());
266                    }
267                }
268
269                for v in need_delete {
270                    simulation.get_mut(u).unwrap().remove(v);
271                    changed = true;
272                }
273            }
274        }
275
276        simulation
277
278    }
279
280    fn get_hyper_simulation_naive(&'a self, other: &'a Self, delta: &impl Delta<'a, Node = Self::Node, Edge = Self::Edge>, d_match: &mut impl DMatch<'a, Edge = Self::Edge>) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
281        init_global_logger_once("hyper-simulation.log");
282
283        let mut simulation: HashMap<&'a Self::Node, HashSet<&'a Self::Node>> = self.nodes().map(|u| {
284            let res = other.nodes().filter(|v| {
285                if self.type_same(u, *v) {
286                    let sematic_clusters = delta.get_sematic_clusters(u, v);
287                    for (cluster_u, cluster_v) in sematic_clusters {
288                        let d_match_set = d_match.d_match_mut(cluster_u, cluster_v);
289                        if !d_match_set.contains(&(u.id(), v.id())) {
290                            return false;
291                        }
292                    }
293                    return true;
294                }
295                false
296            }).collect();
297            (u, res)
298        }).collect();
299
300        info!("END Initial, sim: is ");
301        for (u, v_set) in &simulation {
302            info!("\tsim({}) = {:?}", u.id(), v_set.iter().map(|v| v.id()).collect::<Vec<_>>());
303        }
304
305        let mut simulation_by_id: HashSet<(usize, usize)> = simulation.iter().flat_map(|(u, v_set)| {
306            v_set.iter().map(move |v| (u.id(), v.id()))
307        }).collect();
308
309        let mut changed = true;
310        while changed {
311            changed = false;
312            for u in self.nodes() {
313                let mut need_delete = Vec::new();
314                for v in simulation.get(u).unwrap() {
315                    info!("Checking {} -> {}", u.id(), v.id());
316                    let mut _delete = false;
317
318                    let sematic_clusters = delta.get_sematic_clusters(u, v);
319                    for (cluster_u, cluster_v) in sematic_clusters {
320                        let d_relation = d_match.d_match(cluster_u, cluster_v);
321                        // Check if for all (u_id, v_id) in d_relation, (u_id, v_id) is in simulation, i.e., d_relation is a subset of simulation_by_id
322                        if !d_relation.is_subset(&simulation_by_id) {
323                            info!("Keeping {} -> {}", u.id(), v.id());
324                            _delete = true;
325                            break;
326                        }
327                    }
328
329                    if _delete {
330                        info!("Deleting {} -> {}", u.id(), v.id());
331                        need_delete.push(v.clone());
332                    }
333                }
334
335                for v in need_delete {
336                    simulation.get_mut(u).unwrap().remove(v);
337                    simulation_by_id.remove(&(u.id(), v.id()));
338                    changed = true;
339                }
340            }
341        }
342
343        return simulation;
344    }
345}
graph_simulation/algorithm/hyper_simulation.rs

graph_simulation/algorithm/
hyper_simulation.rs
