zawgl_core/graph/
mod.rs

1// MIT License
2// Copyright (c) 2022 Alexandre RICCIARDI
3// Permission is hereby granted, free of charge, to any person obtaining a copy
4// of this software and associated documentation files (the "Software"), to deal
5// in the Software without restriction, including without limitation the rights
6// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
7// copies of the Software, and to permit persons to whom the Software is
8// furnished to do so, subject to the following conditions:
9//
10// The above copyright notice and this permission notice shall be included in all
11// copies or substantial portions of the Software.
12//
13// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
18// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
19// SOFTWARE.
20
21pub mod traits;
22pub mod container;
23
24use self::traits::*;
25
26#[derive(PartialEq, Eq, Copy, Clone, Debug, Hash)]
27pub struct EdgeIndex {
28    index: usize,
29}
30
31impl EdgeIndex {
32    pub fn new(index: usize) -> Self {
33        EdgeIndex {index}
34    }
35}
36
37impl traits::MemGraphId for EdgeIndex {
38    fn get_index(&self) -> usize {
39        self.index
40    }
41}
42
43#[derive(PartialEq, Eq, Copy, Clone, Debug, Hash)]
44pub struct NodeIndex {
45    index: usize,
46}
47
48impl NodeIndex {
49    pub fn new(index: usize) -> Self {
50        NodeIndex {index}
51    }
52}
53
54impl traits::MemGraphId for NodeIndex {
55    fn get_index(&self) -> usize {
56        self.index
57    }
58}
59
60#[derive(Debug, Clone)]
61pub struct VertexData<EID: MemGraphId, N> {
62    pub first_outbound_edge: Option<EID>,
63    pub first_inbound_edge: Option<EID>,
64    pub node: N,
65}
66
67impl <EID: MemGraphId + Copy, N> VertexData<EID, N> {
68    pub fn new(n: N) -> Self {
69        VertexData{first_outbound_edge: None, first_inbound_edge: None, node: n}
70    }
71    pub fn get_first_outbound_edge(&self) -> Option<EID> {
72        self.first_outbound_edge
73    }
74    pub fn get_first_inbound_edge(&self) -> Option<EID> {
75        self.first_inbound_edge
76    }
77}
78
79#[derive(Debug, Clone)]
80pub struct EdgeData<NID: MemGraphId, EID: MemGraphId, R: Clone> {
81    pub id: EID,
82    pub source: NID,
83    pub target: NID,
84    pub next_outbound_edge: Option<EID>,
85    pub next_inbound_edge: Option<EID>,
86    pub relationship: R,
87    pub discard: bool,
88}
89
90impl <NID: MemGraphId + Copy, EID: MemGraphId + Copy, R: Clone> EdgeData<NID, EID, R> {
91    pub fn get_source(&self) -> NID {
92        self.source
93    }
94    pub fn get_target(&self) -> NID {
95        self.target
96    }
97
98    pub fn get_next_outbound_edge(&self) -> Option<EID> {
99        self.next_outbound_edge
100    }
101    pub fn get_next_inbound_edge(&self) ->  Option<EID> {
102        self.next_inbound_edge
103    }
104}
105
106pub struct Graph<N: Clone, R: Clone> {
107    vertices: Vec<VertexData<EdgeIndex, N>>,
108    edges: Vec<EdgeData<NodeIndex, EdgeIndex, R>>,
109}
110
111impl <N: Clone, R: Clone> Clone for Graph<N, R> {
112    fn clone(&self) -> Self {
113        Graph::new_clone(self.vertices.clone(), self.edges.clone())
114    }
115}
116
117pub struct OutEdges<'a, R: Clone> {
118    edges: &'a Vec<EdgeData<NodeIndex, EdgeIndex, R>>,
119    current_edge_index: Option<EdgeIndex>,
120}
121
122impl <R: Clone> Iterator for OutEdges<'_, R> {
123    type Item = EdgeIndex;
124
125    fn next(&mut self) -> Option<EdgeIndex> {
126        let mut is_valid = false;
127        let mut curr_edge_index = None;
128        while !is_valid {
129            let edge_index = match self.current_edge_index {
130                None => {
131                    is_valid = true;
132                    None
133                },
134                Some(edge_index) => {
135                    let edge = &self.edges[edge_index.get_index()];
136                    is_valid = !edge.discard;
137                    let curr_edge_index = self.current_edge_index;
138                    self.current_edge_index = edge.next_outbound_edge;
139                    curr_edge_index
140                }
141            };
142            curr_edge_index = edge_index;
143        }
144        curr_edge_index
145    }
146}
147
148
149pub struct InEdges<'a, R: Clone> {
150    edges: &'a Vec<EdgeData<NodeIndex, EdgeIndex, R>>,
151    current_edge_index: Option<EdgeIndex>,
152}
153
154impl <'a, R: Clone> Iterator for InEdges<'a, R> {
155    type Item = EdgeIndex;
156
157    fn next(&mut self) -> Option<Self::Item> {
158        let mut is_valid = false;
159        let mut curr_edge_index = None;
160        while !is_valid {
161            let edge_index = match self.current_edge_index {
162                None => {
163                    is_valid = true;
164                    None
165                },
166                Some(edge_index) => {
167                    let edge = &self.edges[edge_index.get_index()];
168                    is_valid = !edge.discard;
169                    let curr_edge_index = self.current_edge_index;
170                    self.current_edge_index = edge.next_inbound_edge;
171                    curr_edge_index
172                }
173            };
174            curr_edge_index = edge_index;
175        }
176        curr_edge_index
177    }
178}
179
180impl <N: Clone, R: Clone> Graph<N, R> {
181    fn out_edges(&self, source: &NodeIndex) -> OutEdges<'_, R> {
182        let first_outbound_edge = self.vertices[source.get_index()].first_outbound_edge;
183        OutEdges{ edges: &self.edges, current_edge_index: first_outbound_edge }
184    }
185
186    fn in_edges(&self, target: &NodeIndex) -> InEdges<'_, R> {
187        let first_inbound_edge = self.vertices[target.get_index()].first_inbound_edge;
188        InEdges{ edges: &self.edges, current_edge_index: first_inbound_edge }
189    }
190    fn in_degree(&self, node: &NodeIndex) -> usize {
191        self.in_edges(node).count()
192    }
193    fn out_degree(&self, node: &NodeIndex) -> usize {
194        self.out_edges(node).count()
195    }
196}
197
198impl <N: Clone, R: Clone> GraphTrait<NodeIndex, EdgeIndex> for Graph<N, R> {
199    fn get_source_index(&self, edge_index: &EdgeIndex) -> NodeIndex {
200        self.edges[edge_index.get_index()].source
201    }
202    fn get_target_index(&self, edge_index: &EdgeIndex) -> NodeIndex {
203        self.edges[edge_index.get_index()].target
204    }
205
206    fn nodes_len(&self) -> usize {
207        self.vertices.len()
208    }
209
210    fn edges_len(&self) -> usize {
211        self.edges.len()
212    }
213
214    fn get_nodes_ids(&self) -> Vec<NodeIndex> {
215        (0..self.nodes_len()).map(NodeIndex::new).collect()
216    }
217    
218}
219impl<N: Clone, R: Clone> Default for Graph<N, R> {
220    fn default() -> Self {
221        Self::new()
222    }
223}
224impl <N: Clone, R: Clone> Graph<N, R> {
225    pub fn new() -> Self {
226        Graph{ vertices: Vec::new(), edges: Vec::new() }
227    }
228
229    fn insert_vertex(&mut self, node: N, edge_index: &EdgeIndex) -> (EdgeIndex, EdgeIndex) {
230        let nid = self.add_vertex(node);
231        let target = self.edges[edge_index.index].target;
232        let source = self.edges[edge_index.index].source;
233        let rel_src = self.edges[edge_index.index].relationship.clone();
234        let rel_tgt = self.edges[edge_index.index].relationship.clone();
235        let source_edge_index = self.add_edge(rel_src, source, nid);
236        let target_edge_index = self.add_edge(rel_tgt, nid, target);
237        self.discard_edge(edge_index);
238        (source_edge_index, target_edge_index)
239    }
240
241    fn discard_edge(&mut self, edge_index: &EdgeIndex) {
242        self.edges[edge_index.index].discard = true;
243    }
244
245    fn new_clone(vertices: Vec<VertexData<EdgeIndex, N>>, edges: Vec<EdgeData<NodeIndex, EdgeIndex, R>>) -> Self {
246        Graph{ vertices, edges }
247    }
248
249    pub fn add_vertex(&mut self, node: N) -> NodeIndex {
250        let index = self.vertices.len();
251        self.vertices.push(VertexData::<EdgeIndex, N>{first_outbound_edge: None, first_inbound_edge: None, node});
252        NodeIndex::new(index)
253    }
254
255    pub fn get_vertex(&self, id: NodeIndex) -> &VertexData<EdgeIndex, N> {
256        &self.vertices[id.get_index()]
257    }
258    pub fn get_edge_data(&self, id: EdgeIndex) -> EdgeData<NodeIndex, EdgeIndex, R> {
259        self.edges[id.get_index()].clone()
260    }
261
262    pub fn add_edge(&mut self, rel: R, source: NodeIndex, target: NodeIndex) -> EdgeIndex {
263        let index = self.edges.len();
264        {
265            let source_data = &self.vertices[source.get_index()];
266            let target_data = &self.vertices[target.get_index()];
267            self.edges.push(EdgeData{id: EdgeIndex::new(index),
268                source, target,
269                next_inbound_edge: target_data.first_inbound_edge, 
270                next_outbound_edge: source_data.first_outbound_edge,
271                relationship: rel,
272                discard: false,
273            });
274        }
275        
276        let ms = &mut self.vertices[source.get_index()];
277        ms.first_outbound_edge = Some(EdgeIndex::new(index));
278        let mt = &mut self.vertices[target.get_index()];
279        mt.first_inbound_edge = Some(EdgeIndex::new(index));
280        EdgeIndex::new(index)
281    }
282}
283
284#[cfg(test)]
285mod test_graph {
286    use super::*;
287    #[test]
288    fn test_small_graph_it() {
289        let mut graph = Graph::new();
290        let n0 = graph.add_vertex(1);
291        let n1 = graph.add_vertex(2);
292        let n2 = graph.add_vertex(3);
293
294        let e0 = graph.add_edge(4, n0, n1);
295        let _e1 = graph.add_edge(4, n1, n2);
296        let e2 = graph.add_edge(5, n0, n2);
297
298        let ed0 = graph.get_edge_data(e0);
299        assert_eq!(ed0.source, n0);
300        assert_eq!(ed0.target, n1);
301        assert_eq!(ed0.next_outbound_edge, None);
302        
303        let nd0 = graph.get_vertex(n0);
304        assert_eq!(nd0.first_outbound_edge, Some(e2));
305
306        let ed2 = graph.get_edge_data(e2);
307        assert_eq!(ed2.source, n0);
308        assert_eq!(ed2.target, n2);
309        assert_eq!(ed2.next_outbound_edge, Some(e0));
310
311    }
312}
zawgl_core/graph/mod.rs

zawgl_core/graph/
mod.rs
