graph_simulation/algorithm/hyper_simulation.rs
1use std::collections::{HashMap, HashSet};
2use log::{info, warn};
3use std::fs::File;
4use std::io::{self, Write};
5
6use graph_base::interfaces::{edge::DirectedHyperedge, graph::SingleId, hypergraph::{ContainedDirectedHyperedge, ContainedHyperedge, DirectedHypergraph, Hypergraph}, typed::{Type, Typed}};
7
8pub trait LMatch {
9 type Edge;
10 // fn l_match(&'a self, e: &'a Self::Edge, e_prime: &'a Self::Edge) -> HashMap<&'a Self::Node, &'a HashSet<&'a Self::Node>>;
11 fn new() -> Self;
12 fn l_match_with_node_mut(&mut self, e: &Self::Edge, e_prime: &Self::Edge, u: usize) -> &HashSet<usize>;
13 fn l_match_with_node(&self, e: &Self::Edge, e_prime: &Self::Edge, u: usize) -> &HashSet<usize>;
14 fn dom(&self, e: &Self::Edge, e_prime: &Self::Edge) -> impl Iterator<Item = &usize>;
15}
16
17pub trait LPredicate<'a>: Hypergraph<'a> {
18 fn l_predicate_node(&'a self, u: &'a Self::Node, v: &'a Self::Node) -> bool;
19 fn l_predicate_edge(&'a self, e: &'a Self::Edge, e_prime: &'a Self::Edge) -> bool;
20 fn l_predicate_set(&'a self, x: &HashSet<&'a Self::Node>, y: &HashSet<&'a Self::Node>) -> bool;
21}
22
23pub trait HyperSimulation<'a>: Hypergraph<'a> {
24
25 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>>;
26 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>>;
27 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>>;
28}
29
30struct MultiWriter<W1: Write, W2: Write> {
31 w1: W1,
32 w2: W2,
33}
34
35impl<W1: Write, W2: Write> Write for MultiWriter<W1, W2> {
36 fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
37 self.w1.write_all(buf)?;
38 self.w2.write_all(buf)?;
39 Ok(buf.len())
40 }
41 fn flush(&mut self) -> io::Result<()> {
42 self.w1.flush()?;
43 self.w2.flush()
44 }
45}
46
47
48impl<'a, H> HyperSimulation<'a> for H
49where H: Hypergraph<'a> + Typed<'a> + LPredicate<'a> + ContainedHyperedge<'a> {
50 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>> {
51 todo!()
52 }
53
54 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>> {
55 todo!()
56 }
57
58 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>> {
59
60 let log_file = File::create("hyper-simulation.log")
61 .expect("Failed to create log file");
62 let multi_writer = MultiWriter {
63 w1: log_file,
64 w2: io::stdout(),
65 };
66
67 env_logger::Builder::new()
68 .target(env_logger::Target::Pipe(Box::new(multi_writer)))
69 .init();
70
71 info!("Start Naive Hyper Simulation");
72
73 let self_contained_hyperedge = self.get_hyperedges_list();
74 let other_contained_hyperedge = other.get_hyperedges_list();
75
76 let mut simulation: HashMap<&'a Self::Node, HashSet<&'a Self::Node>> = self.nodes().map(|u| {
77 let res = other.nodes().filter(|v| {
78 if self.type_same(u, *v) {
79 // For each e, compute the union of l_match(u) over all matching e_prime,
80 // then take the intersection across all e.
81 let mut l_match_intersection: Option<HashSet<usize>> = None;
82 for e in self.contained_hyperedges(&self_contained_hyperedge, u) {
83 let mut l_match_union: HashSet<usize> = HashSet::new();
84 for e_prime in other.contained_hyperedges(&other_contained_hyperedge, v) {
85 if self.l_predicate_edge(e, e_prime) {
86 // let l_match = self.l_match(e, e_prime);
87 let id_set = l_match.l_match_with_node_mut(e, e_prime, u.id());
88 l_match_union = l_match_union.union(&id_set).copied().collect();
89 }
90 }
91 l_match_intersection = match l_match_intersection {
92 Some(ref acc) => Some(acc.intersection(&l_match_union).copied().collect()),
93 None => Some(l_match_union),
94 };
95 }
96 if let Some(l_match_intersection) = l_match_intersection {
97 if l_match_intersection.contains(&v.id()){
98 return true;
99 }
100 }
101 }
102 false
103 }).collect();
104 (u, res)
105 }).collect();
106
107 info!("END Initial, sim: is ");
108 for (u, v_set) in &simulation {
109 info!("\tsim({}) = {:?}", u.id(), v_set.iter().map(|v| v.id()).collect::<Vec<_>>());
110 }
111
112
113 let mut changed = true;
114 while changed {
115 changed = false;
116 for u in self.nodes() {
117 let mut need_delete = Vec::new();
118 for v in simulation.get(u).unwrap() {
119 info!("Checking {} -> {}", u.id(), v.id());
120 let mut _delete = true;
121 for e in self.contained_hyperedges(&self_contained_hyperedge, u) {
122 if !_delete {
123 break;
124 }
125 for e_prime in other.contained_hyperedges(&other_contained_hyperedge, v) {
126 if self.l_predicate_edge(e, e_prime) {
127 if l_match.dom(e, e_prime).all(|u_prime| {
128 l_match.l_match_with_node(e, e_prime, u_prime.clone()).iter().map(|id| {other.get_node_by_id(*id)}).any(|v_prime| {
129 if let Some(v_prime) = v_prime {
130 return simulation.get(u).unwrap().contains(v_prime);
131 } else {
132 return false;
133 }
134 })
135 }) {
136 info!("Keeping {} -> {}", u.id(), v.id());
137 _delete = false;
138 break;
139 }
140 }
141 }
142 }
143 if _delete {
144 info!("Deleting {} -> {}", u.id(), v.id());
145 need_delete.push(v.clone());
146 }
147 }
148 for v in need_delete {
149 simulation.get_mut(u).unwrap().remove(v);
150 changed = true;
151 }
152 }
153 }
154
155 simulation
156 }
157}
158
159// pub trait DiHyperSimulation<'a> {
160// type Node;
161
162// fn get_simulation_fixpoint(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
163// fn get_simulation_recursive(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
164// fn get_simulation_native(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
165// }
166
167// impl<'a, H> DiHyperSimulation<'a> for H
168// where
169// H: DirectedHypergraph<'a> + Typed<'a> + LMatch<'a> + LPredicate<'a> + ContainedDirectedHyperedge<'a>,
170// H::Node: Type, H::Edge: DirectedHyperedge {
171// type Node = H::Node;
172
173// fn get_simulation_fixpoint(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
174// todo!()
175// }
176
177// fn get_simulation_recursive(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
178// todo!()
179// }
180
181// fn get_simulation_native(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
182// // let mut simulation: HashMap<&'a Self::Node, HashSet<&'a Self::Node>> = self.nodes().map(|u| {
183// // let res = other.nodes().filter(|v| {
184// // self.type_same(u, *v)
185// // }).collect();
186// // (u, res)
187// // }).collect();
188
189// // let self_contained_hyperedge = self.get_hyperedges_src();
190// // let other_contained_hyperedge = other.get_hyperedges_src();
191
192// // let mut changed = false;
193// // while !changed {
194// // for u in self.nodes() {
195// // let mut need_delete = Vec::new();
196// // for v in simulation.get(u).unwrap() {
197// // let mut _delete = true;
198// // for e in self.contained_hyperedges(&self_contained_hyperedge, u) {
199// // if !_delete {
200// // break;
201// // }
202// // for e_prime in other.contained_hyperedges(&other_contained_hyperedge, v) {
203// // if self.l_predicate_edge(e, e_prime) {
204// // let l_match = self.l_match(e, e_prime);
205// // if l_match(u).id() == v.id()
206// // && self.dom(l_match).all(|u_prime| {
207// // simulation.get(u).unwrap().contains(&u_prime)
208// // }) {
209// // _delete = false;
210// // break;
211// // }
212// // }
213// // }
214// // }
215// // if _delete {
216// // need_delete.push(v.clone());
217// // }
218// // }
219// // for v in need_delete {
220// // simulation.get_mut(u).unwrap().remove(v);
221// // changed = true;
222// // }
223// // }
224// // }
225
226// // simulation
227// todo!()
228// }
229// }