graph_simulation/algorithm/
simulation.rs

1use graph_base::interfaces::graph::{Adjacency, AdjacencyInv, Graph, Directed};
2use graph_base::interfaces::labeled::{Labeled, LabeledAdjacency};
3
4use std::cell::RefCell;
5use std::collections::{HashSet, HashMap};
6pub trait Simulation<'a> {
7    type Node: 'a;
8
9    fn get_simulation(&'a self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
10
11    fn get_simulation_inter(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
12
13    fn get_simulation_native(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
14
15    fn get_simulation_of_node_edge(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
16
17    fn get_simulation_of_edge(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
18    
19    fn has_simulation(sim: HashMap<&'a Self::Node, HashSet<&'a Self::Node>>) -> bool;
20}
21
22impl<'a, 'b, T> Simulation<'a> for T
23where 
24    T: Graph<'a> + Adjacency<'a> + AdjacencyInv<'a> + Labeled<'a> + Directed + LabeledAdjacency<'a>,
25    T::Node: 'a, T::Edge: 'a,
26    'b: 'a
27{
28    type Node = T::Node;
29
30    fn get_simulation(&'a self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
31        let mut simulation: HashMap<&'a <T as Graph<'_>>::Node, HashSet<&'a <T as Graph<'_>>::Node>> = HashMap::new();
32        let remove = RefCell::new(HashMap::new());
33        let (adj, adj_inv) = (self.get_adj(), self.get_adj_inv());
34
35        let pre_V = self.nodes().map(|v| self.get_post(&adj, v).collect::<HashSet<_>>()).reduce(|acc, x| acc.union(&x).cloned().collect()).unwrap();
36
37        for v in self.nodes() {
38            let sim_v: HashSet<_> = if self.get_post(&adj, v).count() != 0 {
39                self.nodes().filter(|u| self.label_same(v, u)).collect()
40            } else {
41                self.nodes().filter(|u| self.label_same(v, u) && self.get_post(&adj,u).count() != 0).collect()
42            };
43            simulation.insert(v, sim_v.clone());
44
45            let pre_sim_v = sim_v.into_iter().map(|u| self.get_pre(&adj_inv, u).collect::<HashSet<_>>()).reduce(|acc, x| acc.union(&x).cloned().collect()).unwrap();
46            let res: HashSet<_> = pre_V.clone().into_iter().filter(|u| !pre_sim_v.contains(u)).collect();
47            remove.borrow_mut().insert(v, res);
48        }
49
50        let legal_v = || {
51            for v in self.nodes() {
52                if remove.borrow().get(v).unwrap().len() != 0 {
53                    return Some(v);
54                }
55            }
56            None
57        };
58
59        while let Some(v) = legal_v() {
60            for u in self.get_pre(&adj_inv,v) {
61                for w in remove.borrow().get(v).unwrap() {
62                    if simulation.get(u).unwrap().contains(w) {
63                        simulation.get_mut(u).unwrap().remove(w);
64                        for w_prime in self.get_pre(&adj_inv, w) {
65                            if self.get_post(&adj, w_prime).collect::<HashSet<_>>().intersection(simulation.get(u).unwrap()).count() == 0 {
66                                remove.borrow_mut().get_mut(u).unwrap().insert(w_prime);
67                            }
68                        }
69                    }
70
71                }
72            }
73            remove.borrow_mut().get_mut(v).unwrap().clear();
74        }
75
76        simulation
77    }
78
79    fn get_simulation_inter(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
80        let mut simulation: HashMap<&'a <T as Graph<'_>>::Node, HashSet<&'a <T as Graph<'_>>::Node>> = HashMap::new();
81        let remove = RefCell::new(HashMap::new());
82        let (adj, adj_inv) = (self.get_adj(), self.get_adj_inv());
83        let (adj_other, adj_inv_other) = (other.get_adj(), other.get_adj_inv());
84
85        let pre_V = other.nodes().map(|v| other.get_pre(&adj_inv_other, v).collect::<HashSet<_>>()).reduce(|acc, x| acc.union(&x).cloned().collect()).unwrap();
86        
87        for v in self.nodes() {
88            let sim_v: HashSet<_> = if self.get_post(&adj, v).count() == 0 {
89                other.nodes().filter(|u| self.label_same(v, u)).collect()
90            } else {
91                other.nodes().filter(|u| self.label_same(v, u) && other.get_post(&adj_other,u).count() != 0).collect()
92            };
93            simulation.insert(v, sim_v.clone());
94            
95            let pre_sim_v = sim_v.clone().iter().map(|u| other.get_pre(&adj_inv_other, u).collect::<HashSet<_>>()).reduce(|acc, x| acc.union(&x).cloned().collect()).unwrap_or(HashSet::new());
96            let res: HashSet<_> = pre_V.difference(&pre_sim_v).copied().collect();
97            remove.borrow_mut().insert(v, res);
98        }   
99
100        let legal_v = || {
101            for v in self.nodes() {
102                if remove.borrow().get(v).unwrap().len() != 0 {
103                    return Some(v);
104                }
105            }
106            None
107        };
108
109        while let Some(v) = legal_v() {
110            for u in self.get_pre(&adj_inv,v) {
111                let mut remove_u_add = HashSet::new();
112                for w in remove.borrow().get(v).unwrap() {
113                    if simulation.get(u).unwrap().contains(w) {
114                        simulation.get_mut(u).unwrap().remove(w);
115                        for w_prime in other.get_pre(&adj_inv_other, w) {
116                            if other.get_post(&adj_other, w_prime).collect::<HashSet<_>>().intersection(simulation.get(u).unwrap()).count() == 0 {
117                                remove_u_add.insert(w_prime);
118                            }
119                        }
120                    }
121                }
122                remove.borrow_mut().get_mut(u).unwrap().extend(remove_u_add);
123            }
124            remove.borrow_mut().get_mut(v).unwrap().clear();
125        }
126        simulation
127    }
128
129    fn get_simulation_native(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
130        let mut simulation: HashMap<&'a <T as Graph<'_>>::Node, HashSet<&'a <T as Graph<'_>>::Node>> = HashMap::new();
131        let (adj_other, _) = (other.get_adj(), other.get_adj_inv());
132        
133        for v in self.nodes() {
134            let sim_v: HashSet<_> = other.nodes().filter(|u| self.label_same(v, u)).collect();
135            simulation.insert(v, sim_v.clone());
136        }
137
138        let mut changed = true;
139        while changed {
140            changed = false;
141            for (u, u_prime) in self.get_edges_pair() {
142                let mut sim_u_remove = HashSet::new();
143                for v in simulation.get(u).unwrap() {
144                    let mut v_need_remove = true;
145                    for v_prime in other.get_post(&adj_other, v) {
146                        if simulation.get(u_prime).unwrap().contains(v_prime) {
147                            v_need_remove = false;
148                            break;
149                        }
150                    }
151                    if v_need_remove {
152                        sim_u_remove.insert(v.clone());
153                        changed = true;
154                    }
155                }
156                for v in sim_u_remove {
157                    simulation.get_mut(u).unwrap().remove(v);
158                }
159            }
160        }
161
162        
163        simulation
164    }
165
166    fn get_simulation_of_node_edge(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
167        let mut simulation: HashMap<&'a <T as Graph<'_>>::Node, HashSet<&'a <T as Graph<'_>>::Node>> = HashMap::new();
168        let (adj_other, _) = (other.get_labeled_adj(), other.get_adj_inv());
169        
170        for v in self.nodes() {
171            let sim_v: HashSet<_> = other.nodes().filter(|u| self.label_same(v, u)).collect();
172            simulation.insert(v, sim_v.clone());
173        }
174
175        let mut changed = true;
176        while changed {
177            changed = false;
178            for (u,  u_edge, u_prime) in self.get_edges_pair_with_edge() {
179                let mut sim_u_remove = HashSet::new();
180                for v in simulation.get(u).unwrap() {
181                    let mut v_need_remove = true;
182                    for (v_prime, v_edge) in other.get_labeled_post(&adj_other, v) {
183                        if self.edge_label_same(u_edge, v_edge) && simulation.get(u_prime).unwrap().contains(v_prime) {
184                            v_need_remove = false;
185                            break;
186                        }
187                    }
188                    if v_need_remove {
189                        sim_u_remove.insert(v.clone());
190                        changed = true;
191                    }
192                }
193                for v in sim_u_remove {
194                    simulation.get_mut(u).unwrap().remove(v);
195                }
196            }
197        }
198
199        
200        simulation
201    }
202
203    fn get_simulation_of_edge(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
204        let mut simulation: HashMap<&'a <T as Graph<'_>>::Node, HashSet<&'a <T as Graph<'_>>::Node>> = HashMap::new();
205        let (adj_other, _) = (other.get_labeled_adj(), other.get_adj_inv());
206        
207        for v in self.nodes() {
208            let sim_v: HashSet<_> = other.nodes().collect();
209            simulation.insert(v, sim_v.clone());
210        }
211
212        let mut changed = true;
213        while changed {
214            changed = false;
215            for (u,  u_edge, u_prime) in self.get_edges_pair_with_edge() {
216                let mut sim_u_remove = HashSet::new();
217                for v in simulation.get(u).unwrap() {
218                    let mut v_need_remove = true;
219                    for (v_prime, v_edge) in other.get_labeled_post(&adj_other, v) {
220                        if self.edge_node_label_same(u, u_edge, u_prime, v, v_edge, v_prime) && simulation.get(u_prime).unwrap().contains(v_prime) {
221                            v_need_remove = false;
222                            break;
223                        }
224                    }
225                    if v_need_remove {
226                        sim_u_remove.insert(v.clone());
227                        changed = true;
228                    }
229                }
230                for v in sim_u_remove {
231                    simulation.get_mut(u).unwrap().remove(v);
232                }
233            }
234        }
235
236        
237        simulation
238    }
239
240    fn has_simulation(sim: HashMap<&'a Self::Node, HashSet<&'a Self::Node>>) -> bool {
241        sim.iter().all(|(_, sim_v)| {
242            sim_v.len() != 0
243        })
244    }
245}
246
247pub trait HyperSimulation<'a> {
248    type Node: 'a;
249
250    fn get_hyper_simulation_inter(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
251}
graph_simulation/algorithm/simulation.rs

graph_simulation/algorithm/
simulation.rs
