graph_simulation/algorithm/
hyper_simulation.rs

1use std::collections::{HashMap, HashSet, VecDeque};
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    fn get_hyper_simulation_effect(&'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    fn get_hyper_simulation_strict(&'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>>;
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("logs/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, raw-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("logs/hyper_simulation.trace").unwrap();
367
368        return simulation;
369    }
370
371    fn get_hyper_simulation_strict(&'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>> {
372        init_global_logger_once("logs/hyper-simulation.log");
373        let mut hs_trace = HyperSimulationTrace::new();
374        let mut simulation: HashMap<&'a Self::Node, HashSet<&'a Self::Node>> = self.nodes().map(|u| {
375            let res = other.nodes().filter(|v| {
376                if self.type_same(u, *v) {
377                    let sematic_clusters = delta.get_sematic_clusters(u, v);
378                    // Highlight!
379                    if sematic_clusters.len() == 0 {
380                        info!("Deleting {} -> {} because no sematic cluster", u.id(), v.id());
381                        return false;
382                    }
383                    info!("Checking {} -> {}, sematic clusters size: {}", u.id(), v.id(), sematic_clusters.len());
384                    for (cluster_u, cluster_v) in sematic_clusters {
385                        let d_match_set = d_match.d_match(cluster_u, cluster_v);
386                        if !d_match_set.contains(&(u.id(), v.id())) {
387                            // Add the trace that nodes (u, v) are deleted by the `sematic_clusters`
388                            hs_trace.add_base_event(cluster_u.id, d_match_set.clone());
389                            return false;
390                        }
391                    }
392                    return true;
393                }
394                false
395            }).collect();
396            (u, res)
397        }).collect();
398
399        info!("END Initial, raw-sim: is ");
400        for (u, v_set) in &simulation {
401            info!("\tsim({}) = {:?}", u.id(), v_set.iter().map(|v| v.id()).collect::<Vec<_>>());
402        }
403
404        let mut simulation_by_id: HashSet<(usize, usize)> = simulation.iter().flat_map(|(u, v_set)| {
405            v_set.iter().map(move |v| (u.id(), v.id()))
406        }).collect();
407
408        let mut changed = true;
409        while changed {
410            changed = false;
411            for u in self.nodes() {
412                let mut need_delete = Vec::new();
413                for v in simulation.get(u).unwrap() {
414                    info!("Checking {} -> {}", u.id(), v.id());
415                    let mut _delete = false;
416
417                    let sematic_clusters = delta.get_sematic_clusters(u, v);
418                    for (cluster_u, cluster_v) in sematic_clusters {
419                        let d_relation = d_match.d_match(cluster_u, cluster_v);
420                        // 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
421                        if !d_relation.is_subset(&simulation_by_id) {
422                            info!("Deleting {} -> {}", u.id(), v.id());
423                            // Add the trace that nodes (u, v) are deleted by the `sematic_clusters`
424                            let uncoverd: HashSet<(usize, usize)> = d_relation.difference(&simulation_by_id).copied().collect();
425                            hs_trace.add_derivation_event(cluster_u.id, uncoverd);
426                            _delete = true;
427                            break;
428                        }
429                    }
430
431                    if _delete {
432                        need_delete.push(v.clone());
433                    }
434                }
435
436                for v in need_delete {
437                    simulation.get_mut(u).unwrap().remove(v);
438                    simulation_by_id.remove(&(u.id(), v.id()));
439                    changed = true;
440                }
441            }
442        }
443
444        hs_trace.store_trace_file("logs/hyper_simulation.trace").unwrap();
445
446        return simulation;
447    }
448
449    fn get_hyper_simulation_effect(
450        &'a self,
451        other: &'a Self,
452        delta: &'a impl Delta<'a, Node = Self::Node, Edge = Self::Edge>,
453        d_match: &impl DMatch<'a, Edge = Self::Edge>,
454    ) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
455        // 建立 ID 到节点的映射，方便最后构造返回结果
456        let mut id_to_u: HashMap<usize, &'a Self::Node> = HashMap::new();
457        let mut id_to_v: HashMap<usize, &'a Self::Node> = HashMap::new();
458
459        // 存储节点对与其对应的所有的 Semantic Clusters (HC) 及 D-match 结果
460        let mut hc_map: HashMap<(usize, usize), Vec<((usize, usize), HashSet<(usize, usize)>)>> = HashMap::new();
461        
462        // Pi: 当前满足 Hyper Simulation 条件的 (u.id(), v.id()) 集合
463        let mut pi: HashSet<(usize, usize)> = HashSet::new();
464
465        // ==========================================
466        // Phase 1: Declarative Initialization
467        // ==========================================
468        
469        // 1. 初始化 Pi 并获取 HC 和 D-match
470        for u in self.nodes() {
471            id_to_u.insert(u.id(), u);
472            for v in other.nodes() {
473                id_to_v.insert(v.id(), v);
474
475                if self.type_same(u, v) {
476                    let sematic_clusters = delta.get_sematic_clusters(u, v);
477                    let mut valid = true;
478                    let mut local_clusters = Vec::new();
479
480                    for (cluster_u, cluster_v) in sematic_clusters {
481                        let cu_id = cluster_u.id;
482                        let cv_id = cluster_v.id;
483                        let d_match_set = d_match.d_match(cluster_u, cluster_v);
484
485                        // 条件 2.a: (u, v) 必须在 D-match 中
486                        if !d_match_set.contains(&(u.id(), v.id())) {
487                            valid = false;
488                            break; // 只要有一个 cluster 失败，(u,v) 就不可能在 Pi 中
489                        }
490                        local_clusters.push(((cu_id, cv_id), d_match_set.clone()));
491                    }
492
493                    if valid {
494                        pi.insert((u.id(), v.id()));
495                        hc_map.insert((u.id(), v.id()), local_clusters);
496                    }
497                }
498            }
499        }
500
501        // A_cluster 对应的 D-match 缓存，避免重复计算
502        let mut a_cluster_d_match: HashMap<(usize, usize), HashSet<(usize, usize)>> = HashMap::new();
503        
504        // 依赖索引构建:
505        // D_cluster[(Cu, Cv)] -> { (u, v) \in Pi } 
506        let mut d_cluster: HashMap<(usize, usize), HashSet<(usize, usize)>> = HashMap::new();
507        // D_pair[(u', v')] -> { (Cu, Cv) \in A_cluster }
508        let mut d_pair: HashMap<(usize, usize), HashSet<(usize, usize)>> = HashMap::new();
509
510        for (&(u_id, v_id), clusters) in &hc_map {
511            for ((cu_id, cv_id), d_match_set) in clusters {
512                let c_pair = (*cu_id, *cv_id);
513                
514                // 填充 D_cluster
515                d_cluster.entry(c_pair).or_default().insert((u_id, v_id));
516
517                // 如果这是第一次遇到这个簇对，填充 D_pair
518                if !a_cluster_d_match.contains_key(&c_pair) {
519                    a_cluster_d_match.insert(c_pair, d_match_set.clone());
520
521                    for &(up_id, vp_id) in d_match_set {
522                        d_pair.entry((up_id, vp_id)).or_default().insert(c_pair);
523                    }
524                }
525            }
526        }
527
528        // 2. 初始化 V_C (Valid Clusters)
529        let mut v_c: HashSet<(usize, usize)> = HashSet::new();
530        for (c_pair, d_match_set) in &a_cluster_d_match {
531            // 条件 2.b: D-match 的所有元素都必须在当前的 Pi 中
532            if d_match_set.is_subset(&pi) {
533                v_c.insert(*c_pair);
534            }
535        }
536
537        // 3. 找出失效的 (u, v) 加入队列 Q
538        let mut q: VecDeque<(usize, usize)> = VecDeque::new();
539        let mut pi_retained = pi.clone();
540
541        for &(u_id, v_id) in &pi {
542            let mut all_in_vc = true;
543            if let Some(clusters) = hc_map.get(&(u_id, v_id)) {
544                for (c_pair, _) in clusters {
545                    if !v_c.contains(c_pair) {
546                        all_in_vc = false;
547                        break;
548                    }
549                }
550            }
551
552            if !all_in_vc {
553                q.push_back((u_id, v_id));      // 加入 Worklist
554                pi_retained.remove(&(u_id, v_id)); // Pi = Pi \ Q
555            }
556        }
557        pi = pi_retained;
558
559        // ==========================================
560        // Phase 2: Cascade deletions via the queue
561        // ==========================================
562        while let Some((up_id, vp_id)) = q.pop_front() {
563            // 获取所有依赖于已删除节点对 (u', v') 的簇对 (Cu, Cv)
564            if let Some(dependent_clusters) = d_pair.get(&(up_id, vp_id)) {
565                for c_pair in dependent_clusters {
566                    // 如果簇对仍然被认为是有效的，现在它失效了
567                    if v_c.contains(c_pair) {
568                        v_c.remove(c_pair); // V_c = V_c \ {(Cu, Cv)}
569
570                        // 级联使依赖这个失效簇对的 (u, v) 失效
571                        if let Some(dependent_node_pairs) = d_cluster.get(c_pair) {
572                            for node_pair in dependent_node_pairs {
573                                if pi.contains(node_pair) {
574                                    pi.remove(node_pair);
575                                    q.push_back(*node_pair);
576                                }
577                            }
578                        }
579                    }
580                }
581            }
582        }
583
584        // ==========================================
585        // Phase 3: Construct Output
586        // ==========================================
587        // 将基于 ID 的关系还原为引用的 HashMap
588        let mut result: HashMap<&'a Self::Node, HashSet<&'a Self::Node>> = 
589            self.nodes().map(|u| (u, HashSet::new())).collect();
590
591        for (u_id, v_id) in pi {
592            // 由于我们事先在字典中存过映射，这里可以安全取值
593            let u_node = id_to_u[&u_id];
594            let v_node = id_to_v[&v_id];
595            if let Some(set) = result.get_mut(u_node) {
596                set.insert(v_node);
597            }
598        }
599
600        result
601    }
602}
603
604#[derive(Serialize, Deserialize, Debug, PartialEq)]
605pub struct HyperSimulationTrace {
606    events: Vec<HSEvent>
607}
608
609impl HyperSimulationTrace {
610    fn new() -> Self {
611        HyperSimulationTrace {
612            events: Vec::new()
613        }
614    }
615
616    fn add_base_event(&mut self, sc_id: usize, d_match: HashSet<(usize, usize)>) {
617        let event = HSEvent::Base(sc_id, d_match);
618        self.events.push(event);
619    }
620    fn add_derivation_event(&mut self, sc_id: usize, uncoverd: HashSet<(usize, usize)>) {
621        let event = HSEvent::Derivation(sc_id, uncoverd);
622        self.events.push(event);
623    }
624}
625
626impl IntoIterator for HyperSimulationTrace {
627    type Item = HSEvent;
628    type IntoIter = std::vec::IntoIter<HSEvent>;
629    
630    fn into_iter(self) -> Self::IntoIter {
631        self.events.into_iter()
632    }
633}
634
635impl<'a> IntoIterator for &'a HyperSimulationTrace {
636    type Item = &'a HSEvent;
637    type IntoIter = std::slice::Iter<'a, HSEvent>;
638    
639    fn into_iter(self) -> Self::IntoIter {
640        self.events.iter()
641    }
642}
643
644impl TraceLog for HyperSimulationTrace {
645    fn store_trace_file(self, filename: &'static str) -> Result<(), Box<dyn Error>> {
646        // use bincode to save the HyperSimulationTrace.
647        let file = File::create(filename)?;
648        let mut writer = BufWriter::new(file);
649        bincode::serialize_into(&mut writer, &self)?;
650        Ok(())
651    }
652    
653    fn get_trace(filename: &'static str) -> Result<Self, Box<dyn Error>> {
654        let file = File::open(filename)?;
655        let mut reader = BufReader::new(file);
656        let file_decoded: HyperSimulationTrace = bincode::deserialize_from(&mut reader)?;
657        Ok(file_decoded)
658    }
659}
660
661#[derive(Serialize, Deserialize, Debug, PartialEq)]
662pub enum HSEvent {
663    Base(usize, HashSet<(usize, usize)>), // current D-Match
664    Derivation(usize, HashSet<(usize, usize)>) // D-Match \ Sim
665}
graph_simulation/algorithm/hyper_simulation.rs

graph_simulation/algorithm/
hyper_simulation.rs
