fast_paths/
fast_graph32.rs

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
20use std::convert::TryFrom;
21
22use serde::Deserialize;
23use serde::Serialize;
24
25use crate::fast_graph::FastGraphEdge;
26use 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, Clone)]
32pub 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
42impl 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`.
46    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`.
59    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, Clone, Copy)]
72pub 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
80fn usize_to_u32(int: usize) -> u32 {
81    if int == std::usize::MAX {
82        usize_to_u32(std::u32::MAX as usize)
83    } else if let Ok(x) = u32::try_from(int) {
84        x
85    } else {
86        panic!("Could not convert {} to a 32-bit integer", int);
87    }
88}
89
90fn usize_to_u32_vec(vec: &[usize]) -> Vec<u32> {
91    vec.iter().map(|i| usize_to_u32(*i)).collect()
92}
93
94fn usize_to_u32_edges(vec: &[FastGraphEdge]) -> Vec<FastGraphEdge32> {
95    vec.iter().map(|e| usize_to_u32_edge(e)).collect()
96}
97
98fn usize_to_u32_edge(edge: &FastGraphEdge) -> FastGraphEdge32 {
99    FastGraphEdge32 {
100        base_node: usize_to_u32(edge.base_node),
101        adj_node: usize_to_u32(edge.adj_node),
102        weight: usize_to_u32(edge.weight),
103        replaced_in_edge: usize_to_u32(edge.replaced_in_edge),
104        replaced_out_edge: usize_to_u32(edge.replaced_out_edge),
105    }
106}
107
108fn u32_to_usize(int: u32) -> usize {
109    if int == std::u32::MAX {
110        std::usize::MAX
111    } else {
112        int as usize
113    }
114}
115
116fn u32_to_usize_vec(vec: &[u32]) -> Vec<usize> {
117    vec.iter().map(|i| u32_to_usize(*i)).collect()
118}
119
120fn u32_to_usize_edges(vec: &[FastGraphEdge32]) -> Vec<FastGraphEdge> {
121    vec.iter().map(|e| u32_to_usize_edge(e)).collect()
122}
123
124fn u32_to_usize_edge(edge: &FastGraphEdge32) -> FastGraphEdge {
125    FastGraphEdge {
126        base_node: u32_to_usize(edge.base_node),
127        adj_node: u32_to_usize(edge.adj_node),
128        weight: u32_to_usize(edge.weight),
129        replaced_in_edge: u32_to_usize(edge.replaced_in_edge),
130        replaced_out_edge: u32_to_usize(edge.replaced_out_edge),
131    }
132}
133
134#[cfg(test)]
135mod tests {
136    use crate::fast_graph::FastGraph;
137    use crate::fast_graph::FastGraphEdge;
138
139    use super::*;
140
141    #[test]
142    fn create() {
143        let num_nodes = 5;
144        let ranks = vec![286, 45, 480_001, std::usize::MAX, 4468];
145        let edges_fwd = vec![
146            FastGraphEdge::new(std::usize::MAX, 598, 48, std::usize::MAX, std::usize::MAX),
147            FastGraphEdge::new(
148                std::usize::MAX,
149                std::usize::MAX,
150                std::usize::MAX,
151                4,
152                std::usize::MAX,
153            ),
154        ];
155        let edges_bwd = vec![FastGraphEdge::new(0, 1, 3, 4, std::usize::MAX)];
156        let first_edge_ids_fwd = vec![1, std::usize::MAX, std::usize::MAX];
157        let first_edge_ids_bwd = vec![1, std::usize::MAX, 5, std::usize::MAX, 9, 10];
158
159        let mut g = FastGraph::new(num_nodes);
160        g.ranks = ranks;
161        g.edges_fwd = edges_fwd;
162        g.first_edge_ids_fwd = first_edge_ids_fwd;
163        g.edges_bwd = edges_bwd;
164        g.first_edge_ids_bwd = first_edge_ids_bwd;
165
166        let g32 = FastGraph32::new(&g);
167        assert_eq!(g32.num_nodes, 5);
168
169        assert_eq!(g32.ranks.len(), 5);
170        assert_eq!(g32.ranks[0], 286);
171        assert_eq!(g32.ranks[2], 480_001);
172        assert_eq!(g32.ranks[3], std::u32::MAX);
173
174        assert_eq!(g32.edges_fwd.len(), 2);
175        assert_eq!(g32.edges_fwd[0].base_node, std::u32::MAX);
176        assert_eq!(g32.edges_fwd[0].adj_node, 598);
177        assert_eq!(g32.edges_fwd[0].weight, 48);
178        assert_eq!(g32.edges_fwd[0].replaced_in_edge, std::u32::MAX);
179        assert_eq!(g32.edges_fwd[0].replaced_out_edge, std::u32::MAX);
180
181        assert_eq!(g32.edges_fwd[1].base_node, std::u32::MAX);
182        assert_eq!(g32.edges_fwd[1].adj_node, std::u32::MAX);
183        assert_eq!(g32.edges_fwd[1].weight, std::u32::MAX);
184        assert_eq!(g32.edges_fwd[1].replaced_in_edge, 4);
185        assert_eq!(g32.edges_fwd[1].replaced_out_edge, std::u32::MAX);
186
187        assert_eq!(g32.edges_bwd.len(), 1);
188        assert_eq!(g32.edges_bwd[0].weight, 3);
189        assert_eq!(g32.edges_bwd[0].replaced_out_edge, std::u32::MAX);
190
191        assert_eq!(g32.first_edge_ids_fwd.len(), 3);
192        assert_eq!(g32.first_edge_ids_fwd[1], std::u32::MAX);
193        assert_eq!(g32.first_edge_ids_bwd.len(), 6);
194        assert_eq!(g32.first_edge_ids_bwd[3], std::u32::MAX);
195        assert_eq!(g32.first_edge_ids_bwd[4], 9);
196
197        // briefly check back-conversion
198        let g_from32 = g32.convert_to_usize();
199        assert_eq!(g_from32.get_num_nodes(), 5);
200        assert_eq!(
201            g_from32.ranks,
202            vec![286, 45, 480_001, std::usize::MAX, 4468]
203        );
204        assert_eq!(g_from32.first_edge_ids_fwd[2], std::usize::MAX);
205        assert_eq!(g_from32.first_edge_ids_bwd[0], 1);
206        assert_eq!(g_from32.first_edge_ids_bwd[1], std::usize::MAX);
207        assert_eq!(g_from32.edges_fwd[0].base_node, std::usize::MAX);
208        assert_eq!(g_from32.edges_fwd[0].adj_node, 598);
209        assert_eq!(g_from32.edges_fwd[0].weight, 48);
210        assert_eq!(g_from32.edges_bwd[0].replaced_in_edge, 4);
211    }
212
213    #[test]
214    #[should_panic]
215    fn create_fails_with_too_large_numbers() {
216        let num_nodes = 5;
217        let mut g = FastGraph::new(num_nodes);
218        g.ranks = vec![5_000_000_000];
219        FastGraph32::new(&g);
220    }
221}
fast_paths/fast_graph32.rs

fast_paths/
fast_graph32.rs
