graph_simulation/algorithm/
hyper_simulation.rs

1use std::collections::{HashMap, HashSet};
2
3use graph_base::interfaces::{edge::DirectedHyperedge, graph::SingleId, hypergraph::{ContainedDirectedHyperedge, ContainedHyperedge, DirectedHypergraph, Hypergraph}, typed::{Type, Typed}};
4
5pub trait LMatch<'a>: Hypergraph<'a> {
6    // fn l_match(&'a self, e: &'a Self::Edge, e_prime: &'a Self::Edge) -> HashMap<&'a Self::Node, &'a HashSet<&'a Self::Node>>;
7    fn l_match_with_node(&self, e: &Self::Edge, e_prime: &Self::Edge, u: usize) -> &HashSet<usize>;
8    fn dom(&self, e: &Self::Edge, e_prime: &Self::Edge) -> Vec<usize>;
9}
10
11pub trait LPredicate<'a>: Hypergraph<'a> {
12    fn l_predicate_node(&'a self, u: &'a Self::Node, v: &'a Self::Node) -> bool;
13    fn l_predicate_edge(&'a self, e: &'a Self::Edge, e_prime: &'a Self::Edge) -> bool;
14    fn l_predicate_set(&'a self, x: &HashSet<&'a Self::Node>, y: &HashSet<&'a Self::Node>) -> bool;
15}
16
17pub trait HyperSimulation<'a> {
18    type Node;
19
20    fn get_simulation_fixpoint(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
21    fn get_simulation_recursive(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
22    fn get_simulation_naive(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
23}
24
25impl<'a, H> HyperSimulation<'a> for H 
26where H: Hypergraph<'a> + Typed<'a> + LMatch<'a> + LPredicate<'a> + ContainedHyperedge<'a> {
27    type Node = H::Node;
28
29    fn get_simulation_fixpoint(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
30        todo!()
31    }
32
33    fn get_simulation_recursive(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
34        todo!()
35    }
36
37    fn get_simulation_naive(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
38        let self_contained_hyperedge = self.get_hyperedges_list();
39        let other_contained_hyperedge = other.get_hyperedges_list();
40
41        let mut simulation: HashMap<&'a Self::Node, HashSet<&'a Self::Node>> = self.nodes().map(|u| {
42            let res = other.nodes().filter(|v| {
43                if self.type_same(u, *v) {
44                    // For each e, compute the union of l_match(u) over all matching e_prime,
45                    // then take the intersection across all e.
46                    let mut l_match_intersection: Option<HashSet<usize>> = None;
47                    for e in self.contained_hyperedges(&self_contained_hyperedge, u) {
48                        let mut l_match_union: HashSet<usize> = HashSet::new();
49                        for e_prime in other.contained_hyperedges(&other_contained_hyperedge, v) {
50                            if self.l_predicate_edge(e, e_prime) {
51                                // let l_match = self.l_match(e, e_prime);
52                                let id_set = self.l_match_with_node(e, e_prime, u.id());
53                                l_match_union = l_match_union.union(&id_set).copied().collect();
54                            }
55                        }
56                        l_match_intersection = match l_match_intersection {
57                            Some(ref acc) => Some(acc.intersection(&l_match_union).copied().collect()),
58                            None => Some(l_match_union),
59                        };
60                    }
61                    if let Some(l_match_intersection) = l_match_intersection {
62                        if l_match_intersection.contains(&v.id()){
63                            return true;
64                        }
65                    }
66                }
67                false
68            }).collect();
69            (u, res)
70        }).collect();
71
72        let mut changed = false;
73        while !changed {
74            for u in self.nodes() {
75                let mut need_delete = Vec::new();
76                for v in simulation.get(u).unwrap() {
77                    let mut _delete = true;
78                    for e in self.contained_hyperedges(&self_contained_hyperedge, u) {
79                        if !_delete {
80                            break;
81                        }
82                        for e_prime in other.contained_hyperedges(&other_contained_hyperedge, v) {
83                            if self.l_predicate_edge(e, e_prime) {
84                                if self.dom(e, e_prime).iter().all(|u_prime| {
85                                    self.l_match_with_node(e, e_prime, *u_prime).iter().map(|id| {other.get_node_by_id(*id)}).any(|v_prime| {
86                                        if let Some(v_prime) = v_prime {
87                                            return simulation.get(u).unwrap().contains(v_prime);
88                                        } else {
89                                            return false;
90                                        }
91                                    })
92                                }) {
93                                    _delete = false;
94                                    break;
95                                }
96                            }
97                        }
98                    }
99                    if _delete {
100                        need_delete.push(v.clone());
101                    }
102                }
103                for v in need_delete {
104                    simulation.get_mut(u).unwrap().remove(v);
105                    changed = true;
106                }
107            }
108        }
109
110        simulation
111    }
112}
113
114pub trait DiHyperSimulation<'a> {
115    type Node;
116
117    fn get_simulation_fixpoint(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
118    fn get_simulation_recursive(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
119    fn get_simulation_native(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
120}
121
122impl<'a, H> DiHyperSimulation<'a> for H 
123where 
124    H: DirectedHypergraph<'a> + Typed<'a> + LMatch<'a> + LPredicate<'a> + ContainedDirectedHyperedge<'a>,
125    H::Node: Type, H::Edge: DirectedHyperedge {
126    type Node = H::Node;
127
128    fn get_simulation_fixpoint(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
129        todo!()
130    }
131
132    fn get_simulation_recursive(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
133        todo!()
134    }
135
136    fn get_simulation_native(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
137        // let mut simulation: HashMap<&'a Self::Node, HashSet<&'a Self::Node>> = self.nodes().map(|u| {
138        //     let res = other.nodes().filter(|v| {
139        //         self.type_same(u, *v)
140        //     }).collect();
141        //     (u, res)
142        // }).collect();
143
144        // let self_contained_hyperedge = self.get_hyperedges_src();
145        // let other_contained_hyperedge = other.get_hyperedges_src();
146
147        // let mut changed = false;
148        // while !changed {
149        //     for u in self.nodes() {
150        //         let mut need_delete = Vec::new();
151        //         for v in simulation.get(u).unwrap() {
152        //             let mut _delete = true;
153        //             for e in self.contained_hyperedges(&self_contained_hyperedge, u) {
154        //                 if !_delete {
155        //                     break;
156        //                 }
157        //                 for e_prime in other.contained_hyperedges(&other_contained_hyperedge, v) {
158        //                     if self.l_predicate_edge(e, e_prime) {
159        //                         let l_match = self.l_match(e, e_prime);
160        //                         if l_match(u).id() == v.id() 
161        //                             && self.dom(l_match).all(|u_prime| {
162        //                                 simulation.get(u).unwrap().contains(&u_prime)
163        //                         }) {
164        //                             _delete = false;
165        //                             break;
166        //                         }
167        //                     }
168        //                 }
169        //             }
170        //             if _delete {
171        //                 need_delete.push(v.clone());
172        //             }
173        //         }
174        //         for v in need_delete {
175        //             simulation.get_mut(u).unwrap().remove(v);
176        //             changed = true;
177        //         }
178        //     }
179        // }
180
181        // simulation
182        todo!()
183    }
184}