Struct SearchInstance 

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>,
}

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.

Fields

graph: Arc<Graph>

constraint_models: Vec<Arc<dyn ConstraintModel>>

traversal_models: Vec<Arc<dyn TraversalModel>>

map_model: Arc<MapModel>

state_model: Arc<StateModel>

cost_model: Arc<CostModel>

termination_model: Arc<TerminationModel>

label_model: Arc<dyn LabelModel>

default_edge_list: Option<usize>

Implementations

impl SearchInstance

pub fn get_traversal_estimation_model(&self) -> Arc<dyn TraversalModel>

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_constraint_model( &self, edge_list_id: &EdgeListId, ) -> Result<Arc<dyn ConstraintModel>, SearchError>

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_traversal_model( &self, edge_list_id: &EdgeListId, ) -> Result<Arc<dyn TraversalModel>, SearchError>

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 compute_path( &self, path: &[(EdgeListId, EdgeId)], ) -> Result<Vec<EdgeTraversal>, SearchError>

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.