graph_base/impls/
standard.rs

1use std::collections::HashMap;
2use std::fmt::Display;
3
4use crate::interfaces::labeled::{Label, Labeled, HyperLabeled, LabeledAdjacency};
5use crate::interfaces::graph::{SingleId, IdPair, Graph, Adjacency, AdjacencyInv, Directed};
6use crate::interfaces::vertex::Vertex;
7
8#[derive(Hash, Eq, PartialEq, Clone)]
9pub struct LabelNode<L: Label> {
10    id: u64,
11    label: L
12}
13
14impl<L: Label> Display for LabelNode<L> 
15where L: Label {
16    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
17        write!(f, "[id: {}, label: {}]", self.id, self.label)
18    }
19}
20
21impl<L: Label> SingleId for LabelNode<L> {
22    fn id(&self) -> usize {
23        self.id as usize
24    }
25}
26
27impl<L: Label> Label for LabelNode<L> {
28    fn label(&self) -> &str {
29        self.label.label()
30    }
31}
32
33#[derive(Hash, Eq, PartialEq, Clone)]
34pub struct LabeledEdge<L: Label> {
35    src: u64,
36    dst: u64,
37    label: L,
38}
39
40impl<L: Label> IdPair for LabeledEdge<L> {
41    fn pair(&self) -> (usize, usize) {
42        (self.src as usize, self.dst as usize)
43    }
44    
45}
46
47impl<L: Label> Display for LabeledEdge<L> {
48    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
49        write!(f, "[{} -> {}: label: {}]", self.src, self.dst, self.label)
50    }
51}
52
53impl<L: Label> Label for LabeledEdge<L> {
54    fn label(&self) -> &str {
55        self.label.label()
56    }
57}
58
59/// `L1` is the label of the nodes, `L2` is the label of the edges. All these labels needs to implement the `Label` trait.
60/// 
61/// The graph is directed.
62
63// pub trait LabeledGraph<'a>: Graph<'a> 
64//     where <Self as Graph<'a>>::Node: Label, <Self as Graph<'a>>::Edge: Label {}
65pub struct SimpleLabeledGraph<L1: Label, L2: Label> {
66    nodes: Vec<LabelNode<L1>>,
67    edges: Vec<LabeledEdge<L2>>,
68}
69
70#[derive(Hash, Eq, Clone)]
71pub struct SingleLabel(());
72
73impl Display for SingleLabel {
74    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
75        write!(f, "")
76    }
77}
78
79impl Label for SingleLabel {
80    fn label(&self) -> &str {
81        ""
82    }
83}
84
85impl PartialEq for SingleLabel {
86    fn eq(&self, _: &Self) -> bool {
87        true
88    }
89}
90
91pub type StandardLabeledGraph = SimpleLabeledGraph<String, SingleLabel>;
92
93impl<'a> Graph<'a> for StandardLabeledGraph {
94    type Node = LabelNode<String>;
95
96    type Edge = LabeledEdge<SingleLabel>;
97
98    fn new() -> Self {
99        StandardLabeledGraph {
100            nodes: Vec::new(),
101            edges: Vec::new(),
102        }
103    }
104
105    fn nodes(&'a self) -> impl Iterator<Item = &'a Self::Node> {
106        self.nodes.iter()
107    }
108
109    fn edges(&'a self) -> impl Iterator<Item = &'a Self::Edge> {
110        self.edges.iter()
111    }
112    
113
114    fn add_node(&mut self, node: Self::Node) {
115        self.nodes.push(node);
116    }
117
118    fn add_edge(&mut self, edge: Self::Edge) {
119        self.edges.push(edge);
120    }
121}
122
123impl<'a> Labeled<'a> for StandardLabeledGraph {
124    fn label_same(&self, node: &Self::Node, label: &Self::Node) -> bool {
125        node.label == label.label
126    }
127
128    fn get_label(&'a self, node: &'a Self::Node) -> &'a impl Label {
129        &node.label
130    }
131
132    fn get_edges_pair_label(&'a self) -> impl Iterator<Item = (&'a Self::Node, &'a Self::Node, &'a impl Label)> {
133        let id_map: HashMap<_, _, std::collections::hash_map::RandomState> = HashMap::from_iter(self.nodes.iter().map(|node| (node.id, node)));
134        self.edges.iter().map(move |edge| (id_map.get(&edge.src).unwrap().clone(), id_map.get(&edge.dst).unwrap().clone(), &edge.label)).collect::<Vec<_>>().into_iter()
135    }
136
137    fn edge_label_same(&self, _: &Self::Edge, _: &Self::Edge) -> bool {
138        true
139    }
140
141    fn edge_node_label_same(&self, _: &Self::Node, _: &Self::Edge, _: &Self::Node, _: &Self::Node, _: &Self::Edge, _: &Self::Node) -> bool {
142        true
143    }
144}
145
146impl Directed for StandardLabeledGraph {}
147
148impl Adjacency<'_> for StandardLabeledGraph {}
149    
150impl AdjacencyInv<'_> for StandardLabeledGraph {}
151
152impl LabeledAdjacency<'_> for StandardLabeledGraph {}
153
154impl StandardLabeledGraph {
155    pub fn new() -> Self {
156        return StandardLabeledGraph {
157            nodes: Vec::new(),
158            edges: Vec::new(),
159        }
160    }
161
162    pub fn add_node(&mut self, id: u64, label: String) {
163        self.nodes.push(LabelNode {
164            id,
165            label
166        });
167    }
168
169    pub fn add_edge(&mut self, src: u64, dst: u64) {
170        self.edges.push(LabeledEdge {
171            src,
172            dst,
173            label: SingleLabel(())
174        });
175    }
176}
177
178impl Display for StandardLabeledGraph {
179    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
180        let mut s = String::new();
181        s.push_str("nodes: ");
182        for node in self.nodes.iter() {
183            s.push_str(format!("{}, ", node).as_str());
184        }
185        s.push_str("\nedges: ");
186        for edge in self.edges.iter() {
187            s.push_str(format!("{} -> {}, ", edge.src, edge.dst).as_str());
188        }
189        write!(f, "{}", s)
190    }
191}
192impl<L: Label> Vertex for LabelNode<L> {}
193
194pub struct HyperLabelGraph<L: Label> {
195    nodes: Vec<LabelNode<L>>,
196    edges: Vec<LabeledEdge<SingleLabel>>,
197    same_label_fn: Option<Box<dyn Fn(&L, &L) -> bool>>,
198}
199
200impl<'a, L: Label> Graph<'a> for HyperLabelGraph<L> {
201    type Node = LabelNode<L>;
202    type Edge = LabeledEdge<SingleLabel>;
203
204    fn new() -> Self {
205        HyperLabelGraph {
206            nodes: Vec::new(),
207            edges: Vec::new(),
208            same_label_fn: None,
209        }
210    }
211
212    fn nodes(&'a self) -> impl Iterator<Item = &'a Self::Node> {
213        self.nodes.iter()
214    }
215
216    fn edges(&'a self) -> impl Iterator<Item = &'a Self::Edge> {
217        self.edges.iter()
218    }
219
220    fn add_node(&mut self, node: Self::Node) {
221        self.nodes.push(node);
222    }
223
224    fn add_edge(&mut self, edge: Self::Edge) {
225        self.edges.push(edge);
226    }
227}
228
229impl<'a, L: Label> Labeled<'a> for HyperLabelGraph<L> {
230    fn label_same(&self, node: &Self::Node, label: &Self::Node) -> bool {
231        (self.same_label_fn.as_ref().expect("hyper compare function is not set"))(&node.label, &label.label)
232    }
233
234    fn get_label(&'a self, node: &'a Self::Node) -> &'a impl Label {
235        &node.label
236    }
237
238    fn get_edges_pair_label(&'a self) -> impl Iterator<Item = (&'a Self::Node, &'a Self::Node, &'a impl Label)> {
239        let id_map: HashMap<_, _, std::collections::hash_map::RandomState> = HashMap::from_iter(self.nodes.iter().map(|node| (node.id, node)));
240        self.edges.iter().map(move |edge| (id_map.get(&edge.src).unwrap().clone(), id_map.get(&edge.dst).unwrap().clone(), &edge.label)).collect::<Vec<_>>().into_iter()
241    }
242
243    fn edge_label_same(&self, _: &Self::Edge, _: &Self::Edge) -> bool {
244        true
245    }
246
247    fn edge_node_label_same(&self, _: &Self::Node, _: &Self::Edge, _: &Self::Node, _: &Self::Node, _: &Self::Edge, _: &Self::Node) -> bool {
248        true
249    }
250}
251
252impl<L: Label> HyperLabeled<'_> for HyperLabelGraph<L> {
253    type L = L;
254    fn set_same_label_fn(&mut self, f: Box<dyn Fn(&Self::L, &Self::L) -> bool>) {
255        self.same_label_fn = Some(f);
256    }
257}
258
259impl Directed for HyperLabelGraph<SingleLabel> {}
260
261impl Adjacency<'_> for HyperLabelGraph<SingleLabel> {}
262    
263impl AdjacencyInv<'_> for HyperLabelGraph<SingleLabel> {}
264
265impl<L: Label> HyperLabelGraph<L> {
266    pub fn new() -> Self {
267        return HyperLabelGraph {
268            nodes: Vec::new(),
269            edges: Vec::new(),
270            same_label_fn: None,
271        }
272    }
273    
274}
graph_base/impls/standard.rs

graph_base/impls/
standard.rs
