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_effect_pass_by(&'a self, other: &'a Self, delta: &'a impl Delta<'a, Node = Self::Node, Edge = Self::Edge>, d_match: & impl DMatch<'a, Edge = Self::Edge>, type_same_lookup: &HashMap<&'a Self::Node, HashSet<&'a Self::Node>>) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
77    fn get_hyper_simulation_effect_by_id(&'a self, hc_map: &HashMap<(usize, usize), Vec<((usize, usize), HashSet<(usize, usize)>)>>) -> HashSet<(usize, usize)>;
78    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>>;
79}
80// struct MultiWriter<W1: Write, W2: Write> {
81//     w1: W1,
82//     w2: W2,
83// }
84
85// impl<W1: Write, W2: Write> Write for MultiWriter<W1, W2> {
86//     fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
87//         self.w1.write_all(buf)?;
88//         self.w2.write_all(buf)?;
89//         Ok(buf.len())
90//     }
91//     fn flush(&mut self) -> io::Result<()> {
92//         self.w1.flush()?;
93//         self.w2.flush()
94//     }
95// }
96
97
98impl<'a, H> HyperSimulation<'a> for H 
99where H: Hypergraph<'a> + Typed<'a> + LPredicate<'a> + ContainedHyperedge<'a> {
100    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>> {
101        todo!()
102    }
103
104    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>> {
105        todo!()
106    }
107
108    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>> {
109        
110        // let log_file = File::create("hyper-simulation.log")
111        //     .expect("Failed to create log file");
112        // let multi_writer = MultiWriter {
113        //     w1: log_file,
114        //     w2: io::stdout(),
115        // };
116        
117        // env_logger::Builder::new()
118        //     .target(env_logger::Target::Pipe(Box::new(multi_writer)))
119        //     .init();
120
121        init_global_logger_once("hyper-simulation.log");
122
123        info!("Start Naive Hyper Simulation");
124
125        let self_contained_hyperedge = self.get_hyperedges_list();
126        let other_contained_hyperedge = other.get_hyperedges_list();
127
128        let mut simulation: HashMap<&Self::Node, HashSet<&Self::Node>> = self.nodes().map(|u| {
129            let res = other.nodes().filter(|v| {
130                if self.type_same(u, *v) {
131                    // For each e, compute the union of l_match(u) over all matching e_prime,
132                    // then take the intersection across all e.
133                    let mut l_match_intersection: Option<HashSet<usize>> = None;
134                    for e in self.contained_hyperedges(&self_contained_hyperedge, u) {
135                        let mut l_match_union: HashSet<usize> = HashSet::new();
136                        for e_prime in other.contained_hyperedges(&other_contained_hyperedge, v) {
137                            if self.l_predicate_edge(e, e_prime) {
138                                // let l_match = self.l_match(e, e_prime);
139                                let id_set = l_match.l_match_with_node(e, e_prime, u.id());
140                                l_match_union = l_match_union.union(&id_set).copied().collect();
141                            }
142                        }
143                        l_match_intersection = match l_match_intersection {
144                            Some(ref acc) => Some(acc.intersection(&l_match_union).copied().collect()),
145                            None => Some(l_match_union),
146                        };
147                    }
148                    if let Some(l_match_intersection) = l_match_intersection {
149                        if l_match_intersection.contains(&v.id()){
150                            return true;
151                        }
152                    }
153                }
154                false
155            }).collect();
156            (u, res)
157        }).collect();
158
159        info!("END Initial, sim: is ");
160        for (u, v_set) in &simulation {
161            info!("\tsim({}) = {:?}", u.id(), v_set.iter().map(|v| v.id()).collect::<Vec<_>>());
162        }
163        
164
165        let mut changed = true;
166        while changed {
167            changed = false;
168            for u in self.nodes() {
169                let mut need_delete = Vec::new();
170                for v in simulation.get(u).unwrap() {
171                    info!("Checking {} -> {}", u.id(), v.id());
172                    let mut _delete = true;
173                    for e in self.contained_hyperedges(&self_contained_hyperedge, u) {
174                        if !_delete {
175                            break;
176                        }
177                        for e_prime in other.contained_hyperedges(&other_contained_hyperedge, v) {
178                            if self.l_predicate_edge(e, e_prime) {
179                                if l_match.dom(e, e_prime).all(|u_prime| {
180                                    l_match.l_match_with_node(e, e_prime, u_prime.clone()).iter().map(|id| {other.get_node_by_id(*id)}).any(|v_prime| {
181                                        if let Some(v_prime) = v_prime {
182                                            return simulation.get(u).unwrap().contains(v_prime);
183                                        } else {
184                                            return false;
185                                        }
186                                    })
187                                }) {
188                                    info!("Keeping {} -> {}", u.id(), v.id());
189                                    _delete = false;
190                                    break;
191                                }
192                            }
193                        }
194                    }
195                    if _delete {
196                        info!("Deleting {} -> {}", u.id(), v.id());
197                        need_delete.push(v.clone());
198                    }
199                }
200                for v in need_delete {
201                    simulation.get_mut(u).unwrap().remove(v);
202                    changed = true;
203                }
204            }
205        }
206
207        simulation
208    }
209
210    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>> {
211        init_global_logger_once("hyper-simulation.log");
212
213        info!("Start Naive Hyper Simulation");
214
215        // let self_contained_hyperedge = self.get_hyperedges_list();
216        // let other_contained_hyperedge = other.get_hyperedges_list();
217
218        let mut l_predicate_edges: HashMap<(usize, usize), Vec<(&Self::Edge, &Self::Edge)>> = HashMap::new();
219        for e in self.hyperedges() {
220            for e_prime in other.hyperedges() {
221                if self.l_predicate_edge(e, e_prime) {
222                    for u in e.id_set() {
223                        for v in e_prime.id_set() {
224                            l_predicate_edges.entry((u, v)).or_default().push((e, e_prime));
225                        }
226                    }
227                }
228            }
229        }
230
231        let mut simulation: HashMap<&'a Self::Node, HashSet<&'a Self::Node>> = self.nodes().map(|u| {
232            let res = other.nodes().filter(|v| {
233                if self.type_same(u, *v) {
234                    if let Some(edge_pairs) = l_predicate_edges.get(&(u.id(), v.id())) {
235                        for (e, e_prime) in edge_pairs {
236                            let id_set = l_match.l_match_with_node(e, e_prime, u.id());
237                            if !id_set.contains(&v.id()) {
238                                return false;
239                            }
240                        }
241                        return true;
242                    } else {
243                        return true;
244                    }
245                }
246                false
247            }).collect();
248            (u, res)
249        }).collect();
250
251        info!("END Initial, sim: is ");
252        for (u, v_set) in &simulation {
253            info!("\tsim({}) = {:?}", u.id(), v_set.iter().map(|v| v.id()).collect::<Vec<_>>());
254        }
255        
256
257        let mut changed = true;
258        while changed {
259            changed = false;
260            for u in self.nodes() {
261                let mut need_delete = Vec::new();
262                for v in simulation.get(u).unwrap() {
263                    info!("Checking {} -> {}", u.id(), v.id());
264                    let mut _delete = false;
265
266                    if let Some(edge_pairs) = l_predicate_edges.get(&(u.id(), v.id())) {
267                        for (e, e_prime) in edge_pairs {
268                            if l_match.dom(e, e_prime).all(|u_prime| {
269                                l_match.l_match_with_node(e, e_prime, u_prime.clone()).iter().map(|id| {other.get_node_by_id(*id)}).any(|v_prime| {
270                                    if let Some(v_prime) = v_prime {
271                                        return simulation.get(u).unwrap().contains(v_prime);
272                                    } else {
273                                        return false;
274                                    }
275                                })
276                            }) {
277                                info!("Keeping {} -> {}", u.id(), v.id());
278                                _delete = true;
279                                break;
280                            }
281                        }
282                    }
283
284                    if _delete {
285                        info!("Deleting {} -> {}", u.id(), v.id());
286                        need_delete.push(v.clone());
287                    }
288                }
289
290                for v in need_delete {
291                    simulation.get_mut(u).unwrap().remove(v);
292                    changed = true;
293                }
294            }
295        }
296
297        simulation
298
299    }
300
301    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>> {
302        init_global_logger_once("logs/hyper-simulation.log");
303        let mut hs_trace = HyperSimulationTrace::new();
304        let mut simulation: HashMap<&'a Self::Node, HashSet<&'a Self::Node>> = self.nodes().map(|u| {
305            let res = other.nodes().filter(|v| {
306                if self.type_same(u, *v) {
307                    let sematic_clusters = delta.get_sematic_clusters(u, v);
308                    for (cluster_u, cluster_v) in sematic_clusters {
309                        let d_match_set = d_match.d_match(cluster_u, cluster_v);
310                        if !d_match_set.contains(&(u.id(), v.id())) {
311                            // Add the trace that nodes (u, v) are deleted by the `sematic_clusters`
312                            hs_trace.add_base_event(cluster_u.id, d_match_set.clone());
313                            return false;
314                        }
315                    }
316                    return true;
317                }
318                false
319            }).collect();
320            (u, res)
321        }).collect();
322
323        info!("END Initial, raw-sim: is ");
324        for (u, v_set) in &simulation {
325            info!("\tsim({}) = {:?}", u.id(), v_set.iter().map(|v| v.id()).collect::<Vec<_>>());
326        }
327
328        let mut simulation_by_id: HashSet<(usize, usize)> = simulation.iter().flat_map(|(u, v_set)| {
329            v_set.iter().map(move |v| (u.id(), v.id()))
330        }).collect();
331
332        let mut changed = true;
333        while changed {
334            changed = false;
335            for u in self.nodes() {
336                let mut need_delete = Vec::new();
337                for v in simulation.get(u).unwrap() {
338                    info!("Checking {} -> {}", u.id(), v.id());
339                    let mut _delete = false;
340
341                    let sematic_clusters = delta.get_sematic_clusters(u, v);
342                    for (cluster_u, cluster_v) in sematic_clusters {
343                        let d_relation = d_match.d_match(cluster_u, cluster_v);
344                        // 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
345                        if !d_relation.is_subset(&simulation_by_id) {
346                            info!("Deleting {} -> {}", u.id(), v.id());
347                            // Add the trace that nodes (u, v) are deleted by the `sematic_clusters`
348                            let uncoverd: HashSet<(usize, usize)> = d_relation.difference(&simulation_by_id).copied().collect();
349                            hs_trace.add_derivation_event(cluster_u.id, uncoverd);
350                            _delete = true;
351                            break;
352                        }
353                    }
354
355                    if _delete {
356                        need_delete.push(v.clone());
357                    }
358                }
359
360                for v in need_delete {
361                    simulation.get_mut(u).unwrap().remove(v);
362                    simulation_by_id.remove(&(u.id(), v.id()));
363                    changed = true;
364                }
365            }
366        }
367
368        hs_trace.store_trace_file("logs/hyper_simulation.trace").unwrap();
369
370        return simulation;
371    }
372
373    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>> {
374        init_global_logger_once("logs/hyper-simulation.log");
375        let mut hs_trace = HyperSimulationTrace::new();
376        let mut simulation: HashMap<&'a Self::Node, HashSet<&'a Self::Node>> = self.nodes().map(|u| {
377            let res = other.nodes().filter(|v| {
378                if self.type_same(u, *v) {
379                    let sematic_clusters = delta.get_sematic_clusters(u, v);
380                    // Highlight!
381                    if sematic_clusters.len() == 0 {
382                        info!("Deleting {} -> {} because no sematic cluster", u.id(), v.id());
383                        return false;
384                    }
385                    info!("Checking {} -> {}, sematic clusters size: {}", u.id(), v.id(), sematic_clusters.len());
386                    for (cluster_u, cluster_v) in sematic_clusters {
387                        let d_match_set = d_match.d_match(cluster_u, cluster_v);
388                        if !d_match_set.contains(&(u.id(), v.id())) {
389                            // Add the trace that nodes (u, v) are deleted by the `sematic_clusters`
390                            hs_trace.add_base_event(cluster_u.id, d_match_set.clone());
391                            return false;
392                        }
393                    }
394                    return true;
395                }
396                false
397            }).collect();
398            (u, res)
399        }).collect();
400
401        info!("END Initial, raw-sim: is ");
402        for (u, v_set) in &simulation {
403            info!("\tsim({}) = {:?}", u.id(), v_set.iter().map(|v| v.id()).collect::<Vec<_>>());
404        }
405
406        let mut simulation_by_id: HashSet<(usize, usize)> = simulation.iter().flat_map(|(u, v_set)| {
407            v_set.iter().map(move |v| (u.id(), v.id()))
408        }).collect();
409
410        let mut changed = true;
411        while changed {
412            changed = false;
413            for u in self.nodes() {
414                let mut need_delete = Vec::new();
415                for v in simulation.get(u).unwrap() {
416                    info!("Checking {} -> {}", u.id(), v.id());
417                    let mut _delete = false;
418
419                    let sematic_clusters = delta.get_sematic_clusters(u, v);
420                    for (cluster_u, cluster_v) in sematic_clusters {
421                        let d_relation = d_match.d_match(cluster_u, cluster_v);
422                        // 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
423                        if !d_relation.is_subset(&simulation_by_id) {
424                            info!("Deleting {} -> {}", u.id(), v.id());
425                            // Add the trace that nodes (u, v) are deleted by the `sematic_clusters`
426                            let uncoverd: HashSet<(usize, usize)> = d_relation.difference(&simulation_by_id).copied().collect();
427                            hs_trace.add_derivation_event(cluster_u.id, uncoverd);
428                            _delete = true;
429                            break;
430                        }
431                    }
432
433                    if _delete {
434                        need_delete.push(v.clone());
435                    }
436                }
437
438                for v in need_delete {
439                    simulation.get_mut(u).unwrap().remove(v);
440                    simulation_by_id.remove(&(u.id(), v.id()));
441                    changed = true;
442                }
443            }
444        }
445
446        hs_trace.store_trace_file("logs/hyper_simulation.trace").unwrap();
447
448        return simulation;
449    }
450
451    fn get_hyper_simulation_effect(
452        &'a self,
453        other: &'a Self,
454        delta: &'a impl Delta<'a, Node = Self::Node, Edge = Self::Edge>,
455        d_match: &impl DMatch<'a, Edge = Self::Edge>,
456    ) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
457
458        init_global_logger_once("logs/hyper-simulation.log");
459
460        // 建立 ID 到节点的映射，方便最后构造返回结果
461        let mut id_to_u: HashMap<usize, &'a Self::Node> = HashMap::new();
462        let mut id_to_v: HashMap<usize, &'a Self::Node> = HashMap::new();
463
464        // 存储节点对与其对应的所有的 Semantic Clusters (HC) 及 D-match 结果
465        let mut hc_map: HashMap<(usize, usize), Vec<((usize, usize), HashSet<(usize, usize)>)>> = HashMap::new();
466        
467        // Pi: 当前满足 Hyper Simulation 条件的 (u.id(), v.id()) 集合
468        let mut pi: HashSet<(usize, usize)> = HashSet::new();
469
470        // ==========================================
471        // Phase 1: Declarative Initialization
472        // ==========================================
473        
474        // 1. 初始化 Pi 并获取 HC 和 D-match
475        for u in self.nodes() {
476            id_to_u.insert(u.id(), u);
477            for v in other.nodes() {
478                id_to_v.insert(v.id(), v);
479
480                if self.type_same(u, v) {
481                    let sematic_clusters = delta.get_sematic_clusters(u, v);
482                    let mut valid = true;
483                    let mut local_clusters = Vec::new();
484
485                    for (cluster_u, cluster_v) in sematic_clusters {
486                        let cu_id = cluster_u.id;
487                        let cv_id = cluster_v.id;
488                        let d_match_set = d_match.d_match(cluster_u, cluster_v);
489
490                        // 条件 2.a: (u, v) 必须在 D-match 中
491                        if !d_match_set.contains(&(u.id(), v.id())) {
492                            valid = false;
493                            break; // 只要有一个 cluster 失败，(u,v) 就不可能在 Pi 中
494                        }
495                        local_clusters.push(((cu_id, cv_id), d_match_set.clone()));
496                    }
497
498                    if valid {
499                        pi.insert((u.id(), v.id()));
500                        hc_map.insert((u.id(), v.id()), local_clusters);
501                    }
502                }
503            }
504        }
505
506        info!("完成了 Pi 的初始化和 HC、D-match 的获取，Pi 大小: {}", pi.len());
507
508        // A_cluster 对应的 D-match 缓存，避免重复计算
509        let mut a_cluster_d_match: HashMap<(usize, usize), HashSet<(usize, usize)>> = HashMap::new();
510        
511        // 依赖索引构建:
512        // D_cluster[(Cu, Cv)] -> { (u, v) \in Pi } 
513        let mut d_cluster: HashMap<(usize, usize), HashSet<(usize, usize)>> = HashMap::new();
514        // D_pair[(u', v')] -> { (Cu, Cv) \in A_cluster }
515        let mut d_pair: HashMap<(usize, usize), HashSet<(usize, usize)>> = HashMap::new();
516
517        for (&(u_id, v_id), clusters) in &hc_map {
518            for ((cu_id, cv_id), d_match_set) in clusters {
519                let c_pair = (*cu_id, *cv_id);
520                
521                // 填充 D_cluster
522                d_cluster.entry(c_pair).or_default().insert((u_id, v_id));
523
524                // 如果这是第一次遇到这个簇对，填充 D_pair
525                if !a_cluster_d_match.contains_key(&c_pair) {
526                    a_cluster_d_match.insert(c_pair, d_match_set.clone());
527
528                    for &(up_id, vp_id) in d_match_set {
529                        d_pair.entry((up_id, vp_id)).or_default().insert(c_pair);
530                    }
531                }
532            }
533        }
534
535        info!("1. 初始化 Pi 并获取 HC 和 D-match");
536
537        // 2. 初始化 V_C (Valid Clusters)
538        let mut v_c: HashSet<(usize, usize)> = HashSet::new();
539        for (c_pair, d_match_set) in &a_cluster_d_match {
540            // 条件 2.b: D-match 的所有元素都必须在当前的 Pi 中
541            if d_match_set.is_subset(&pi) {
542                v_c.insert(*c_pair);
543            }
544        }
545
546        info!("2. 初始化 V_C (Valid Clusters)");
547
548        // 3. 找出失效的 (u, v) 加入队列 Q
549        let mut q: VecDeque<(usize, usize)> = VecDeque::new();
550        let mut pi_retained = pi.clone();
551
552        for &(u_id, v_id) in &pi {
553            let mut all_in_vc = true;
554            if let Some(clusters) = hc_map.get(&(u_id, v_id)) {
555                for (c_pair, _) in clusters {
556                    if !v_c.contains(c_pair) {
557                        all_in_vc = false;
558                        break;
559                    }
560                }
561            }
562
563            if !all_in_vc {
564                q.push_back((u_id, v_id));      // 加入 Worklist
565                pi_retained.remove(&(u_id, v_id)); // Pi = Pi \ Q
566            }
567        }
568        pi = pi_retained;
569
570        info!("3. 找出失效的 (u, v) 加入队列 Q");
571
572        // ==========================================
573        // Phase 2: Cascade deletions via the queue
574        // ==========================================
575        while let Some((up_id, vp_id)) = q.pop_front() {
576            // 获取所有依赖于已删除节点对 (u', v') 的簇对 (Cu, Cv)
577            if let Some(dependent_clusters) = d_pair.get(&(up_id, vp_id)) {
578                for c_pair in dependent_clusters {
579                    // 如果簇对仍然被认为是有效的，现在它失效了
580                    if v_c.contains(c_pair) {
581                        v_c.remove(c_pair); // V_c = V_c \ {(Cu, Cv)}
582
583                        // 级联使依赖这个失效簇对的 (u, v) 失效
584                        if let Some(dependent_node_pairs) = d_cluster.get(c_pair) {
585                            for node_pair in dependent_node_pairs {
586                                if pi.contains(node_pair) {
587                                    pi.remove(node_pair);
588                                    q.push_back(*node_pair);
589                                }
590                            }
591                        }
592                    }
593                }
594            }
595        }
596
597        info!("结束了主调用");
598
599        // ==========================================
600        // Phase 3: Construct Output
601        // ==========================================
602        // 将基于 ID 的关系还原为引用的 HashMap
603        let mut result: HashMap<&'a Self::Node, HashSet<&'a Self::Node>> = 
604            self.nodes().map(|u| (u, HashSet::new())).collect();
605
606        for (u_id, v_id) in pi {
607            // 由于我们事先在字典中存过映射，这里可以安全取值
608            let u_node = id_to_u[&u_id];
609            let v_node = id_to_v[&v_id];
610            if let Some(set) = result.get_mut(u_node) {
611                set.insert(v_node);
612            }
613        }
614
615        result
616    }
617
618    fn get_hyper_simulation_effect_pass_by(&'a self, _other: &'a Self, delta: &'a impl Delta<'a, Node = Self::Node, Edge = Self::Edge>, d_match: & impl DMatch<'a, Edge = Self::Edge>, type_same_lookup: &HashMap<&'a Self::Node, HashSet<&'a Self::Node>>) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
619        init_global_logger_once("logs/hyper-simulation.log");
620
621        // 建立 ID 到节点的映射，方便最后构造返回结果
622        let mut id_to_u: HashMap<usize, &'a Self::Node> = HashMap::new();
623        let mut id_to_v: HashMap<usize, &'a Self::Node> = HashMap::new();
624
625        // 存储节点对与其对应的所有的 Semantic Clusters (HC) 及 D-match 结果
626        let mut hc_map: HashMap<(usize, usize), Vec<((usize, usize), HashSet<(usize, usize)>)>> = HashMap::new();
627        
628        // Pi: 当前满足 Hyper Simulation 条件的 (u.id(), v.id()) 集合
629        let mut pi: HashSet<(usize, usize)> = HashSet::new();
630
631        // ==========================================
632        // Phase 1: Declarative Initialization
633        // ==========================================
634        
635        // 1. 初始化 Pi 并获取 HC 和 D-match
636        for u in self.nodes() {
637            id_to_u.insert(u.id(), u);
638
639            if let Some(type_same_vs) = type_same_lookup.get(u) {
640                for v in type_same_vs {
641                    id_to_v.insert(v.id(), v);
642
643                    let sematic_clusters = delta.get_sematic_clusters(u, v);
644                    let mut valid = true;
645                    let mut local_clusters = Vec::new();
646
647                    for (cluster_u, cluster_v) in sematic_clusters {
648                        let cu_id = cluster_u.id;
649                        let cv_id = cluster_v.id;
650                        let d_match_set = d_match.d_match(cluster_u, cluster_v);
651
652                        // 条件 2.a: (u, v) 必须在 D-match 中
653                        if !d_match_set.contains(&(u.id(), v.id())) {
654                            valid = false;
655                            break; // 只要有一个 cluster 失败，(u,v) 就不可能在 Pi 中
656                        }
657                        local_clusters.push(((cu_id, cv_id), d_match_set.clone()));
658                    }
659
660                    if valid {
661                        pi.insert((u.id(), v.id()));
662                        hc_map.insert((u.id(), v.id()), local_clusters);
663                    }
664                }
665            }
666        }
667
668        info!("完成了 Pi 的初始化和 HC、D-match 的获取，Pi 大小: {}", pi.len());
669
670        // A_cluster 对应的 D-match 缓存，避免重复计算
671        let mut a_cluster_d_match: HashMap<(usize, usize), HashSet<(usize, usize)>> = HashMap::new();
672        
673        // 依赖索引构建:
674        // D_cluster[(Cu, Cv)] -> { (u, v) \in Pi } 
675        let mut d_cluster: HashMap<(usize, usize), HashSet<(usize, usize)>> = HashMap::new();
676        // D_pair[(u', v')] -> { (Cu, Cv) \in A_cluster }
677        let mut d_pair: HashMap<(usize, usize), HashSet<(usize, usize)>> = HashMap::new();
678
679        for (&(u_id, v_id), clusters) in &hc_map {
680            for ((cu_id, cv_id), d_match_set) in clusters {
681                let c_pair = (*cu_id, *cv_id);
682                
683                // 填充 D_cluster
684                d_cluster.entry(c_pair).or_default().insert((u_id, v_id));
685
686                // 如果这是第一次遇到这个簇对，填充 D_pair
687                if !a_cluster_d_match.contains_key(&c_pair) {
688                    a_cluster_d_match.insert(c_pair, d_match_set.clone());
689
690                    for &(up_id, vp_id) in d_match_set {
691                        d_pair.entry((up_id, vp_id)).or_default().insert(c_pair);
692                    }
693                }
694            }
695        }
696
697        info!("1. 初始化 Pi 并获取 HC 和 D-match");
698
699        // 2. 初始化 V_C (Valid Clusters)
700        let mut v_c: HashSet<(usize, usize)> = HashSet::new();
701        for (c_pair, d_match_set) in &a_cluster_d_match {
702            // 条件 2.b: D-match 的所有元素都必须在当前的 Pi 中
703            if d_match_set.is_subset(&pi) {
704                v_c.insert(*c_pair);
705            }
706        }
707
708        info!("2. 初始化 V_C (Valid Clusters)");
709
710        // 3. 找出失效的 (u, v) 加入队列 Q
711        let mut q: VecDeque<(usize, usize)> = VecDeque::new();
712        let mut pi_retained = pi.clone();
713
714        for &(u_id, v_id) in &pi {
715            let mut all_in_vc = true;
716            if let Some(clusters) = hc_map.get(&(u_id, v_id)) {
717                for (c_pair, _) in clusters {
718                    if !v_c.contains(c_pair) {
719                        all_in_vc = false;
720                        break;
721                    }
722                }
723            }
724
725            if !all_in_vc {
726                q.push_back((u_id, v_id));      // 加入 Worklist
727                pi_retained.remove(&(u_id, v_id)); // Pi = Pi \ Q
728            }
729        }
730        pi = pi_retained;
731
732        info!("3. 找出失效的 (u, v) 加入队列 Q");
733
734        // ==========================================
735        // Phase 2: Cascade deletions via the queue
736        // ==========================================
737        while let Some((up_id, vp_id)) = q.pop_front() {
738            // 获取所有依赖于已删除节点对 (u', v') 的簇对 (Cu, Cv)
739            if let Some(dependent_clusters) = d_pair.get(&(up_id, vp_id)) {
740                for c_pair in dependent_clusters {
741                    // 如果簇对仍然被认为是有效的，现在它失效了
742                    if v_c.contains(c_pair) {
743                        v_c.remove(c_pair); // V_c = V_c \ {(Cu, Cv)}
744
745                        // 级联使依赖这个失效簇对的 (u, v) 失效
746                        if let Some(dependent_node_pairs) = d_cluster.get(c_pair) {
747                            for node_pair in dependent_node_pairs {
748                                if pi.contains(node_pair) {
749                                    pi.remove(node_pair);
750                                    q.push_back(*node_pair);
751                                }
752                            }
753                        }
754                    }
755                }
756            }
757        }
758
759        info!("结束了主调用");
760
761        // ==========================================
762        // Phase 3: Construct Output
763        // ==========================================
764        // 将基于 ID 的关系还原为引用的 HashMap
765        let mut result: HashMap<&'a Self::Node, HashSet<&'a Self::Node>> = 
766            self.nodes().map(|u| (u, HashSet::new())).collect();
767
768        for (u_id, v_id) in pi {
769            // 由于我们事先在字典中存过映射，这里可以安全取值
770            let u_node = id_to_u[&u_id];
771            let v_node = id_to_v[&v_id];
772            if let Some(set) = result.get_mut(u_node) {
773                set.insert(v_node);
774            }
775        }
776
777        result
778    }
779
780    fn get_hyper_simulation_effect_by_id(&'a self, hc_map: &HashMap<(usize, usize), Vec<((usize, usize), HashSet<(usize, usize)>)>>) -> HashSet<(usize, usize)> {
781        // ==========================================
782        // hc_map 参数说明：
783        // ==========================================
784        // hc_map 是一个预计算的语义集群和 D-match 关系映射表，用于完全在 ID 空间内执行 Hyper Simulation 计算。
785        // 
786        // 结构：HashMap<(u_id, v_id), Vec<((cu_id, cv_id), D_match_set)>>
787        // 
788        // 键 (u_id, v_id)：
789        //   - 候选节点对，其中 u_id 属于 self，v_id 属于 other
790        //   - 代表可能参加 Hyper Simulation 的节点对
791        // 
792        // 值 Vec<((cu_id, cv_id), D_match_set)>：
793        //   - 该节点对相关的所有语义集群及其 D-match 关系
794        //   - (cu_id, cv_id)：语义集群对的 ID（u 侧和 v 侧）
795        //   - D_match_set：HashSet<(usize, usize)>，该集群对的 D-match 结果
796        //     即满足 d_match(cluster_u, cluster_v) 的所有节点对 (u'_id, v'_id)
797        // 
798        // 调用前的准备步骤（由调用者负责）：
799        //   1. 计算 type_same 的两个图之间所有可兼容的节点对
800        //   2. 对每个节点对，调用 delta.get_sematic_clusters() 获取语义集群
801        //   3. 对每个集群对，调用 d_match.d_match() 计算 D-match 集合
802        //   4. 构建此 hc_map 并传入
803        //
804        // 函数内执行：
805        //   - 完全基于 ID-based 的数据结构，不涉及具体的节点类型
806        //   - 执行三个阶段：初始化、V_C 构建、级联删除
807        //   - 返回最终的 Hyper Simulation 结果集合
808        
809        init_global_logger_once("logs/hyper-simulation.log");
810
811        // Pi: 当前满足 Hyper Simulation 条件的 (u.id(), v.id()) 集合
812        let mut pi: HashSet<(usize, usize)> = HashSet::new();
813
814        // ==========================================
815        // Phase 1: Initialize Pi from hc_map
816        // ==========================================
817        for &(u_id, v_id) in hc_map.keys() {
818            pi.insert((u_id, v_id));
819        }
820
821        info!("完成了 Pi 的初始化和 HC、D-match 的获取，Pi 大小: {}", pi.len());
822
823        // A_cluster 对应的 D-match 缓存，避免重复计算
824        let mut a_cluster_d_match: HashMap<(usize, usize), HashSet<(usize, usize)>> = HashMap::new();
825        
826        // 依赖索引构建:
827        // D_cluster[(Cu, Cv)] -> { (u, v) \in Pi } 
828        let mut d_cluster: HashMap<(usize, usize), HashSet<(usize, usize)>> = HashMap::new();
829        // D_pair[(u', v')] -> { (Cu, Cv) \in A_cluster }
830        let mut d_pair: HashMap<(usize, usize), HashSet<(usize, usize)>> = HashMap::new();
831
832        for (&(u_id, v_id), clusters) in hc_map.iter() {
833            for ((cu_id, cv_id), d_match_set) in clusters {
834                let c_pair = (*cu_id, *cv_id);
835                
836                // 填充 D_cluster
837                d_cluster.entry(c_pair).or_default().insert((u_id, v_id));
838
839                // 如果这是第一次遇到这个簇对，填充 D_pair
840                if !a_cluster_d_match.contains_key(&c_pair) {
841                    a_cluster_d_match.insert(c_pair, d_match_set.clone());
842
843                    for &(up_id, vp_id) in d_match_set {
844                        d_pair.entry((up_id, vp_id)).or_default().insert(c_pair);
845                    }
846                }
847            }
848        }
849
850        info!("1. 初始化 Pi 并获取 HC 和 D-match");
851
852        // 2. 初始化 V_C (Valid Clusters)
853        let mut v_c: HashSet<(usize, usize)> = HashSet::new();
854        for (c_pair, d_match_set) in &a_cluster_d_match {
855            // 条件 2.b: D-match 的所有元素都必须在当前的 Pi 中
856            if d_match_set.is_subset(&pi) {
857                v_c.insert(*c_pair);
858            }
859        }
860
861        info!("2. 初始化 V_C (Valid Clusters)");
862
863        // 3. 找出失效的 (u, v) 加入队列 Q
864        let mut q: VecDeque<(usize, usize)> = VecDeque::new();
865        let mut pi_retained = pi.clone();
866
867        for &(u_id, v_id) in &pi {
868            let mut all_in_vc = true;
869            if let Some(clusters) = hc_map.get(&(u_id, v_id)) {
870                for (c_pair, _) in clusters {
871                    if !v_c.contains(c_pair) {
872                        all_in_vc = false;
873                        break;
874                    }
875                }
876            }
877
878            if !all_in_vc {
879                q.push_back((u_id, v_id));      // 加入 Worklist
880                pi_retained.remove(&(u_id, v_id)); // Pi = Pi \ Q
881            }
882        }
883        pi = pi_retained;
884
885        info!("3. 找出失效的 (u, v) 加入队列 Q");
886
887        // ==========================================
888        // Phase 2: Cascade deletions via the queue
889        // ==========================================
890        while let Some((up_id, vp_id)) = q.pop_front() {
891            // 获取所有依赖于已删除节点对 (u', v') 的簇对 (Cu, Cv)
892            if let Some(dependent_clusters) = d_pair.get(&(up_id, vp_id)) {
893                for c_pair in dependent_clusters {
894                    // 如果簇对仍然被认为是有效的，现在它失效了
895                    if v_c.contains(c_pair) {
896                        v_c.remove(c_pair); // V_c = V_c \ {(Cu, Cv)}
897
898                        // 级联使依赖这个失效簇对的 (u, v) 失效
899                        if let Some(dependent_node_pairs) = d_cluster.get(c_pair) {
900                            for node_pair in dependent_node_pairs {
901                                if pi.contains(node_pair) {
902                                    pi.remove(node_pair);
903                                    q.push_back(*node_pair);
904                                }
905                            }
906                        }
907                    }
908                }
909            }
910        }
911
912        info!("结束了主调用");
913
914        // ==========================================
915        // Phase 3: Return ID-based Result
916        // ==========================================
917        pi
918    }
919}
920
921#[derive(Serialize, Deserialize, Debug, PartialEq)]
922pub struct HyperSimulationTrace {
923    events: Vec<HSEvent>
924}
925
926impl HyperSimulationTrace {
927    fn new() -> Self {
928        HyperSimulationTrace {
929            events: Vec::new()
930        }
931    }
932
933    fn add_base_event(&mut self, sc_id: usize, d_match: HashSet<(usize, usize)>) {
934        let event = HSEvent::Base(sc_id, d_match);
935        self.events.push(event);
936    }
937    fn add_derivation_event(&mut self, sc_id: usize, uncoverd: HashSet<(usize, usize)>) {
938        let event = HSEvent::Derivation(sc_id, uncoverd);
939        self.events.push(event);
940    }
941}
942
943impl IntoIterator for HyperSimulationTrace {
944    type Item = HSEvent;
945    type IntoIter = std::vec::IntoIter<HSEvent>;
946    
947    fn into_iter(self) -> Self::IntoIter {
948        self.events.into_iter()
949    }
950}
951
952impl<'a> IntoIterator for &'a HyperSimulationTrace {
953    type Item = &'a HSEvent;
954    type IntoIter = std::slice::Iter<'a, HSEvent>;
955    
956    fn into_iter(self) -> Self::IntoIter {
957        self.events.iter()
958    }
959}
960
961impl TraceLog for HyperSimulationTrace {
962    fn store_trace_file(self, filename: &'static str) -> Result<(), Box<dyn Error>> {
963        // use bincode to save the HyperSimulationTrace.
964        let file = File::create(filename)?;
965        let mut writer = BufWriter::new(file);
966        bincode::serialize_into(&mut writer, &self)?;
967        Ok(())
968    }
969    
970    fn get_trace(filename: &'static str) -> Result<Self, Box<dyn Error>> {
971        let file = File::open(filename)?;
972        let mut reader = BufReader::new(file);
973        let file_decoded: HyperSimulationTrace = bincode::deserialize_from(&mut reader)?;
974        Ok(file_decoded)
975    }
976}
977
978#[derive(Serialize, Deserialize, Debug, PartialEq)]
979pub enum HSEvent {
980    Base(usize, HashSet<(usize, usize)>), // current D-Match
981    Derivation(usize, HashSet<(usize, usize)>) // D-Match \ Sim
982}
graph_simulation/algorithm/hyper_simulation.rs

graph_simulation/algorithm/
hyper_simulation.rs
