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
456        init_global_logger_once("logs/hyper-simulation.log");
457
458        // 建立 ID 到节点的映射，方便最后构造返回结果
459        let mut id_to_u: HashMap<usize, &'a Self::Node> = HashMap::new();
460        let mut id_to_v: HashMap<usize, &'a Self::Node> = HashMap::new();
461
462        // 存储节点对与其对应的所有的 Semantic Clusters (HC) 及 D-match 结果
463        let mut hc_map: HashMap<(usize, usize), Vec<((usize, usize), HashSet<(usize, usize)>)>> = HashMap::new();
464        
465        // Pi: 当前满足 Hyper Simulation 条件的 (u.id(), v.id()) 集合
466        let mut pi: HashSet<(usize, usize)> = HashSet::new();
467
468        // ==========================================
469        // Phase 1: Declarative Initialization
470        // ==========================================
471        
472        // 1. 初始化 Pi 并获取 HC 和 D-match
473        for u in self.nodes() {
474            id_to_u.insert(u.id(), u);
475            for v in other.nodes() {
476                id_to_v.insert(v.id(), v);
477
478                if self.type_same(u, v) {
479                    let sematic_clusters = delta.get_sematic_clusters(u, v);
480                    let mut valid = true;
481                    let mut local_clusters = Vec::new();
482
483                    for (cluster_u, cluster_v) in sematic_clusters {
484                        let cu_id = cluster_u.id;
485                        let cv_id = cluster_v.id;
486                        let d_match_set = d_match.d_match(cluster_u, cluster_v);
487
488                        // 条件 2.a: (u, v) 必须在 D-match 中
489                        if !d_match_set.contains(&(u.id(), v.id())) {
490                            valid = false;
491                            break; // 只要有一个 cluster 失败，(u,v) 就不可能在 Pi 中
492                        }
493                        local_clusters.push(((cu_id, cv_id), d_match_set.clone()));
494                    }
495
496                    if valid {
497                        pi.insert((u.id(), v.id()));
498                        hc_map.insert((u.id(), v.id()), local_clusters);
499                    }
500                }
501            }
502        }
503
504        // A_cluster 对应的 D-match 缓存，避免重复计算
505        let mut a_cluster_d_match: HashMap<(usize, usize), HashSet<(usize, usize)>> = HashMap::new();
506        
507        // 依赖索引构建:
508        // D_cluster[(Cu, Cv)] -> { (u, v) \in Pi } 
509        let mut d_cluster: HashMap<(usize, usize), HashSet<(usize, usize)>> = HashMap::new();
510        // D_pair[(u', v')] -> { (Cu, Cv) \in A_cluster }
511        let mut d_pair: HashMap<(usize, usize), HashSet<(usize, usize)>> = HashMap::new();
512
513        for (&(u_id, v_id), clusters) in &hc_map {
514            for ((cu_id, cv_id), d_match_set) in clusters {
515                let c_pair = (*cu_id, *cv_id);
516                
517                // 填充 D_cluster
518                d_cluster.entry(c_pair).or_default().insert((u_id, v_id));
519
520                // 如果这是第一次遇到这个簇对，填充 D_pair
521                if !a_cluster_d_match.contains_key(&c_pair) {
522                    a_cluster_d_match.insert(c_pair, d_match_set.clone());
523
524                    for &(up_id, vp_id) in d_match_set {
525                        d_pair.entry((up_id, vp_id)).or_default().insert(c_pair);
526                    }
527                }
528            }
529        }
530
531        info!("1. 初始化 Pi 并获取 HC 和 D-match");
532
533        // 2. 初始化 V_C (Valid Clusters)
534        let mut v_c: HashSet<(usize, usize)> = HashSet::new();
535        for (c_pair, d_match_set) in &a_cluster_d_match {
536            // 条件 2.b: D-match 的所有元素都必须在当前的 Pi 中
537            if d_match_set.is_subset(&pi) {
538                v_c.insert(*c_pair);
539            }
540        }
541
542        info!("2. 初始化 V_C (Valid Clusters)");
543
544        // 3. 找出失效的 (u, v) 加入队列 Q
545        let mut q: VecDeque<(usize, usize)> = VecDeque::new();
546        let mut pi_retained = pi.clone();
547
548        for &(u_id, v_id) in &pi {
549            let mut all_in_vc = true;
550            if let Some(clusters) = hc_map.get(&(u_id, v_id)) {
551                for (c_pair, _) in clusters {
552                    if !v_c.contains(c_pair) {
553                        all_in_vc = false;
554                        break;
555                    }
556                }
557            }
558
559            if !all_in_vc {
560                q.push_back((u_id, v_id));      // 加入 Worklist
561                pi_retained.remove(&(u_id, v_id)); // Pi = Pi \ Q
562            }
563        }
564        pi = pi_retained;
565
566        info!("3. 找出失效的 (u, v) 加入队列 Q");
567
568        // ==========================================
569        // Phase 2: Cascade deletions via the queue
570        // ==========================================
571        while let Some((up_id, vp_id)) = q.pop_front() {
572            // 获取所有依赖于已删除节点对 (u', v') 的簇对 (Cu, Cv)
573            if let Some(dependent_clusters) = d_pair.get(&(up_id, vp_id)) {
574                for c_pair in dependent_clusters {
575                    // 如果簇对仍然被认为是有效的，现在它失效了
576                    if v_c.contains(c_pair) {
577                        v_c.remove(c_pair); // V_c = V_c \ {(Cu, Cv)}
578
579                        // 级联使依赖这个失效簇对的 (u, v) 失效
580                        if let Some(dependent_node_pairs) = d_cluster.get(c_pair) {
581                            for node_pair in dependent_node_pairs {
582                                if pi.contains(node_pair) {
583                                    pi.remove(node_pair);
584                                    q.push_back(*node_pair);
585                                }
586                            }
587                        }
588                    }
589                }
590            }
591        }
592
593        info!("结束了主调用");
594
595        // ==========================================
596        // Phase 3: Construct Output
597        // ==========================================
598        // 将基于 ID 的关系还原为引用的 HashMap
599        let mut result: HashMap<&'a Self::Node, HashSet<&'a Self::Node>> = 
600            self.nodes().map(|u| (u, HashSet::new())).collect();
601
602        for (u_id, v_id) in pi {
603            // 由于我们事先在字典中存过映射，这里可以安全取值
604            let u_node = id_to_u[&u_id];
605            let v_node = id_to_v[&v_id];
606            if let Some(set) = result.get_mut(u_node) {
607                set.insert(v_node);
608            }
609        }
610
611        result
612    }
613}
614
615#[derive(Serialize, Deserialize, Debug, PartialEq)]
616pub struct HyperSimulationTrace {
617    events: Vec<HSEvent>
618}
619
620impl HyperSimulationTrace {
621    fn new() -> Self {
622        HyperSimulationTrace {
623            events: Vec::new()
624        }
625    }
626
627    fn add_base_event(&mut self, sc_id: usize, d_match: HashSet<(usize, usize)>) {
628        let event = HSEvent::Base(sc_id, d_match);
629        self.events.push(event);
630    }
631    fn add_derivation_event(&mut self, sc_id: usize, uncoverd: HashSet<(usize, usize)>) {
632        let event = HSEvent::Derivation(sc_id, uncoverd);
633        self.events.push(event);
634    }
635}
636
637impl IntoIterator for HyperSimulationTrace {
638    type Item = HSEvent;
639    type IntoIter = std::vec::IntoIter<HSEvent>;
640    
641    fn into_iter(self) -> Self::IntoIter {
642        self.events.into_iter()
643    }
644}
645
646impl<'a> IntoIterator for &'a HyperSimulationTrace {
647    type Item = &'a HSEvent;
648    type IntoIter = std::slice::Iter<'a, HSEvent>;
649    
650    fn into_iter(self) -> Self::IntoIter {
651        self.events.iter()
652    }
653}
654
655impl TraceLog for HyperSimulationTrace {
656    fn store_trace_file(self, filename: &'static str) -> Result<(), Box<dyn Error>> {
657        // use bincode to save the HyperSimulationTrace.
658        let file = File::create(filename)?;
659        let mut writer = BufWriter::new(file);
660        bincode::serialize_into(&mut writer, &self)?;
661        Ok(())
662    }
663    
664    fn get_trace(filename: &'static str) -> Result<Self, Box<dyn Error>> {
665        let file = File::open(filename)?;
666        let mut reader = BufReader::new(file);
667        let file_decoded: HyperSimulationTrace = bincode::deserialize_from(&mut reader)?;
668        Ok(file_decoded)
669    }
670}
671
672#[derive(Serialize, Deserialize, Debug, PartialEq)]
673pub enum HSEvent {
674    Base(usize, HashSet<(usize, usize)>), // current D-Match
675    Derivation(usize, HashSet<(usize, usize)>) // D-Match \ Sim
676}
graph_simulation/algorithm/hyper_simulation.rs

graph_simulation/algorithm/
hyper_simulation.rs
