Struct SearchTree 

pub struct SearchTree { /* private fields */ }

A search tree that supports efficient lookups and bi-directional parent/child traversal Designed for route planning algorithms that need both indexing and backtracking capabilities

Implementations

impl SearchTree

pub fn new_stateful(direction: Direction) -> Self

Create a new empty search tree with the specified orientation that supports Labels that contain state.

pub fn new_vertex_oriented(direction: Direction) -> Self

Create a new empty search tree with the specified orientation that supports Labels that have no state (Label::Vertex).

pub fn with_root( root_label: Label, orientation: Direction, ) -> Result<Self, SearchTreeError>

Create a new search tree with the given root node.

pub fn set_root(&mut self, root_label: Label) -> Result<(), SearchTreeError>

Set the root node of the tree

pub fn insert_trajectory( &mut self, parent_label: Label, edge_traversal: EdgeTraversal, child_label: Label, ) -> Result<(), SearchTreeError>

Insert the trajectory (parent) -[edge]-> (child) as a node in the tree. it is assumed that the incoming edge traversal has already been deemed dominant over any matching trajectory already existing in the tree.

pub fn iter<'a>( &'a self, ) -> Box<dyn Iterator<Item = (Label, &'a SearchTreeNode)> + 'a>

pub fn keys<'a>(&'a self) -> Box<dyn Iterator<Item = Label> + 'a>

pub fn values<'a>(&'a self) -> Box<dyn Iterator<Item = &'a SearchTreeNode> + 'a>

pub fn get(&self, label: &Label) -> Option<&SearchTreeNode>

Get a node by its label

pub fn get_min_accumulated_cost_label( &self, destination_vertex: VertexId, ) -> Result<(Label, Cost), SearchTreeError>

gets the label with the minimum accumulated tree cost associated with the destination vertex of a search.

pub fn get_labels( &self, vertex: VertexId, ) -> Box<dyn Iterator<Item = Label> + '_>

Find labels for the given vertex ID

pub fn calculate_total_objective_cost( &self, label: &Label, ) -> Result<Cost, SearchTreeError>

walk up the tree from the given label to the root, summing the marginal objective costs. fails if the tree is malformed by counting labels visited and comparing to the count of Labels in the tree.

Arguments

• label - trip destination label to backtrack from and calculate cost

pub fn get_mut(&mut self, label: &Label) -> Option<&mut SearchTreeNode>

Get a mutable reference to a node by its label

pub fn root(&self) -> Option<&Label>

Get the root label

pub fn get_parent(&self, label: &Label) -> Option<&SearchTreeNode>

Get the parent of a node

pub fn contains(&self, label: &Label) -> bool

Check if the tree contains a node with the given label

pub fn len(&self) -> usize

Get the number of nodes in the tree

pub fn is_empty(&self) -> bool

Check if the tree is empty

pub fn direction(&self) -> Direction

Get the tree orientation

pub fn backtrack_with_depth( &self, leaf_vertex: VertexId, depth: u64, ) -> Result<Vec<EdgeTraversal>, SearchTreeError>

Backtrack from a leaf vertex to construct a path using the tree’s inherent direction and limit the backtracking depth to some nonzero count of edges.

Arguments

• leaf_vertex - The vertex ID to backtrack from. this should be the destination vertex dst of the graph triplet (src)-[edge]->(dst).
• depth - max number of edges to find for the path starting at leaf_vertex

Returns

A path of EdgeTraversals from root to leaf (forward) or leaf to root (reverse)

pub fn backtrack( &self, leaf_vertex: VertexId, ) -> Result<Vec<EdgeTraversal>, SearchTreeError>

Backtrack from a leaf vertex to construct a path using the tree’s inherent direction

Arguments

• leaf_vertex - The vertex ID to backtrack from

Returns

A path of EdgeTraversals from root to leaf (forward) or leaf to root (reverse)

pub fn backtrack_label( &self, label: &Label, ) -> Result<Vec<EdgeTraversal>, SearchTreeError>

convenience method to backtrack from some label.

pub fn backtrack_label_with_depth( &self, label: &Label, depth: u64, ) -> Result<Vec<EdgeTraversal>, SearchTreeError>

convenience method to backtrack from some label to some depth.

pub fn backtrack_edge_oriented_route( &self, target: (EdgeListId, EdgeId), graph: Arc<Graph>, ) -> Result<Vec<EdgeTraversal>, SearchTreeError>

backtrack for edge-oriented search, begins from source vertex of target edge.

pub fn reconstruct_path( &self, target_label: &Label, depth: Option<u64>, ) -> Result<Vec<EdgeTraversal>, SearchTreeError>

Reconstruct a path from root to the given target label This is the primary backtracking method for route reconstruction If depth is provided, the path will be limited to a specified number of EdgeTraversals.

pub fn predecessor( &self, child: &Label, ) -> Result<Option<(&EdgeTraversal, &Label)>, SearchTreeError>

get the edge traversal and parent Label that leads to some child Label, aka, where (parent) -[incoming_edge]-> (child)

pub fn labels(&self) -> impl Iterator<Item = Label> + '_

Get all labels in the tree

pub fn nodes(&self) -> impl Iterator<Item = &SearchTreeNode>

Get all nodes in the tree

Trait Implementations

impl Allocative for SearchTree

fn visit<'allocative_a, 'allocative_b: 'allocative_a>( &self, visitor: &'allocative_a mut Visitor<'allocative_b>, )

impl Clone for SearchTree

fn clone(&self) -> SearchTree

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for SearchTree

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for SearchTree

fn default() -> Self

Returns the “default value” for a type.