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

graph_simulation/algorithm/
hyper_simulation.rs
