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