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 {
6    type Edge;
7    // fn l_match(&'a self, e: &'a Self::Edge, e_prime: &'a Self::Edge) -> HashMap<&'a Self::Node, &'a HashSet<&'a Self::Node>>;
8    fn new() -> Self;
9    fn l_match_with_node_mut(&mut self, e: &Self::Edge, e_prime: &Self::Edge, u: usize) -> &HashSet<usize>;
10    fn l_match_with_node(&self, e: &Self::Edge, e_prime: &Self::Edge, u: usize) -> &HashSet<usize>;
11    fn dom(&self, e: &Self::Edge, e_prime: &Self::Edge) -> impl Iterator<Item = &usize>;
12}
13
14pub trait LPredicate<'a>: Hypergraph<'a> {
15    fn l_predicate_node(&'a self, u: &'a Self::Node, v: &'a Self::Node) -> bool;
16    fn l_predicate_edge(&'a self, e: &'a Self::Edge, e_prime: &'a Self::Edge) -> bool;
17    fn l_predicate_set(&'a self, x: &HashSet<&'a Self::Node>, y: &HashSet<&'a Self::Node>) -> bool;
18}
19
20pub trait HyperSimulation<'a>: Hypergraph<'a> {
21
22    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>>;
23    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>>;
24    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>>;
25}
26
27impl<'a, H> HyperSimulation<'a> for H 
28where H: Hypergraph<'a> + Typed<'a> + LPredicate<'a> + ContainedHyperedge<'a> {
29    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>> {
30        todo!()
31    }
32
33    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>> {
34        todo!()
35    }
36
37    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>> {
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 = l_match.l_match_with_node_mut(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 l_match.dom(e, e_prime).all(|u_prime| {
85                                    l_match.l_match_with_node(e, e_prime, u_prime.clone()).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
114// pub 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
122// impl<'a, H> DiHyperSimulation<'a> for H 
123// where 
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// }
graph_simulation/algorithm/hyper_simulation.rs

graph_simulation/algorithm/
hyper_simulation.rs
