graph_simulation/algorithm/
hyper_simulation.rs

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

graph_simulation/algorithm/
hyper_simulation.rs
