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

graph_simulation/algorithm/
hyper_simulation.rs
