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};
5
6
7use serde::{Serialize, Deserialize};
8use std::fs::File;
9use std::io::{BufReader, BufWriter};
10use std::error::Error;
11
12
13use graph_base::interfaces::{edge::{DirectedHyperedge, Hyperedge}, graph::SingleId, hypergraph::{ContainedDirectedHyperedge, ContainedHyperedge, DirectedHypergraph, Hypergraph}, typed::{Type, Typed}};
14
15use crate::{algorithm::simulation, utils::logger::init_global_logger_once};
16use crate::utils::logger::TraceLog;
17
18pub trait LMatch {
19    type Edge;
20    // fn l_match(&'a self, e: &'a Self::Edge, e_prime: &'a Self::Edge) -> HashMap<&'a Self::Node, &'a HashSet<&'a Self::Node>>;
21    fn new() -> Self;
22    fn l_match_with_node_mut(&mut self, e: &Self::Edge, e_prime: &Self::Edge, u: usize) -> &HashSet<usize>;
23    fn l_match_with_node(&self, e: &Self::Edge, e_prime: &Self::Edge, u: usize) -> &HashSet<usize>;
24    fn dom(&self, e: &Self::Edge, e_prime: &Self::Edge) -> impl Iterator<Item = &usize>;
25}
26
27#[derive(Hash)]
28pub struct SematicCluster<'a, E: Hyperedge> {
29    id: usize,
30    hyperedges: Vec<&'a E>,
31}
32
33impl<'a, E: Hyperedge> SematicCluster<'a, E> {
34
35    pub fn new(id: usize, hyperedges: Vec<&'a E>) -> Self {
36        Self {
37            id,
38            hyperedges,
39        }
40    }
41
42    pub fn id(&self) -> usize {
43        self.id
44    }
45
46    pub fn hyperedges(&self) -> &Vec<&'a E> {
47        &self.hyperedges
48    }
49}
50
51pub trait Delta<'a> {
52    type Node;
53    type Edge: Hyperedge;
54    fn get_sematic_clusters(&'a self, u: &'a Self::Node, v: &'a Self::Node) -> &'a Vec<(SematicCluster<'a, Self::Edge>, SematicCluster<'a, Self::Edge>)>;
55}
56
57pub trait DMatch<'a> {
58    type Edge: Hyperedge;
59    // fn d_match_mut(&mut self, e: &SematicCluster<'a, Self::Edge>, e_prime: &SematicCluster<'a, Self::Edge>) -> &HashSet<(usize, usize)>;
60    fn d_match(&self, e: &SematicCluster<'a, Self::Edge>, e_prime: &SematicCluster<'a, Self::Edge>) -> &HashSet<(usize, usize)>;
61}
62
63pub trait LPredicate<'a>: Hypergraph<'a> {
64    fn l_predicate_node(&'a self, u: &'a Self::Node, v: &'a Self::Node) -> bool;
65    fn l_predicate_edge(&'a self, e: &'a Self::Edge, e_prime: &'a Self::Edge) -> bool;
66    fn l_predicate_set(&'a self, x: &HashSet<&'a Self::Node>, y: &HashSet<&'a Self::Node>) -> bool;
67}
68
69pub trait HyperSimulation<'a>: Hypergraph<'a> {
70    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>>;
71    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>>;
72    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>>;
73    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>>;
74    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>>;
75}
76
77// struct MultiWriter<W1: Write, W2: Write> {
78//     w1: W1,
79//     w2: W2,
80// }
81
82// impl<W1: Write, W2: Write> Write for MultiWriter<W1, W2> {
83//     fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
84//         self.w1.write_all(buf)?;
85//         self.w2.write_all(buf)?;
86//         Ok(buf.len())
87//     }
88//     fn flush(&mut self) -> io::Result<()> {
89//         self.w1.flush()?;
90//         self.w2.flush()
91//     }
92// }
93
94
95impl<'a, H> HyperSimulation<'a> for H 
96where H: Hypergraph<'a> + Typed<'a> + LPredicate<'a> + ContainedHyperedge<'a> {
97    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>> {
98        todo!()
99    }
100
101    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>> {
102        todo!()
103    }
104
105    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>> {
106        
107        // let log_file = File::create("hyper-simulation.log")
108        //     .expect("Failed to create log file");
109        // let multi_writer = MultiWriter {
110        //     w1: log_file,
111        //     w2: io::stdout(),
112        // };
113        
114        // env_logger::Builder::new()
115        //     .target(env_logger::Target::Pipe(Box::new(multi_writer)))
116        //     .init();
117
118        init_global_logger_once("hyper-simulation.log");
119
120        info!("Start Naive Hyper Simulation");
121
122        let self_contained_hyperedge = self.get_hyperedges_list();
123        let other_contained_hyperedge = other.get_hyperedges_list();
124
125        let mut simulation: HashMap<&Self::Node, HashSet<&Self::Node>> = self.nodes().map(|u| {
126            let res = other.nodes().filter(|v| {
127                if self.type_same(u, *v) {
128                    // For each e, compute the union of l_match(u) over all matching e_prime,
129                    // then take the intersection across all e.
130                    let mut l_match_intersection: Option<HashSet<usize>> = None;
131                    for e in self.contained_hyperedges(&self_contained_hyperedge, u) {
132                        let mut l_match_union: HashSet<usize> = HashSet::new();
133                        for e_prime in other.contained_hyperedges(&other_contained_hyperedge, v) {
134                            if self.l_predicate_edge(e, e_prime) {
135                                // let l_match = self.l_match(e, e_prime);
136                                let id_set = l_match.l_match_with_node(e, e_prime, u.id());
137                                l_match_union = l_match_union.union(&id_set).copied().collect();
138                            }
139                        }
140                        l_match_intersection = match l_match_intersection {
141                            Some(ref acc) => Some(acc.intersection(&l_match_union).copied().collect()),
142                            None => Some(l_match_union),
143                        };
144                    }
145                    if let Some(l_match_intersection) = l_match_intersection {
146                        if l_match_intersection.contains(&v.id()){
147                            return true;
148                        }
149                    }
150                }
151                false
152            }).collect();
153            (u, res)
154        }).collect();
155
156        info!("END Initial, sim: is ");
157        for (u, v_set) in &simulation {
158            info!("\tsim({}) = {:?}", u.id(), v_set.iter().map(|v| v.id()).collect::<Vec<_>>());
159        }
160        
161
162        let mut changed = true;
163        while changed {
164            changed = false;
165            for u in self.nodes() {
166                let mut need_delete = Vec::new();
167                for v in simulation.get(u).unwrap() {
168                    info!("Checking {} -> {}", u.id(), v.id());
169                    let mut _delete = true;
170                    for e in self.contained_hyperedges(&self_contained_hyperedge, u) {
171                        if !_delete {
172                            break;
173                        }
174                        for e_prime in other.contained_hyperedges(&other_contained_hyperedge, v) {
175                            if self.l_predicate_edge(e, e_prime) {
176                                if l_match.dom(e, e_prime).all(|u_prime| {
177                                    l_match.l_match_with_node(e, e_prime, u_prime.clone()).iter().map(|id| {other.get_node_by_id(*id)}).any(|v_prime| {
178                                        if let Some(v_prime) = v_prime {
179                                            return simulation.get(u).unwrap().contains(v_prime);
180                                        } else {
181                                            return false;
182                                        }
183                                    })
184                                }) {
185                                    info!("Keeping {} -> {}", u.id(), v.id());
186                                    _delete = false;
187                                    break;
188                                }
189                            }
190                        }
191                    }
192                    if _delete {
193                        info!("Deleting {} -> {}", u.id(), v.id());
194                        need_delete.push(v.clone());
195                    }
196                }
197                for v in need_delete {
198                    simulation.get_mut(u).unwrap().remove(v);
199                    changed = true;
200                }
201            }
202        }
203
204        simulation
205    }
206
207    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>> {
208        init_global_logger_once("hyper-simulation.log");
209
210        info!("Start Naive Hyper Simulation");
211
212        // let self_contained_hyperedge = self.get_hyperedges_list();
213        // let other_contained_hyperedge = other.get_hyperedges_list();
214
215        let mut l_predicate_edges: HashMap<(usize, usize), Vec<(&Self::Edge, &Self::Edge)>> = HashMap::new();
216        for e in self.hyperedges() {
217            for e_prime in other.hyperedges() {
218                if self.l_predicate_edge(e, e_prime) {
219                    for u in e.id_set() {
220                        for v in e_prime.id_set() {
221                            l_predicate_edges.entry((u, v)).or_default().push((e, e_prime));
222                        }
223                    }
224                }
225            }
226        }
227
228        let mut simulation: HashMap<&'a Self::Node, HashSet<&'a Self::Node>> = self.nodes().map(|u| {
229            let res = other.nodes().filter(|v| {
230                if self.type_same(u, *v) {
231                    if let Some(edge_pairs) = l_predicate_edges.get(&(u.id(), v.id())) {
232                        for (e, e_prime) in edge_pairs {
233                            let id_set = l_match.l_match_with_node(e, e_prime, u.id());
234                            if !id_set.contains(&v.id()) {
235                                return false;
236                            }
237                        }
238                        return true;
239                    } else {
240                        return true;
241                    }
242                }
243                false
244            }).collect();
245            (u, res)
246        }).collect();
247
248        info!("END Initial, sim: is ");
249        for (u, v_set) in &simulation {
250            info!("\tsim({}) = {:?}", u.id(), v_set.iter().map(|v| v.id()).collect::<Vec<_>>());
251        }
252        
253
254        let mut changed = true;
255        while changed {
256            changed = false;
257            for u in self.nodes() {
258                let mut need_delete = Vec::new();
259                for v in simulation.get(u).unwrap() {
260                    info!("Checking {} -> {}", u.id(), v.id());
261                    let mut _delete = false;
262
263                    if let Some(edge_pairs) = l_predicate_edges.get(&(u.id(), v.id())) {
264                        for (e, e_prime) in edge_pairs {
265                            if l_match.dom(e, e_prime).all(|u_prime| {
266                                l_match.l_match_with_node(e, e_prime, u_prime.clone()).iter().map(|id| {other.get_node_by_id(*id)}).any(|v_prime| {
267                                    if let Some(v_prime) = v_prime {
268                                        return simulation.get(u).unwrap().contains(v_prime);
269                                    } else {
270                                        return false;
271                                    }
272                                })
273                            }) {
274                                info!("Keeping {} -> {}", u.id(), v.id());
275                                _delete = true;
276                                break;
277                            }
278                        }
279                    }
280
281                    if _delete {
282                        info!("Deleting {} -> {}", u.id(), v.id());
283                        need_delete.push(v.clone());
284                    }
285                }
286
287                for v in need_delete {
288                    simulation.get_mut(u).unwrap().remove(v);
289                    changed = true;
290                }
291            }
292        }
293
294        simulation
295
296    }
297
298    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>> {
299        init_global_logger_once("hyper-simulation.log");
300        let mut hs_trace = HyperSimulationTrace::new();
301        let mut simulation: HashMap<&'a Self::Node, HashSet<&'a Self::Node>> = self.nodes().map(|u| {
302            let res = other.nodes().filter(|v| {
303                if self.type_same(u, *v) {
304                    let sematic_clusters = delta.get_sematic_clusters(u, v);
305                    for (cluster_u, cluster_v) in sematic_clusters {
306                        let d_match_set = d_match.d_match(cluster_u, cluster_v);
307                        if !d_match_set.contains(&(u.id(), v.id())) {
308                            // Add the trace that nodes (u, v) are deleted by the `sematic_clusters`
309                            hs_trace.add_base_event(cluster_u.id, d_match_set.clone());
310                            return false;
311                        }
312                    }
313                    return true;
314                }
315                false
316            }).collect();
317            (u, res)
318        }).collect();
319
320        info!("END Initial, sim: is ");
321        for (u, v_set) in &simulation {
322            info!("\tsim({}) = {:?}", u.id(), v_set.iter().map(|v| v.id()).collect::<Vec<_>>());
323        }
324
325        let mut simulation_by_id: HashSet<(usize, usize)> = simulation.iter().flat_map(|(u, v_set)| {
326            v_set.iter().map(move |v| (u.id(), v.id()))
327        }).collect();
328
329        let mut changed = true;
330        while changed {
331            changed = false;
332            for u in self.nodes() {
333                let mut need_delete = Vec::new();
334                for v in simulation.get(u).unwrap() {
335                    info!("Checking {} -> {}", u.id(), v.id());
336                    let mut _delete = false;
337
338                    let sematic_clusters = delta.get_sematic_clusters(u, v);
339                    for (cluster_u, cluster_v) in sematic_clusters {
340                        let d_relation = d_match.d_match(cluster_u, cluster_v);
341                        // 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
342                        if !d_relation.is_subset(&simulation_by_id) {
343                            info!("Deleting {} -> {}", u.id(), v.id());
344                            // Add the trace that nodes (u, v) are deleted by the `sematic_clusters`
345                            let uncoverd: HashSet<(usize, usize)> = d_relation.difference(&simulation_by_id).copied().collect();
346                            hs_trace.add_derivation_event(cluster_u.id, uncoverd);
347                            _delete = true;
348                            break;
349                        }
350                    }
351
352                    if _delete {
353                        need_delete.push(v.clone());
354                    }
355                }
356
357                for v in need_delete {
358                    simulation.get_mut(u).unwrap().remove(v);
359                    simulation_by_id.remove(&(u.id(), v.id()));
360                    changed = true;
361                }
362            }
363        }
364
365        hs_trace.store_trace_file("hyper_simulation.trace").unwrap();
366
367        return simulation;
368    }
369}
370
371#[derive(Serialize, Deserialize, Debug, PartialEq)]
372pub struct HyperSimulationTrace {
373    events: Vec<HSEvent>
374}
375
376impl HyperSimulationTrace {
377    fn new() -> Self {
378        HyperSimulationTrace {
379            events: Vec::new()
380        }
381    }
382
383    fn add_base_event(&mut self, sc_id: usize, d_match: HashSet<(usize, usize)>) {
384        let event = HSEvent::Base(sc_id, d_match);
385        self.events.push(event);
386    }
387    fn add_derivation_event(&mut self, sc_id: usize, uncoverd: HashSet<(usize, usize)>) {
388        let event = HSEvent::Derivation(sc_id, uncoverd);
389        self.events.push(event);
390    }
391}
392
393impl IntoIterator for HyperSimulationTrace {
394    type Item = HSEvent;
395    type IntoIter = std::vec::IntoIter<HSEvent>;
396    
397    fn into_iter(self) -> Self::IntoIter {
398        self.events.into_iter()
399    }
400}
401
402impl<'a> IntoIterator for &'a HyperSimulationTrace {
403    type Item = &'a HSEvent;
404    type IntoIter = std::slice::Iter<'a, HSEvent>;
405    
406    fn into_iter(self) -> Self::IntoIter {
407        self.events.iter()
408    }
409}
410
411impl TraceLog for HyperSimulationTrace {
412    fn store_trace_file(self, filename: &'static str) -> Result<(), Box<dyn Error>> {
413        // use bincode to save the HyperSimulationTrace.
414        let file = File::create(filename)?;
415        let mut writer = BufWriter::new(file);
416        bincode::serialize_into(&mut writer, &self)?;
417        Ok(())
418    }
419    
420    fn get_trace(filename: &'static str) -> Result<Self, Box<dyn Error>> {
421        let file = File::open(filename)?;
422        let mut reader = BufReader::new(file);
423        let file_decoded: HyperSimulationTrace = bincode::deserialize_from(&mut reader)?;
424        Ok(file_decoded)
425    }
426}
427
428#[derive(Serialize, Deserialize, Debug, PartialEq)]
429pub enum HSEvent {
430    Base(usize, HashSet<(usize, usize)>), // current D-Match
431    Derivation(usize, HashSet<(usize, usize)>) // D-Match \ Sim
432}
graph_simulation/algorithm/hyper_simulation.rs

graph_simulation/algorithm/
hyper_simulation.rs
