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(direction: Direction) -> Self

Create a new empty search tree with the specified orientation

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

Create a new search tree with the given root node.

pub fn set_root(&mut self, root_label: Label)

Set the root node of the tree

pub fn insert( &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

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

pub fn keys<'a>(&'a self) -> Box<dyn Iterator<Item = &'a 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_cost_label(&self, vertex: VertexId) -> Option<&Label>

gets the label with the minimum cost associated with a vertex

pub fn get_labels(&self, vertex: VertexId) -> Option<&HashSet<Label>>

Find labels for the given vertex ID

pub fn get_label_by<F>( &self, vertex: VertexId, compare: F, min: bool, ) -> Option<&Label>

where F: FnMut(&(&Label, Option<&EdgeTraversal>)) -> OrderedFloat<f64>,

finds a single label by picking the one that is maximal/minimal wrt some comparison function. for most cases, using the method get_min_cost_label is the correct choice.

Arguments

• vertex - the vertex expected to match some label
• compare - a comparison function
• min - if true, find the minimal value according to the ordering function F, otherwise, the max

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 get_children(&self, label: &Label) -> Vec<&SearchTreeNode>

Get all children of a node

pub fn get_child_labels(&self, label: &Label) -> Vec<Label>

Get all child labels 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 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 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_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 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.