1 /*
2  * Licensed to the Apache Software Foundation (ASF) under one
3  * or more contributor license agreements.  See the NOTICE file
4  * distributed with this work for additional information
5  * regarding copyright ownership.  The ASF licenses this file
6  * to you under the Apache License, Version 2.0 (the
7  * "License"); you may not use this file except in compliance
8  * with the License.  You may obtain a copy of the License at
9  *
10  *   http://www.apache.org/licenses/LICENSE-2.0
11  *
12  * Unless required by applicable law or agreed to in writing,
13  * software distributed under the License is distributed on an
14  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15  * KIND, either express or implied.  See the License for the
16  * specific language governing permissions and limitations
17  * under the License.
18  */
19 
20 use std::convert::TryFrom;
21 
22 use serde::Deserialize;
23 use serde::Serialize;
24 
25 use crate::fast_graph::FastGraphEdge;
26 use crate::FastGraph;
27 
28 /// Special graph data-structure that is identical to `FastGraph` except that it uses u32 integers
29 /// instead of usize integers. This is used to store a `FastGraph` in a 32bit representation on disk
30 /// when using a 64bit system.
31 #[derive(Serialize, Deserialize, Debug)]
32 pub struct FastGraph32 {
33     num_nodes: u32,
34     pub ranks: Vec<u32>,
35     pub edges_fwd: Vec<FastGraphEdge32>,
36     pub first_edge_ids_fwd: Vec<u32>,
37 
38     pub edges_bwd: Vec<FastGraphEdge32>,
39     pub first_edge_ids_bwd: Vec<u32>,
40 }
41 
42 impl FastGraph32 {
43     /// Creates a 32bit Graph from a given `FastGraph`. All (potentially 64bit) `usize` integers are
44     /// simply converted to u32 and if a value exceeds the 32bit limit an error is thrown. The only
45     /// exception is `std::u32::MAX`, which is converted to `std::usize::MAX`.
new(fast_graph: &FastGraph) -> Self46     pub fn new(fast_graph: &FastGraph) -> Self {
47         FastGraph32 {
48             num_nodes: usize_to_u32(fast_graph.get_num_nodes()),
49             ranks: usize_to_u32_vec(&fast_graph.ranks),
50             edges_fwd: usize_to_u32_edges(&fast_graph.edges_fwd),
51             first_edge_ids_fwd: usize_to_u32_vec(&fast_graph.first_edge_ids_fwd),
52             edges_bwd: usize_to_u32_edges(&fast_graph.edges_bwd),
53             first_edge_ids_bwd: usize_to_u32_vec(&fast_graph.first_edge_ids_bwd),
54         }
55     }
56 
57     /// Converts a 32bit Graph to an actual `FastGraph` using `usize` such that it can be used with
58     /// FastPaths crate. Any integers that equal `std::u32::MAX` are mapped to `std::usize::MAX`.
convert_to_usize(self) -> FastGraph59     pub fn convert_to_usize(self) -> FastGraph {
60         let mut g = FastGraph::new(self.num_nodes as usize);
61         g.ranks = u32_to_usize_vec(&self.ranks);
62         g.edges_fwd = u32_to_usize_edges(&self.edges_fwd);
63         g.first_edge_ids_fwd = u32_to_usize_vec(&self.first_edge_ids_fwd);
64         g.edges_bwd = u32_to_usize_edges(&self.edges_bwd);
65         g.first_edge_ids_bwd = u32_to_usize_vec(&self.first_edge_ids_bwd);
66         g
67     }
68 }
69 
70 /// 32bit equivalent to `FastGraphEdge`, see `FastGraph32` docs.
71 #[derive(Serialize, Deserialize, Debug)]
72 pub struct FastGraphEdge32 {
73     pub base_node: u32,
74     pub adj_node: u32,
75     pub weight: u32,
76     pub replaced_in_edge: u32,
77     pub replaced_out_edge: u32,
78 }
79 
usize_to_u32(int: usize) -> u3280 fn usize_to_u32(int: usize) -> u32 {
81     if int == std::usize::MAX {
82         usize_to_u32(std::u32::MAX as usize)
83     } else {
84         if let Ok(x) = u32::try_from(int) {
85             x
86         } else {
87             panic!("Could not convert {} to a 32-bit integer", int);
88         }
89     }
90 }
91 
usize_to_u32_vec(vec: &Vec<usize>) -> Vec<u32>92 fn usize_to_u32_vec(vec: &Vec<usize>) -> Vec<u32> {
93     vec.iter().map(|i| usize_to_u32(*i)).collect()
94 }
95 
usize_to_u32_edges(vec: &Vec<FastGraphEdge>) -> Vec<FastGraphEdge32>96 fn usize_to_u32_edges(vec: &Vec<FastGraphEdge>) -> Vec<FastGraphEdge32> {
97     vec.iter().map(|e| usize_to_u32_edge(e)).collect()
98 }
99 
usize_to_u32_edge(edge: &FastGraphEdge) -> FastGraphEdge32100 fn usize_to_u32_edge(edge: &FastGraphEdge) -> FastGraphEdge32 {
101     FastGraphEdge32 {
102         base_node: usize_to_u32(edge.base_node),
103         adj_node: usize_to_u32(edge.adj_node),
104         weight: usize_to_u32(edge.weight),
105         replaced_in_edge: usize_to_u32(edge.replaced_in_edge),
106         replaced_out_edge: usize_to_u32(edge.replaced_out_edge),
107     }
108 }
109 
u32_to_usize(int: u32) -> usize110 fn u32_to_usize(int: u32) -> usize {
111     if int == std::u32::MAX {
112         std::usize::MAX
113     } else {
114         int as usize
115     }
116 }
117 
u32_to_usize_vec(vec: &Vec<u32>) -> Vec<usize>118 fn u32_to_usize_vec(vec: &Vec<u32>) -> Vec<usize> {
119     vec.iter().map(|i| u32_to_usize(*i)).collect()
120 }
121 
u32_to_usize_edges(vec: &Vec<FastGraphEdge32>) -> Vec<FastGraphEdge>122 fn u32_to_usize_edges(vec: &Vec<FastGraphEdge32>) -> Vec<FastGraphEdge> {
123     vec.iter().map(|e| u32_to_usize_edge(e)).collect()
124 }
125 
u32_to_usize_edge(edge: &FastGraphEdge32) -> FastGraphEdge126 fn u32_to_usize_edge(edge: &FastGraphEdge32) -> FastGraphEdge {
127     FastGraphEdge {
128         base_node: u32_to_usize(edge.base_node),
129         adj_node: u32_to_usize(edge.adj_node),
130         weight: u32_to_usize(edge.weight),
131         replaced_in_edge: u32_to_usize(edge.replaced_in_edge),
132         replaced_out_edge: u32_to_usize(edge.replaced_out_edge),
133     }
134 }
135 
136 #[cfg(test)]
137 mod tests {
138     use crate::fast_graph::FastGraph;
139     use crate::fast_graph::FastGraphEdge;
140 
141     use super::*;
142 
143     #[test]
create()144     fn create() {
145         let num_nodes = 5;
146         let ranks = vec![286, 45, 480_001, std::usize::MAX, 4468];
147         let edges_fwd = vec![
148             FastGraphEdge::new(std::usize::MAX, 598, 48, std::usize::MAX, std::usize::MAX),
149             FastGraphEdge::new(
150                 std::usize::MAX,
151                 std::usize::MAX,
152                 std::usize::MAX,
153                 4,
154                 std::usize::MAX,
155             ),
156         ];
157         let edges_bwd = vec![FastGraphEdge::new(0, 1, 3, 4, std::usize::MAX)];
158         let first_edge_ids_fwd = vec![1, std::usize::MAX, std::usize::MAX];
159         let first_edge_ids_bwd = vec![1, std::usize::MAX, 5, std::usize::MAX, 9, 10];
160 
161         let mut g = FastGraph::new(num_nodes);
162         g.ranks = ranks;
163         g.edges_fwd = edges_fwd;
164         g.first_edge_ids_fwd = first_edge_ids_fwd;
165         g.edges_bwd = edges_bwd;
166         g.first_edge_ids_bwd = first_edge_ids_bwd;
167 
168         let g32 = FastGraph32::new(&g);
169         assert_eq!(g32.num_nodes, 5);
170 
171         assert_eq!(g32.ranks.len(), 5);
172         assert_eq!(g32.ranks[0], 286);
173         assert_eq!(g32.ranks[2], 480_001);
174         assert_eq!(g32.ranks[3], std::u32::MAX);
175 
176         assert_eq!(g32.edges_fwd.len(), 2);
177         assert_eq!(g32.edges_fwd[0].base_node, std::u32::MAX);
178         assert_eq!(g32.edges_fwd[0].adj_node, 598);
179         assert_eq!(g32.edges_fwd[0].weight, 48);
180         assert_eq!(g32.edges_fwd[0].replaced_in_edge, std::u32::MAX);
181         assert_eq!(g32.edges_fwd[0].replaced_out_edge, std::u32::MAX);
182 
183         assert_eq!(g32.edges_fwd[1].base_node, std::u32::MAX);
184         assert_eq!(g32.edges_fwd[1].adj_node, std::u32::MAX);
185         assert_eq!(g32.edges_fwd[1].weight, std::u32::MAX);
186         assert_eq!(g32.edges_fwd[1].replaced_in_edge, 4);
187         assert_eq!(g32.edges_fwd[1].replaced_out_edge, std::u32::MAX);
188 
189         assert_eq!(g32.edges_bwd.len(), 1);
190         assert_eq!(g32.edges_bwd[0].weight, 3);
191         assert_eq!(g32.edges_bwd[0].replaced_out_edge, std::u32::MAX);
192 
193         assert_eq!(g32.first_edge_ids_fwd.len(), 3);
194         assert_eq!(g32.first_edge_ids_fwd[1], std::u32::MAX);
195         assert_eq!(g32.first_edge_ids_bwd.len(), 6);
196         assert_eq!(g32.first_edge_ids_bwd[3], std::u32::MAX);
197         assert_eq!(g32.first_edge_ids_bwd[4], 9);
198 
199         // briefly check back-conversion
200         let g_from32 = g32.convert_to_usize();
201         assert_eq!(g_from32.get_num_nodes(), 5);
202         assert_eq!(
203             g_from32.ranks,
204             vec![286, 45, 480_001, std::usize::MAX, 4468]
205         );
206         assert_eq!(g_from32.first_edge_ids_fwd[2], std::usize::MAX);
207         assert_eq!(g_from32.first_edge_ids_bwd[0], 1);
208         assert_eq!(g_from32.first_edge_ids_bwd[1], std::usize::MAX);
209         assert_eq!(g_from32.edges_fwd[0].base_node, std::usize::MAX);
210         assert_eq!(g_from32.edges_fwd[0].adj_node, 598);
211         assert_eq!(g_from32.edges_fwd[0].weight, 48);
212         assert_eq!(g_from32.edges_bwd[0].replaced_in_edge, 4);
213     }
214 
215     #[test]
216     #[should_panic]
create_fails_with_too_large_numbers()217     fn create_fails_with_too_large_numbers() {
218         let num_nodes = 5;
219         let mut g = FastGraph::new(num_nodes);
220         g.ranks = vec![5_000_000_000];
221         FastGraph32::new(&g);
222     }
223 }
224