Struct traitgraph_algo::dijkstra::Dijkstra

source · [−]

pub struct Dijkstra<Graph: GraphBase, WeightType: DijkstraWeight, NodeWeights: NodeWeightArray<WeightType>, Heap: DijkstraHeap<WeightType, Graph::NodeIndex>> { /* private fields */ }

Expand description

Data structure for Dijkstra’s shortest path algorithm.

This variant of Dijkstra’s algorithm supports only computing the length of a shortest path, and not the shortest path itself. Therefore it does not need an array of back pointers for each node, saving a bit of memory.

Implementations

source

impl<WeightType: DijkstraWeight + Eq + Debug, EdgeData: DijkstraWeightedEdgeData<WeightType>, Graph: StaticGraph<EdgeData = EdgeData>, NodeWeights: NodeWeightArray<WeightType>, Heap: DijkstraHeap<WeightType, Graph::NodeIndex>> Dijkstra<Graph, WeightType, NodeWeights, Heap>

source

pub fn new(graph: &Graph) -> Self

Create the data structures for the given graph.

source

pub fn shortest_path_lens<TargetMap: DijkstraTargetMap<Graph>>(
 &mut self,
 graph: &Graph,
 source: Graph::NodeIndex,
 targets: &TargetMap,
 target_amount: usize,
 max_weight: WeightType,
 forbid_source_target: bool,
 distances: &mut Vec<(Graph::NodeIndex, WeightType)>
)

Compute the shortest paths from source to all targets, with given maximum weight.

Auto Trait Implementations

impl<Graph, WeightType, NodeWeights, Heap> RefUnwindSafe for Dijkstra<Graph, WeightType, NodeWeights, Heap> where
 Graph: RefUnwindSafe,
 Heap: RefUnwindSafe,
 NodeWeights: RefUnwindSafe,
 WeightType: RefUnwindSafe,

impl<Graph, WeightType, NodeWeights, Heap> Send for Dijkstra<Graph, WeightType, NodeWeights, Heap> where
 Graph: Send,
 Heap: Send,
 NodeWeights: Send,
 WeightType: Send,

impl<Graph, WeightType, NodeWeights, Heap> Sync for Dijkstra<Graph, WeightType, NodeWeights, Heap> where
 Graph: Sync,
 Heap: Sync,
 NodeWeights: Sync,
 WeightType: Sync,

impl<Graph, WeightType, NodeWeights, Heap> Unpin for Dijkstra<Graph, WeightType, NodeWeights, Heap> where
 Graph: Unpin,
 Heap: Unpin,
 NodeWeights: Unpin,
 WeightType: Unpin,

impl<Graph, WeightType, NodeWeights, Heap> UnwindSafe for Dijkstra<Graph, WeightType, NodeWeights, Heap> where
 Graph: UnwindSafe,
 Heap: UnwindSafe,
 NodeWeights: UnwindSafe,
 WeightType: UnwindSafe,

Blanket Implementations

source

impl<T> Any for T where
T: 'static + ?Sized,

source

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more

source

impl<T> Borrow<T> for T where
T: ?Sized,

const: unstable · source

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more

source

impl<T> BorrowMut<T> for T where
T: ?Sized,

const: unstable · source

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more

source

impl<T> From<T> for T

const: unstable · source

fn from(t: T) -> T

Returns the argument unchanged.

source

impl<T, U> Into for T where
U: From<T>,

const: unstable · source

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source

impl<T, U> TryFrom for T where
U: Into<T>,

type Error = Infallible

The type returned in the event of a conversion error.

const: unstable · source

fn try_from(value: U) -> Result<T, <T as TryFrom>::Error>

Performs the conversion.

source

impl<T, U> TryInto for T where
U: TryFrom<T>,

type Error = >::Error

The type returned in the event of a conversion error.

const: unstable · source

fn try_into(self) -> Result<U, >::Error>

Performs the conversion.

Struct traitgraph_algo::dijkstra::Dijkstra

Implementations

