Trait Dijkstrable 

pub trait Dijkstrable {
    type Point: Copy;
    type Bounds: ?Sized + Copy;
    type Dist: Copy + Add<Output = Self::Dist>;
    type PQE: PriorityQueueElement<Point = Self::Point, Dist = Self::Dist>;

    // Required methods
    fn neighbours(
        _: Self::Point,
        _: Self::Bounds,
    ) -> impl Iterator<Item = (Self::Point, Self::Dist)>;
    fn is_impossible(&self, _: Self::Point) -> bool;
    fn dist(&self, _: Self::Point) -> Option<Self::Dist>;
    fn set_dist(&mut self, _: Self::Point, _: Option<Self::Dist>);

    // Provided method
    fn dijkstra(
        &mut self,
        start: Self::Point,
        start_dist: Self::Dist,
        bounds: Self::Bounds,
    ) { ... }
}

An object on which we can run Dijkstra’s algorithm to retrieve the multiple shortest paths.

Required Associated Types

type Point: Copy

“Point”, “node”, or “vertex” type.

type Bounds: ?Sized + Copy

Type for the bounds of the search (useful if searching in a Vec or similar rather than a graph proper). This is only used in the implementation of neighbours(), so it can be effectively ignored if it’s not relevant for that particular implementation.

type Dist: Copy + Add<Output = Self::Dist>

Type for the distance.

type PQE: PriorityQueueElement<Point = Self::Point, Dist = Self::Dist>

Type for the elements of a priority queue structure. PqElement is often a good choice.

Required Methods

fn neighbours( _: Self::Point, _: Self::Bounds, ) -> impl Iterator<Item = (Self::Point, Self::Dist)>

Returns an iterator to all the neighbours (or “adjacent points”) of the provided Point. Implementations can ignore the Bounds if it’s not relevant.

fn is_impossible(&self, _: Self::Point) -> bool

Returns whether it is impossible to get to the destination from the current Point.

fn dist(&self, _: Self::Point) -> Option<Self::Dist>

Returns the distance between the destination and the current Point, or None if it has not been computed yet or is impossible.

fn set_dist(&mut self, _: Self::Point, _: Option<Self::Dist>)

Sets the distance between the destination and the current Point. If the destination and the current Point are not connected, None will be passed in.

Provided Methods

fn dijkstra( &mut self, start: Self::Point, start_dist: Self::Dist, bounds: Self::Bounds, )

Performs Dijkstra’s algorithm. The result is the ending dist() value for the starting point.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors