fast_paths/
fast_graph.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 serde::Deserialize;
21use serde::Serialize;
22
23use crate::constants::Weight;
24use crate::constants::{EdgeId, NodeId, INVALID_EDGE};
25
26#[derive(Serialize, Deserialize, Debug, Clone)]
27pub struct FastGraph {
28    num_nodes: usize,
29    pub(crate) ranks: Vec<usize>,
30    pub(crate) edges_fwd: Vec<FastGraphEdge>,
31    pub(crate) first_edge_ids_fwd: Vec<EdgeId>,
32
33    pub(crate) edges_bwd: Vec<FastGraphEdge>,
34    pub(crate) first_edge_ids_bwd: Vec<EdgeId>,
35}
36
37impl FastGraph {
38    pub fn new(num_nodes: usize) -> Self {
39        FastGraph {
40            ranks: vec![0; num_nodes],
41            num_nodes,
42            edges_fwd: vec![],
43            first_edge_ids_fwd: vec![0; num_nodes + 1],
44            edges_bwd: vec![],
45            first_edge_ids_bwd: vec![0; num_nodes + 1],
46        }
47    }
48
49    pub fn get_node_ordering(&self) -> Vec<NodeId> {
50        let mut ordering = vec![0; self.ranks.len()];
51        for i in 0..self.ranks.len() {
52            ordering[self.ranks[i]] = i;
53        }
54        ordering
55    }
56
57    pub fn get_num_nodes(&self) -> usize {
58        self.num_nodes
59    }
60
61    pub fn get_num_out_edges(&self) -> usize {
62        self.edges_fwd.len()
63    }
64
65    pub fn get_num_in_edges(&self) -> usize {
66        self.edges_bwd.len()
67    }
68
69    pub fn begin_in_edges(&self, node: NodeId) -> usize {
70        self.first_edge_ids_bwd[self.ranks[node]]
71    }
72
73    pub fn end_in_edges(&self, node: NodeId) -> usize {
74        self.first_edge_ids_bwd[self.ranks[node] + 1]
75    }
76
77    pub fn begin_out_edges(&self, node: NodeId) -> usize {
78        self.first_edge_ids_fwd[self.ranks[node]]
79    }
80
81    pub fn end_out_edges(&self, node: NodeId) -> usize {
82        self.first_edge_ids_fwd[self.ranks[node] + 1]
83    }
84}
85
86#[derive(Serialize, Deserialize, Debug, Clone, Copy)]
87pub struct FastGraphEdge {
88    // todo: the base_node is 'redundant' for the routing query so to say, but makes the implementation easier for now
89    // and can still be removed at a later time, we definitely need this information on original
90    // edges for shortcut unpacking. a possible hack is storing it in the (for non-shortcuts)
91    // unused replaced_in/out_edge field.
92    pub base_node: NodeId,
93    pub adj_node: NodeId,
94    pub weight: Weight,
95    pub replaced_in_edge: EdgeId,
96    pub replaced_out_edge: EdgeId,
97}
98
99impl FastGraphEdge {
100    pub fn new(
101        base_node: NodeId,
102        adj_node: NodeId,
103        weight: Weight,
104        replaced_edge1: EdgeId,
105        replaced_edge2: EdgeId,
106    ) -> Self {
107        FastGraphEdge {
108            base_node,
109            adj_node,
110            weight,
111            replaced_in_edge: replaced_edge1,
112            replaced_out_edge: replaced_edge2,
113        }
114    }
115
116    pub fn is_shortcut(&self) -> bool {
117        assert!(
118            (self.replaced_in_edge == INVALID_EDGE && self.replaced_out_edge == INVALID_EDGE)
119                || (self.replaced_in_edge != INVALID_EDGE
120                    && self.replaced_out_edge != INVALID_EDGE)
121        );
122        self.replaced_in_edge != INVALID_EDGE
123    }
124}
fast_paths/fast_graph.rs

fast_paths/
fast_graph.rs