impl<WeightType: DijkstraWeight + Eq + Debug, EdgeData: DijkstraWeightedEdgeData<WeightType>, Graph: StaticGraph<EdgeData = EdgeData>, NodeWeights: NodeWeightArray<WeightType>, Heap: DijkstraHeap<WeightType, Graph::NodeIndex>> Dijkstra<Graph, WeightType, NodeWeights, Heap>

pub fn new(graph: &Graph) -> Self

pub fn shortest_path_lens<TargetMap: DijkstraTargetMap<Graph>>(
    &mut self,
    graph: &Graph,
    source: Graph::NodeIndex,
    targets: &TargetMap,
    target_amount: usize,
    max_weight: WeightType,
    forbid_source_target: bool,
    distances: &mut Vec<(Graph::NodeIndex, WeightType)>
)

Auto Trait Implementations

impl<Graph, WeightType, NodeWeights, Heap> RefUnwindSafe for Dijkstra<Graph, WeightType, NodeWeights, Heap> where
    Graph: RefUnwindSafe,
    Heap: RefUnwindSafe,
    NodeWeights: RefUnwindSafe,
    WeightType: RefUnwindSafe,

impl<Graph, WeightType, NodeWeights, Heap> Send for Dijkstra<Graph, WeightType, NodeWeights, Heap> where
    Graph: Send,
    Heap: Send,
    NodeWeights: Send,
    WeightType: Send,

impl<Graph, WeightType, NodeWeights, Heap> Sync for Dijkstra<Graph, WeightType, NodeWeights, Heap> where
    Graph: Sync,
    Heap: Sync,
    NodeWeights: Sync,
    WeightType: Sync,

impl<Graph, WeightType, NodeWeights, Heap> Unpin for Dijkstra<Graph, WeightType, NodeWeights, Heap> where
    Graph: Unpin,
    Heap: Unpin,
    NodeWeights: Unpin,
    WeightType: Unpin,

impl<Graph, WeightType, NodeWeights, Heap> UnwindSafe for Dijkstra<Graph, WeightType, NodeWeights, Heap> where
    Graph: UnwindSafe,
    Heap: UnwindSafe,
    NodeWeights: UnwindSafe,
    WeightType: UnwindSafe,

Blanket Implementations

impl<T> Any for T where
T: 'static + ?Sized,

fn type_id(&self) -> TypeId

impl<T> Borrow<T> for T where
T: ?Sized,

fn borrow(&self) -> &T

impl<T> BorrowMut<T> for T where
T: ?Sized,

fn borrow_mut(&mut self) -> &mut T

impl<T> From<T> for T

fn from(t: T) -> T

impl<T, U> Into<U> for T where
U: From<T>,

fn into(self) -> U

impl<T, U> TryFrom<U> for T where
U: Into<T>,

type Error = Infallible

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

impl<T, U> TryInto<U> for T where
U: TryFrom<T>,

type Error = <U as TryFrom<T>>::Error

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

impl<V, T> VZip<V> for T where
V: MultiLane<T>,

fn vzip(self) -> V

Struct traitgraph_algo::dijkstra::Dijkstra

Implementations

impl<WeightType: DijkstraWeight + Eq + Debug, EdgeData: DijkstraWeightedEdgeData<WeightType>, Graph: StaticGraph<EdgeData = EdgeData>, NodeWeights: NodeWeightArray<WeightType>, Heap: DijkstraHeap<WeightType, Graph::NodeIndex>> Dijkstra<Graph, WeightType, NodeWeights, Heap>

pub fn new(graph: &Graph) -> Self

pub fn shortest_path_lens<TargetMap: DijkstraTargetMap<Graph>>( &mut self, graph: &Graph, source: Graph::NodeIndex, targets: &TargetMap, target_amount: usize, max_weight: WeightType, forbid_source_target: bool, distances: &mut Vec<(Graph::NodeIndex, WeightType)>)

Auto Trait Implementations

impl<Graph, WeightType, NodeWeights, Heap> RefUnwindSafe for Dijkstra<Graph, WeightType, NodeWeights, Heap> where Graph: RefUnwindSafe, Heap: RefUnwindSafe, NodeWeights: RefUnwindSafe, WeightType: RefUnwindSafe,

