graph_simulation/algorithm/
hyper_simulation.rs1use 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_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 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 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 todo!()
179 }
180}