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

graph_simulation/algorithm/
hyper_simulation.rs