impl<Graph, WeightType, NodeWeights, Heap> Send for Dijkstra<Graph, WeightType, NodeWeights, Heap> where Graph: Send, Heap: Send, NodeWeights: Send, WeightType: Send,

impl<Graph, WeightType, NodeWeights, Heap> Sync for Dijkstra<Graph, WeightType, NodeWeights, Heap> where Graph: Sync, Heap: Sync, NodeWeights: Sync, WeightType: Sync,

impl<Graph, WeightType, NodeWeights, Heap> Unpin for Dijkstra<Graph, WeightType, NodeWeights, Heap> where Graph: Unpin, Heap: Unpin, NodeWeights: Unpin, WeightType: Unpin,

impl<Graph, WeightType, NodeWeights, Heap> UnwindSafe for Dijkstra<Graph, WeightType, NodeWeights, Heap> where Graph: UnwindSafe, Heap: UnwindSafe, NodeWeights: UnwindSafe, WeightType: UnwindSafe,

Blanket Implementations

impl<T> Any for T where T: 'static + ?Sized,

fn type_id(&self) -> TypeId

impl<T> Borrow<T> for T where T: ?Sized,

fn borrow(&self) -> &T

impl<T> BorrowMut<T> for T where T: ?Sized,

fn borrow_mut(&mut self) -> &mut T

impl<T> From<T> for T

fn from(t: T) -> T

impl<T, U> Into<U> for T where U: From<T>,

fn into(self) -> U

impl<T, U> TryFrom<U> for T where U: Into<T>,

type Error = Infallible

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

impl<T, U> TryInto<U> for T where U: TryFrom<T>,

type Error = <U as TryFrom<T>>::Error

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

impl<V, T> VZip<V> for T where V: MultiLane<T>,

fn vzip(self) -> V

pub fn shortest_path_lens<TargetMap: DijkstraTargetMap<Graph>>(
&mut self,
graph: &Graph,
source: Graph::NodeIndex,
targets: &TargetMap,
target_amount: usize,
max_weight: WeightType,
forbid_source_target: bool,
distances: &mut Vec<(Graph::NodeIndex, WeightType)>
)

impl<Graph, WeightType, NodeWeights, Heap> RefUnwindSafe for Dijkstra<Graph, WeightType, NodeWeights, Heap> where
Graph: RefUnwindSafe,
Heap: RefUnwindSafe,
NodeWeights: RefUnwindSafe,
WeightType: RefUnwindSafe,

impl<Graph, WeightType, NodeWeights, Heap> Send for Dijkstra<Graph, WeightType, NodeWeights, Heap> where
Graph: Send,
Heap: Send,
NodeWeights: Send,
WeightType: Send,

impl<Graph, WeightType, NodeWeights, Heap> Sync for Dijkstra<Graph, WeightType, NodeWeights, Heap> where
Graph: Sync,
Heap: Sync,
NodeWeights: Sync,
WeightType: Sync,

impl<Graph, WeightType, NodeWeights, Heap> Unpin for Dijkstra<Graph, WeightType, NodeWeights, Heap> where
Graph: Unpin,
Heap: Unpin,
NodeWeights: Unpin,
WeightType: Unpin,

impl<Graph, WeightType, NodeWeights, Heap> UnwindSafe for Dijkstra<Graph, WeightType, NodeWeights, Heap> where
Graph: UnwindSafe,
Heap: UnwindSafe,
NodeWeights: UnwindSafe,
WeightType: UnwindSafe,

impl<T> Any for T where
T: 'static + ?Sized,

impl<T> Borrow<T> for T where
T: ?Sized,

impl<T> BorrowMut<T> for T where
T: ?Sized,

impl<T, U> Into<U> for T where
U: From<T>,

impl<T, U> TryFrom<U> for T where
U: Into<T>,

impl<T, U> TryInto<U> for T where
U: TryFrom<T>,

impl<V, T> VZip<V> for T where
V: MultiLane<T>,