map_model/pathfind/
node_map.rs

1//! Some helpers for working with fast_paths.
2
3use std::collections::BTreeMap;
4use std::fmt::Debug;
5
6use fast_paths::{InputGraph, NodeId};
7use serde::{Deserialize, Deserializer, Serialize};
8
9/// A bidirectional mapping between fast_paths NodeId and some custom ID type.
10// TODO Upstream this in fast_paths when this is more solid.
11#[derive(Clone, Serialize)]
12pub struct NodeMap<T: Copy + Ord + Debug + Serialize> {
13    // These two fields are redundant and large, so don't serialize the bigger one, to cut down
14    // file size.
15    #[serde(skip_serializing)]
16    node_to_id: BTreeMap<T, NodeId>,
17    id_to_node: Vec<T>,
18}
19
20impl<T: Copy + Ord + Debug + Serialize> NodeMap<T> {
21    pub fn new() -> NodeMap<T> {
22        NodeMap {
23            node_to_id: BTreeMap::new(),
24            id_to_node: Vec::new(),
25        }
26    }
27
28    pub fn get_or_insert(&mut self, node: T) -> NodeId {
29        if let Some(id) = self.node_to_id.get(&node) {
30            return *id;
31        }
32        let id = self.id_to_node.len();
33        self.node_to_id.insert(node, id);
34        self.id_to_node.push(node);
35        id
36    }
37
38    pub fn get(&self, node: T) -> NodeId {
39        if let Some(id) = self.node_to_id.get(&node) {
40            *id
41        } else {
42            panic!("{:?} not in NodeMap", node);
43        }
44    }
45
46    pub fn translate_id(&self, id: usize) -> T {
47        self.id_to_node[id]
48    }
49
50    /// Call this after filling out the input graph, right before preparation.
51    pub fn guarantee_node_ordering(&self, input_graph: &mut InputGraph) {
52        // The fast_paths implementation will trim out the last nodes in the input graph if there
53        // are no edges involving them:
54        // https://github.com/easbar/fast_paths/blob/fdb65f25c5485c9c74c1b3cbe66d829eea81b14b/src/input_graph.rs#L151
55        //
56        // We sometimes add nodes that aren't used yet, so that we can reuse the same node ordering
57        // later. Detect if the last node isn't used.
58        let last_node = self.id_to_node.len() - 1;
59        input_graph.freeze();
60        for edge in input_graph.get_edges() {
61            if edge.from == last_node || edge.to == last_node {
62                // The last node is used, so we're fine
63                input_graph.thaw();
64                return;
65            }
66        }
67        input_graph.thaw();
68
69        // Add a dummy edge from this unused node to any arbitrary node (namely the first), to
70        // prevent it from getting trimmed out. Since no path will start or end from this unused
71        // node, this won't affect resulting paths.
72        let first_node = 0;
73        input_graph.add_edge(last_node, first_node, 1);
74    }
75}
76
77// A serialized NodeMap has this form in JSON. Use this to deserialize.
78#[derive(Deserialize)]
79struct InnerNodeMap<T: Copy + Ord + Debug> {
80    id_to_node: Vec<T>,
81}
82
83pub fn deserialize_nodemap<
84    'de,
85    D: Deserializer<'de>,
86    T: Deserialize<'de> + Copy + Ord + Debug + Serialize,
87>(
88    d: D,
89) -> Result<NodeMap<T>, D::Error> {
90    let inner = <InnerNodeMap<T>>::deserialize(d)?;
91    let id_to_node = inner.id_to_node;
92    let mut node_to_id = BTreeMap::new();
93    for (id, node) in id_to_node.iter().enumerate() {
94        node_to_id.insert(*node, id);
95    }
96
97    Ok(NodeMap {
98        node_to_id,
99        id_to_node,
100    })
101}
map_model/pathfind/node_map.rs

map_model/pathfind/
node_map.rs
