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(&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 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.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 todo!()
183 }
184}