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

graph_simulation/algorithm/
hyper_simulation.rs
