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(&'a self, e: &'a Self::Edge, e_prime: &'a Self::Edge, u: &'a Self::Node) -> &'a HashSet<&'a Self::Node>;
8    fn dom(&'a self, e: &'a Self::Edge, e_prime: &'a Self::Edge) -> impl Iterator<Item = &'a Self::Node>;
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).iter().map(|v_prime| v_prime.id()).collect::<HashSet<_>>();
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).all(|u_prime| {
85                                    self.l_match_with_node(e, e_prime, u_prime).iter().any(|v_prime| {
86                                        simulation.get(u).unwrap().contains(v_prime)
87                                    })
88                                }) {
89                                    _delete = false;
90                                    break;
91                                }
92                            }
93                        }
94                    }
95                    if _delete {
96                        need_delete.push(v.clone());
97                    }
98                }
99                for v in need_delete {
100                    simulation.get_mut(u).unwrap().remove(v);
101                    changed = true;
102                }
103            }
104        }
105
106        simulation
107    }
108}
109
110pub trait DiHyperSimulation<'a> {
111    type Node;
112
113    fn get_simulation_fixpoint(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
114    fn get_simulation_recursive(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
115    fn get_simulation_native(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>>;
116}
117
118impl<'a, H> DiHyperSimulation<'a> for H 
119where 
120    H: DirectedHypergraph<'a> + Typed<'a> + LMatch<'a> + LPredicate<'a> + ContainedDirectedHyperedge<'a>,
121    H::Node: Type, H::Edge: DirectedHyperedge {
122    type Node = H::Node;
123
124    fn get_simulation_fixpoint(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
125        todo!()
126    }
127
128    fn get_simulation_recursive(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
129        todo!()
130    }
131
132    fn get_simulation_native(&'a self, other: &'a Self) -> HashMap<&'a Self::Node, HashSet<&'a Self::Node>> {
133        // let mut simulation: HashMap<&'a Self::Node, HashSet<&'a Self::Node>> = self.nodes().map(|u| {
134        //     let res = other.nodes().filter(|v| {
135        //         self.type_same(u, *v)
136        //     }).collect();
137        //     (u, res)
138        // }).collect();
139
140        // let self_contained_hyperedge = self.get_hyperedges_src();
141        // let other_contained_hyperedge = other.get_hyperedges_src();
142
143        // let mut changed = false;
144        // while !changed {
145        //     for u in self.nodes() {
146        //         let mut need_delete = Vec::new();
147        //         for v in simulation.get(u).unwrap() {
148        //             let mut _delete = true;
149        //             for e in self.contained_hyperedges(&self_contained_hyperedge, u) {
150        //                 if !_delete {
151        //                     break;
152        //                 }
153        //                 for e_prime in other.contained_hyperedges(&other_contained_hyperedge, v) {
154        //                     if self.l_predicate_edge(e, e_prime) {
155        //                         let l_match = self.l_match(e, e_prime);
156        //                         if l_match(u).id() == v.id() 
157        //                             && self.dom(l_match).all(|u_prime| {
158        //                                 simulation.get(u).unwrap().contains(&u_prime)
159        //                         }) {
160        //                             _delete = false;
161        //                             break;
162        //                         }
163        //                     }
164        //                 }
165        //             }
166        //             if _delete {
167        //                 need_delete.push(v.clone());
168        //             }
169        //         }
170        //         for v in need_delete {
171        //             simulation.get_mut(u).unwrap().remove(v);
172        //             changed = true;
173        //         }
174        //     }
175        // }
176
177        // simulation
178        todo!()
179    }
180}