routee-compass-core 0.7.0

use super::{
    edge_traversal::EdgeTraversal, search_error::SearchError, search_tree_branch::SearchTreeBranch,
};
use crate::model::road_network::{edge_id::EdgeId, graph::Graph, vertex_id::VertexId};
use std::{
    collections::{HashMap, HashSet},
    sync::Arc,
};

/// reconstructs a path from a minimum shortest path tree for some source and target vertex
/// directionality travels up from target to source, toward root of the tree, in both the forward
/// and reverse cases.
pub fn vertex_oriented_route(
    source_id: VertexId,
    target_id: VertexId,
    solution: &HashMap<VertexId, SearchTreeBranch>,
) -> Result<Vec<EdgeTraversal>, SearchError> {
    let mut result: Vec<EdgeTraversal> = vec![];
    let mut visited: HashSet<EdgeId> = HashSet::new();
    let mut this_vertex = target_id;
    loop {
        if this_vertex == source_id {
            break;
        }
        let traversal = solution
            .get(&this_vertex)
            .ok_or_else(|| SearchError::VertexMissingFromSearchTree(this_vertex))?;
        let first_visit = visited.insert(traversal.edge_traversal.edge_id);
        if !first_visit {
            return Err(SearchError::LoopInSearchResult(
                traversal.edge_traversal.edge_id,
            ));
        }
        result.push(traversal.edge_traversal.clone());
        this_vertex = traversal.terminal_vertex;
    }
    let reversed = result.into_iter().rev().collect();
    Ok(reversed)
}

/// edge-oriented backtrack method
pub fn edge_oriented_route(
    source_id: EdgeId,
    target_id: EdgeId,
    solution: &HashMap<VertexId, SearchTreeBranch>,
    graph: Arc<Graph>,
) -> Result<Vec<EdgeTraversal>, SearchError> {
    let o_v = graph
        .src_vertex_id(source_id)
        .map_err(SearchError::GraphError)?;
    let d_v = graph
        .dst_vertex_id(target_id)
        .map_err(SearchError::GraphError)?;
    vertex_oriented_route(o_v, d_v, solution)
}