graph_simulation/algorithm/
hyper_simulation.rs

1use std::collections::{HashMap, HashSet};
2use log::{info, warn};
3// use std::fs::File;
4// use std::io::{self, Write};
5use crate::{algorithm::simulation, utils::logger::init_global_logger_once};
6
7use graph_base::interfaces::{edge::{DirectedHyperedge, Hyperedge}, graph::SingleId, hypergraph::{ContainedDirectedHyperedge, ContainedHyperedge, DirectedHypergraph, Hypergraph}, typed::{Type, Typed}};
8
9pub trait LMatch {
10    type Edge;
11    // fn l_match(&'a self, e: &'a Self::Edge, e_prime: &'a Self::Edge) -> HashMap<&'a Self::Node, &'a HashSet<&'a Self::Node>>;
12    fn new() -> Self;
13    fn l_match_with_node_mut(&mut self, e: &Self::Edge, e_prime: &Self::Edge, u: usize) -> &HashSet<usize>;
14    fn l_match_with_node(&self, e: &Self::Edge, e_prime: &Self::Edge, u: usize) -> &HashSet<usize>;
15    fn dom(&self, e: &Self::Edge, e_prime: &Self::Edge) -> impl Iterator<Item = &usize>;
16}
17
18pub struct SematicCluster<'a, E: Hyperedge> {
19    id: usize,
20    hyperedges: Vec<&'a E>,
21}
22
23pub trait Delta<'a> {
24    type Node;
25    type Edge: Hyperedge;
26    fn get_sematic_clusters(&self, u: &'a Self::Node, v: &'a Self::Node) -> &'a Vec<(SematicCluster<'a, Self::Edge>, SematicCluster<'a, Self::Edge>)>;
27}
28
29pub trait DMatch<'a> {
30    type Edge: Hyperedge;
31    fn new() -> Self;
32    fn d_match_mut(&mut self, e: &SematicCluster<'a, Self::Edge>, e_prime: &SematicCluster<'a, Self::Edge>) -> &HashSet<(usize, usize)>;
33    fn d_match(&self, e: &SematicCluster<'a, Self::Edge>, e_prime: &SematicCluster<'a, Self::Edge>) -> &HashSet<(usize, usize)>;
34}
35
36pub trait LPredicate<'a>: Hypergraph<'a> {
37    fn l_predicate_node(&'a self, u: &'a Self::Node, v: &'a Self::Node) -> bool;
38    fn l_predicate_edge(&'a self, e: &'a Self::Edge, e_prime: &'a Self::Edge) -> bool;
39    fn l_predicate_set(&'a self, x: &HashSet<&'a Self::Node>, y: &HashSet<&'a Self::Node>) -> bool;
40}
41
42pub trait HyperSimulation<'a>: Hypergraph<'a> {
43
44    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>>;
45    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>>;
46    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>>;
47    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>>;
48    fn get_hyper_simulation_naive(&'a self, other: &'a Self, delta: &impl Delta<'a, Node = Self::Node, Edge = Self::Edge>, d_match: &mut impl DMatch<'a, Edge = Self::Edge>) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
49}
50
51// struct MultiWriter<W1: Write, W2: Write> {
52//     w1: W1,
53//     w2: W2,
54// }
55
56// impl<W1: Write, W2: Write> Write for MultiWriter<W1, W2> {
57//     fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
58//         self.w1.write_all(buf)?;
59//         self.w2.write_all(buf)?;
60//         Ok(buf.len())
61//     }
62//     fn flush(&mut self) -> io::Result<()> {
63//         self.w1.flush()?;
64//         self.w2.flush()
65//     }
66// }
67
68
69impl<'a, H> HyperSimulation<'a> for H 
70where H: Hypergraph<'a> + Typed<'a> + LPredicate<'a> + ContainedHyperedge<'a> {
71    fn get_simulation_fixpoint(&'a self, other: &'a Self, l_match: &mut impl LMatch<Edge = Self::Edge>) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
72        todo!()
73    }
74
75    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>> {
76        todo!()
77    }
78
79    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>> {
80        
81        // let log_file = File::create("hyper-simulation.log")
82        //     .expect("Failed to create log file");
83        // let multi_writer = MultiWriter {
84        //     w1: log_file,
85        //     w2: io::stdout(),
86        // };
87        
88        // env_logger::Builder::new()
89        //     .target(env_logger::Target::Pipe(Box::new(multi_writer)))
90        //     .init();
91
92        init_global_logger_once("hyper-simulation.log");
93
94        info!("Start Naive Hyper Simulation");
95
96        let self_contained_hyperedge = self.get_hyperedges_list();
97        let other_contained_hyperedge = other.get_hyperedges_list();
98
99        let mut simulation: HashMap<&Self::Node, HashSet<&Self::Node>> = self.nodes().map(|u| {
100            let res = other.nodes().filter(|v| {
101                if self.type_same(u, *v) {
102                    // For each e, compute the union of l_match(u) over all matching e_prime,
103                    // then take the intersection across all e.
104                    let mut l_match_intersection: Option<HashSet<usize>> = None;
105                    for e in self.contained_hyperedges(&self_contained_hyperedge, u) {
106                        let mut l_match_union: HashSet<usize> = HashSet::new();
107                        for e_prime in other.contained_hyperedges(&other_contained_hyperedge, v) {
108                            if self.l_predicate_edge(e, e_prime) {
109                                // let l_match = self.l_match(e, e_prime);
110                                let id_set = l_match.l_match_with_node_mut(e, e_prime, u.id());
111                                l_match_union = l_match_union.union(&id_set).copied().collect();
112                            }
113                        }
114                        l_match_intersection = match l_match_intersection {
115                            Some(ref acc) => Some(acc.intersection(&l_match_union).copied().collect()),
116                            None => Some(l_match_union),
117                        };
118                    }
119                    if let Some(l_match_intersection) = l_match_intersection {
120                        if l_match_intersection.contains(&v.id()){
121                            return true;
122                        }
123                    }
124                }
125                false
126            }).collect();
127            (u, res)
128        }).collect();
129
130        info!("END Initial, sim: is ");
131        for (u, v_set) in &simulation {
132            info!("\tsim({}) = {:?}", u.id(), v_set.iter().map(|v| v.id()).collect::<Vec<_>>());
133        }
134        
135
136        let mut changed = true;
137        while changed {
138            changed = false;
139            for u in self.nodes() {
140                let mut need_delete = Vec::new();
141                for v in simulation.get(u).unwrap() {
142                    info!("Checking {} -> {}", u.id(), v.id());
143                    let mut _delete = true;
144                    for e in self.contained_hyperedges(&self_contained_hyperedge, u) {
145                        if !_delete {
146                            break;
147                        }
148                        for e_prime in other.contained_hyperedges(&other_contained_hyperedge, v) {
149                            if self.l_predicate_edge(e, e_prime) {
150                                if l_match.dom(e, e_prime).all(|u_prime| {
151                                    l_match.l_match_with_node(e, e_prime, u_prime.clone()).iter().map(|id| {other.get_node_by_id(*id)}).any(|v_prime| {
152                                        if let Some(v_prime) = v_prime {
153                                            return simulation.get(u).unwrap().contains(v_prime);
154                                        } else {
155                                            return false;
156                                        }
157                                    })
158                                }) {
159                                    info!("Keeping {} -> {}", u.id(), v.id());
160                                    _delete = false;
161                                    break;
162                                }
163                            }
164                        }
165                    }
166                    if _delete {
167                        info!("Deleting {} -> {}", u.id(), v.id());
168                        need_delete.push(v.clone());
169                    }
170                }
171                for v in need_delete {
172                    simulation.get_mut(u).unwrap().remove(v);
173                    changed = true;
174                }
175            }
176        }
177
178        simulation
179    }
180
181    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>> {
182        init_global_logger_once("hyper-simulation.log");
183
184        info!("Start Naive Hyper Simulation");
185
186        // let self_contained_hyperedge = self.get_hyperedges_list();
187        // let other_contained_hyperedge = other.get_hyperedges_list();
188
189        let mut l_predicate_edges: HashMap<(usize, usize), Vec<(&Self::Edge, &Self::Edge)>> = HashMap::new();
190        for e in self.hyperedges() {
191            for e_prime in other.hyperedges() {
192                if self.l_predicate_edge(e, e_prime) {
193                    for u in e.id_set() {
194                        for v in e_prime.id_set() {
195                            l_predicate_edges.entry((u, v)).or_default().push((e, e_prime));
196                        }
197                    }
198                }
199            }
200        }
201
202        let mut simulation: HashMap<&'a Self::Node, HashSet<&'a Self::Node>> = self.nodes().map(|u| {
203            let res = other.nodes().filter(|v| {
204                if self.type_same(u, *v) {
205                    if let Some(edge_pairs) = l_predicate_edges.get(&(u.id(), v.id())) {
206                        for (e, e_prime) in edge_pairs {
207                            let id_set = l_match.l_match_with_node(e, e_prime, u.id());
208                            if !id_set.contains(&v.id()) {
209                                return false;
210                            }
211                        }
212                        return true;
213                    } else {
214                        return true;
215                    }
216                }
217                false
218            }).collect();
219            (u, res)
220        }).collect();
221
222        info!("END Initial, sim: is ");
223        for (u, v_set) in &simulation {
224            info!("\tsim({}) = {:?}", u.id(), v_set.iter().map(|v| v.id()).collect::<Vec<_>>());
225        }
226        
227
228        let mut changed = true;
229        while changed {
230            changed = false;
231            for u in self.nodes() {
232                let mut need_delete = Vec::new();
233                for v in simulation.get(u).unwrap() {
234                    info!("Checking {} -> {}", u.id(), v.id());
235                    let mut _delete = false;
236
237                    if let Some(edge_pairs) = l_predicate_edges.get(&(u.id(), v.id())) {
238                        for (e, e_prime) in edge_pairs {
239                            if l_match.dom(e, e_prime).all(|u_prime| {
240                                l_match.l_match_with_node(e, e_prime, u_prime.clone()).iter().map(|id| {other.get_node_by_id(*id)}).any(|v_prime| {
241                                    if let Some(v_prime) = v_prime {
242                                        return simulation.get(u).unwrap().contains(v_prime);
243                                    } else {
244                                        return false;
245                                    }
246                                })
247                            }) {
248                                info!("Keeping {} -> {}", u.id(), v.id());
249                                _delete = true;
250                                break;
251                            }
252                        }
253                    }
254
255                    if _delete {
256                        info!("Deleting {} -> {}", u.id(), v.id());
257                        need_delete.push(v.clone());
258                    }
259                }
260
261                for v in need_delete {
262                    simulation.get_mut(u).unwrap().remove(v);
263                    changed = true;
264                }
265            }
266        }
267
268        simulation
269
270    }
271
272    fn get_hyper_simulation_naive(&'a self, other: &'a Self, delta: &impl Delta<'a, Node = Self::Node, Edge = Self::Edge>, d_match: &mut impl DMatch<'a, Edge = Self::Edge>) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
273        init_global_logger_once("hyper-simulation.log");
274
275        let mut simulation: HashMap<&'a Self::Node, HashSet<&'a Self::Node>> = self.nodes().map(|u| {
276            let res = other.nodes().filter(|v| {
277                if self.type_same(u, *v) {
278                    let sematic_clusters = delta.get_sematic_clusters(u, v);
279                    for (cluster_u, cluster_v) in sematic_clusters {
280                        let d_match_set = d_match.d_match_mut(cluster_u, cluster_v);
281                        if !d_match_set.contains(&(u.id(), v.id())) {
282                            return false;
283                        }
284                    }
285                    return true;
286                }
287                false
288            }).collect();
289            (u, res)
290        }).collect();
291
292        info!("END Initial, sim: is ");
293        for (u, v_set) in &simulation {
294            info!("\tsim({}) = {:?}", u.id(), v_set.iter().map(|v| v.id()).collect::<Vec<_>>());
295        }
296
297        let mut simulation_by_id: HashSet<(usize, usize)> = simulation.iter().flat_map(|(u, v_set)| {
298            v_set.iter().map(move |v| (u.id(), v.id()))
299        }).collect();
300
301        let mut changed = true;
302        while changed {
303            changed = false;
304            for u in self.nodes() {
305                let mut need_delete = Vec::new();
306                for v in simulation.get(u).unwrap() {
307                    info!("Checking {} -> {}", u.id(), v.id());
308                    let mut _delete = false;
309
310                    let sematic_clusters = delta.get_sematic_clusters(u, v);
311                    for (cluster_u, cluster_v) in sematic_clusters {
312                        let d_relation = d_match.d_match(cluster_u, cluster_v);
313                        // 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
314                        if !d_relation.is_subset(&simulation_by_id) {
315                            info!("Keeping {} -> {}", u.id(), v.id());
316                            _delete = true;
317                            break;
318                        }
319                    }
320
321                    if _delete {
322                        info!("Deleting {} -> {}", u.id(), v.id());
323                        need_delete.push(v.clone());
324                    }
325                }
326
327                for v in need_delete {
328                    simulation.get_mut(u).unwrap().remove(v);
329                    simulation_by_id.remove(&(u.id(), v.id()));
330                    changed = true;
331                }
332            }
333        }
334
335        return simulation;
336    }
337}
graph_simulation/algorithm/hyper_simulation.rs

graph_simulation/algorithm/
hyper_simulation.rs
