1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
use crate::{
algorithm::search::{Direction, EdgeTraversal, SearchError, SearchTree},
model::{
constraint::ConstraintModel,
cost::CostModel,
label::{label_model::LabelModel, Label},
map::MapModel,
network::{EdgeId, EdgeListId, Graph},
state::StateModel,
termination::TerminationModel,
traversal::TraversalModel,
},
};
use std::sync::Arc;
/// A `SearchInstance` represents the collection of read-only models and data required
/// to execute a search query. It encapsulates the graph, constraints, traversal logic,
/// cost calculations, and termination criteria, providing a unified interface for
/// search algorithms to interact with the underlying network and models.
pub struct SearchInstance {
pub graph: Arc<Graph>,
pub constraint_models: Vec<Arc<dyn ConstraintModel>>,
pub traversal_models: Vec<Arc<dyn TraversalModel>>,
pub map_model: Arc<MapModel>,
pub state_model: Arc<StateModel>,
pub cost_model: Arc<CostModel>,
pub termination_model: Arc<TerminationModel>,
pub label_model: Arc<dyn LabelModel>,
pub default_edge_list: Option<usize>,
}
impl SearchInstance {
/// Retrieves the traversal model that should be used for traversal estimation
/// when no specific edge is being traversed (e.g., at the start of a search or
/// when calculating heuristics). It falls back to the default edge list's model.
pub fn get_traversal_estimation_model(&self) -> Arc<dyn TraversalModel> {
self.traversal_models[self.default_edge_list.unwrap_or_default()].clone()
}
/// Retrieves the constraint model associated with a specific edge list.
///
/// # Arguments
///
/// * `edge_list_id` - The ID of the edge list to get the constraint model for.
///
/// # Returns
///
/// A reference to the constraint model, or an error if the ID is not found.
pub fn get_constraint_model(
&self,
edge_list_id: &EdgeListId,
) -> Result<Arc<dyn ConstraintModel>, SearchError> {
self.constraint_models
.get(edge_list_id.0)
.ok_or_else(|| SearchError::InternalError(format!("during search, attempting to retrieve constraint models for edge list {edge_list_id} that does not exist")))
.cloned()
}
/// Retrieves the traversal model associated with a specific edge list.
///
/// # Arguments
///
/// * `edge_list_id` - The ID of the edge list to get the traversal model for.
///
/// # Returns
///
/// A reference to the traversal model, or an error if the ID is not found.
pub fn get_traversal_model(
&self,
edge_list_id: &EdgeListId,
) -> Result<Arc<dyn TraversalModel>, SearchError> {
self.traversal_models
.get(edge_list_id.0)
.ok_or_else(|| SearchError::InternalError(format!("during search, attempting to retrieve traversal models for edge list {edge_list_id} that does not exist")))
.cloned()
}
/// Computes the sequence of `EdgeTraversal` objects for a given path of edge IDs.
///
/// This method is essential for reconstructing the full state (costs, state transitions)
/// along a path that was generated by an external process, such as map matching,
/// which typically only returns a sequence of edge identifiers.
///
/// # Implementation Note: Vector Index Tracking
///
/// When building the internal `SearchTree` for the path, this method uses "indexed labels"
/// (`Label::VertexWithIntState`) where the state is the current index in the path.
///
/// We must track the vector index of each insertion for the following reasons:
///
/// 1. **Path Cycles**: A path may visit the same vertex multiple times (e.g., in complex
/// intersections or specific routing constraints). If we used plain `Label::Vertex`,
/// subsequent visits to the same vertex would overwrite previous entries in the
/// `SearchTree`'s internal map, breaking the tree structure.
/// 2. **Backtracking**: The `SearchTree` depends on unique labels to correctly backtrack
/// from a destination to the root. By indexing each step, we ensure that every node
/// in the path is a unique entity in the tree, even if they share the same physical vertex.
/// 3. **State Consistency**: It ensures that the state at each step of the path is
/// linearly associated with its predecessor, avoiding any ambiguity that could arise
/// if multiple paths through the same vertex were present in the tree.
pub fn compute_path(
&self,
path: &[(EdgeListId, EdgeId)],
) -> Result<Vec<EdgeTraversal>, SearchError> {
let mut edge_traversals = Vec::with_capacity(path.len());
let mut current_state = self.state_model.initial_state(None)?;
let mut tree = SearchTree::new(Direction::Forward);
let mut prev_label = if let Some((edge_list_id, edge_id)) = path.first() {
let (src, _, _) = self.graph.edge_triplet(edge_list_id, edge_id)?;
let root_label = Label::Vertex(src.vertex_id);
tree.set_root(root_label.clone());
root_label
} else {
return Ok(Vec::new());
};
for (i, (edge_list_id, edge_id)) in path.iter().enumerate() {
let trajectory = self.graph.edge_triplet(edge_list_id, edge_id)?;
let (_, _, dst) = trajectory;
let tm = self.get_traversal_model(edge_list_id)?;
let traversal = EdgeTraversal::new_local(
trajectory,
&tree,
¤t_state,
&self.state_model,
tm.as_ref(),
&self.cost_model,
)?;
// Use indexed labels to handle cycles in the path correctly
let child_label = Label::VertexWithIntState {
vertex_id: dst.vertex_id,
state: i,
};
tree.insert(
prev_label,
traversal.clone(),
child_label.clone(),
self.label_model.clone(),
)
.map_err(|e| SearchError::InternalError(e.to_string()))?;
prev_label = child_label;
current_state = traversal.result_state.clone();
edge_traversals.push(traversal);
}
Ok(edge_traversals)
}
}