graph_base/interfaces/
hypergraph.rs

1use std::{collections::HashMap, fmt::Display};
2use crate::interfaces::graph::SingleId;
3use crate::interfaces::edge::Hyperedge;
4
5use super::{edge::DirectedHyperedge, vertex::Vertex};
6
7pub trait IdVector {
8    fn id(&self) -> Vec<usize>;
9}
10
11pub trait Hypergraph<'a> {
12    type Node: Vertex;
13    type Edge: Hyperedge;
14    fn new() -> Self;
15    fn nodes(&'a self) -> impl Iterator<Item = &'a Self::Node>;
16    fn hyperedges(&'a self) -> impl Iterator<Item = &'a Self::Edge>;
17    fn get_hyperedges_vector(&'a self) -> impl Iterator<Item = Vec<&'a Self::Node>> {
18        let id_map: HashMap<_, _> = HashMap::from_iter(self.nodes().map(|node| (node.id(), node)));
19        self.hyperedges().map(move |edge| edge.id().iter().map(|id| id_map.get(id).unwrap()).cloned().collect::<Vec<_>>()).collect::<Vec<_>>().into_iter()
20    }
21    fn get_hyperedges_vector_with_edge(&'a self) -> impl Iterator<Item = (&'a Self::Edge, Vec<&'a Self::Node>)> {
22        let id_map: HashMap<_, _> = HashMap::from_iter(self.nodes().map(|node| (node.id(), node)));
23        self.hyperedges().map(move |edge| (edge, edge.id().iter().map(|id| id_map.get(id).unwrap()).cloned().collect::<Vec<_>>())).collect::<Vec<_>>().into_iter()
24    }
25
26    fn get_node_by_id(&'a self, id: usize) -> Option<&'a Self::Node>;
27
28    fn add_node(&mut self, node: Self::Node);
29    fn add_hyperedge(&mut self, edge: Self::Edge);
30}
31
32
33pub struct AdjacencyList<'a, T: Hypergraph<'a>>(HashMap<&'a T::Node, Vec<&'a T::Node>>);
34
35impl<'a, T> Display for AdjacencyList<'a, T> 
36where 
37    T: Hypergraph<'a> {    
38    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
39        let mut s = String::new();
40        for (node, adj) in self.0.iter() {
41            
42            let s1 = format!("{}", node);
43            let mut s2 = String::new();
44            for node in adj {
45                s2.push_str(format!("{}, ", node).as_str());
46            }
47
48            s.push_str(format!("Node {} -> {{{}}}\n", s1, s2).as_str());
49        }
50        write!(f, "{}", s)
51    }
52}
53
54pub trait DirectedHypergraph<'a>: Hypergraph<'a> + Sized 
55where 
56    Self::Edge: DirectedHyperedge {}
57
58pub trait Neighbor<'a>: Hypergraph<'a> + Sized {
59    fn get_neighbors(&'a self) -> AdjacencyList<'a, Self> {
60        let mut adj = HashMap::new();
61        for node in self.nodes() {
62            adj.insert(node, Vec::new());
63        }
64        for edge in self.hyperedges() {
65            let nodes = edge.id();
66            for i in 0..nodes.len() {
67                for j in (i + 1)..nodes.len() {
68                    let node1 = self.nodes().find(|node| node.id() == nodes[i]).unwrap();
69                    let node2 = self.nodes().find(|node| node.id() == nodes[j]).unwrap();
70                    adj.get_mut(node1).unwrap().push(node2);
71                    adj.get_mut(node2).unwrap().push(node1);
72                }
73            }
74        }
75        AdjacencyList(adj)
76    }
77
78    fn neighbors(&'a self, adj: &AdjacencyList<'a, Self>, node: &Self::Node) -> impl Iterator<Item = &'a Self::Node> {
79        adj.0.get(node).unwrap().iter().cloned()
80    }
81}
82
83pub trait Precursor<'a>: DirectedHypergraph<'a>
84where
85    Self::Edge: DirectedHyperedge, {
86    fn get_precursor(&'a self) -> AdjacencyList<'a, Self> {
87        let mut adj = HashMap::new();
88        for node in self.nodes() {
89            adj.insert(node, Vec::new());
90        }
91        for edge in self.hyperedges() {
92            let nodes = edge.id();
93            for i in 0..nodes.len() {
94                for j in (i + 1)..nodes.len() {
95                    let node1 = self.nodes().find(|node| node.id() == nodes[i]).unwrap();
96                    let node2 = self.nodes().find(|node| node.id() == nodes[j]).unwrap();
97                    adj.get_mut(node2).unwrap().push(node1);
98                }
99            }
100        }
101        AdjacencyList(adj)
102    }
103}
104
105pub trait Successor<'a>: DirectedHypergraph<'a>
106where
107    Self::Edge: DirectedHyperedge, {
108    fn get_postcursor(&'a self) -> AdjacencyList<'a, Self> {
109        let mut adj = HashMap::new();
110        for node in self.nodes() {
111            adj.insert(node, Vec::new());
112        }
113        for edge in self.hyperedges() {
114            let nodes = edge.id();
115            for i in 0..nodes.len() {
116                for j in (i + 1)..nodes.len() {
117                    let node1 = self.nodes().find(|node| node.id() == nodes[i]).unwrap();
118                    let node2 = self.nodes().find(|node| node.id() == nodes[j]).unwrap();
119                    adj.get_mut(node1).unwrap().push(node2);
120                }
121            }
122        }
123        AdjacencyList(adj)
124    }
125}
126
127pub struct HyperedgeList<'a, T: Hypergraph<'a>>(HashMap<&'a T::Node, Vec<&'a T::Edge>>);
128
129impl<'a, T> Display for HyperedgeList<'a, T> 
130where 
131    T: Hypergraph<'a> {    
132    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
133        let mut s = String::new();
134        for (node, edges) in self.0.iter() {
135            
136            let s1 = format!("{}", node);
137            let mut s2 = String::new();
138            for edge in edges {
139                // s2.push_str(format!("{}, ", edge).as_str());
140            }
141
142            s.push_str(format!("Node {} -> {{{}}}\n", s1, s2).as_str());
143        }
144        write!(f, "{}", s)
145    }
146}
147
148pub trait ContainedHyperedge<'a>: Hypergraph<'a> + Sized {
149    fn get_hyperedges_list(&'a self) -> HyperedgeList<'a, Self> {
150        let mut adj = HashMap::new();
151        for node in self.nodes() {
152            adj.insert(node, Vec::new());
153        }
154        for edge in self.hyperedges() {
155            let nodes = edge.id();
156            for i in 0..nodes.len() {
157                let node = self.nodes().find(|node| node.id() == nodes[i]).unwrap();
158                adj.get_mut(node).unwrap().push(edge);
159            }
160        }
161        HyperedgeList(adj)
162    }
163
164    fn contained_hyperedges(&'a self, adj: &HyperedgeList<'a, Self>, node: &Self::Node) -> impl Iterator<Item = &'a Self::Edge> {
165        adj.0.get(node).unwrap().iter().cloned()
166    }
167}
168pub trait ContainedDirectedHyperedge<'a>: DirectedHypergraph<'a> + Sized
169where 
170    Self::Edge: DirectedHyperedge {
171    fn contained_hyperedges(&'a self, adj: &HyperedgeList<'a, Self>, node: &Self::Node) -> impl Iterator<Item = &'a Self::Edge> {
172        adj.0.get(node).unwrap().iter().cloned()
173    }
174
175    fn get_hyperedges_src(&'a self) -> HyperedgeList<'a, Self> {
176        let mut adj = HashMap::new();
177        for node in self.nodes() {
178            adj.insert(node, Vec::new());
179        }
180        for edge in self.hyperedges() {
181            for id in edge.src() {
182                let node = self.nodes().find(|node| node.id() == id).unwrap();
183                adj.get_mut(node).unwrap().push(edge);
184            }
185        }
186        HyperedgeList(adj)
187    }
188    fn get_hyperedges_dst(&'a self) -> HyperedgeList<'a, Self> {
189        let mut adj = HashMap::new();
190        for node in self.nodes() {
191            adj.insert(node, Vec::new());
192        }
193        for edge in self.hyperedges() {
194            for id in edge.dst() {
195                let node = self.nodes().find(|node| node.id() == id).unwrap();
196                adj.get_mut(node).unwrap().push(edge);
197            }    
198        }
199        HyperedgeList(adj)
200    }
201    
202}
graph_base/interfaces/hypergraph.rs

graph_base/interfaces/
hypergraph.rs
