graph_simulation/algorithm/
simulation.rs

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

graph_simulation/algorithm/
simulation.rs
