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

graph_simulation/algorithm/
hyper_simulation.rs
