Struct rs_graph::shortestpath::dijkstra::Dijkstra

source ·

pub struct Dijkstra<'a, G, W, N, E, H = BinHeap<NodeItem<N, E, W>, usize>>where
    G: 'a + IndexGraph<'a, Node = N, Edge = E>,
    N: 'a + Node + Hash,
    E: 'a + Edge,
    W: NumAssign + Ord + Copy,
    H: Heap<Key = NodeItem<G::Node, G::Edge, W>, Item = usize>,{ /* private fields */ }

Expand description

Dijkstra’s shortest path algorithm.

Implementations

source

impl<'a, G, W, N, E, H> Dijkstra<'a, G, W, N, E, H>where
 G: 'a + IndexGraph<'a, Node = N, Edge = E>,
 N: 'a + Node + Hash,
 E: 'a + Edge,
 W: NumAssign + Ord + Copy,
 H: Heap<Key = NodeItem<G::Node, G::Edge, W>, Item = usize>,

source

pub fn new(g: &'a G) -> Self

Create new data structure for running Dijkstra on a graph.

source

pub fn undirected<Weights>(
 &mut self,
 weights: Weights,
 src: G::Node,
 snk: Option<G::Node>
) -> Vec<(G::Node, G::Edge)>where
 Weights: EdgeMap<'a, G, W>,

Compute a shortest path with Dijkstra’s algorithm on an undirected graph.

Each edge can be traversed in both directions with the same weight.

weights the (non-negative) edge weights
src the source node
snk the sink node

Return the incoming edge for each node forming the shortest path tree.

source

pub fn bidirected<Weights>(
 &mut self,
 weights: Weights,
 src: G::Node,
 snk: Option<G::Node>
) -> Vec<(G::Node, G::Edge)>where
 G: IndexNetwork<'a>,
 Weights: EdgeMap<'a, G, W>,

Solve shortest path with Dijkstra as bidirected graph.

The graph is considered as bidirected graph with different weights for each direction.

weights the (non-negative) arc weights
src the source node
snk the sink node

Return the incoming arc for each node forming the shortest path tree.

source

pub fn directed<Weights>(
 &mut self,
 weights: Weights,
 src: G::Node,
 snk: Option<G::Node>
) -> Vec<(G::Node, G::Edge)>where
 G: Digraph<'a>,
 Weights: EdgeMap<'a, G, W>,

Solve shortest path with Dijkstra as directed graph.

The graph is considered directed, travel is only allowed along outgoing edges.

weights the (non-negative) arc weights
src the source node
snk the sink node

Return the incoming arc for each node forming the shortest path tree.

source

pub fn generic<Weights, F, Neighs, It>(
 &mut self,
 weights: Weights,
 src: G::Node,
 snk: Option<G::Node>,
 accum: F,
 neighs: Neighs
) -> Vec<(G::Node, G::Edge)>where
 Weights: EdgeMap<'a, G, W>,
 F: Fn(W, W) -> W,
 Neighs: Fn(&'a G, G::Node) -> It,
 It: Iterator<Item = (G::Edge, G::Node)>,

Auto Trait Implementations

impl<'a, G, W, N, E, H> RefUnwindSafe for Dijkstra<'a, G, W, N, E, H>where
 G: RefUnwindSafe,
 H: RefUnwindSafe,
 N: RefUnwindSafe,

impl<'a, G, W, N, E, H> Send for Dijkstra<'a, G, W, N, E, H>where
 G: Sync,
 H: Send,
 N: Send,

impl<'a, G, W, N, E, H> Sync for Dijkstra<'a, G, W, N, E, H>where
 G: Sync,
 H: Sync,
 N: Sync,

impl<'a, G, W, N, E, H> Unpin for Dijkstra<'a, G, W, N, E, H>where
H: Unpin,
N: Unpin,

impl<'a, G, W, N, E, H> UnwindSafe for Dijkstra<'a, G, W, N, E, H>where
 G: RefUnwindSafe,
 H: UnwindSafe,
 N: UnwindSafe,

Blanket Implementations

source

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

source

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more

source

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

const: unstable · source

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more

source

impl<T> BorrowMut<T> for Twhere
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 Twhere
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 Twhere
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 Twhere
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 rs_graph::shortestpath::dijkstra::Dijkstra

Implementations

impl<'a, G, W, N, E, H> Dijkstra<'a, G, W, N, E, H>where
    G: 'a + IndexGraph<'a, Node = N, Edge = E>,
    N: 'a + Node + Hash,
    E: 'a + Edge,
    W: NumAssign + Ord + Copy,
    H: Heap<Key = NodeItem<G::Node, G::Edge, W>, Item = usize>,

pub fn new(g: &'a G) -> Self

pub fn undirected<Weights>(
    &mut self,
    weights: Weights,
    src: G::Node,
    snk: Option<G::Node>
) -> Vec<(G::Node, G::Edge)>where
    Weights: EdgeMap<'a, G, W>,

pub fn bidirected<Weights>(
    &mut self,
    weights: Weights,
    src: G::Node,
    snk: Option<G::Node>
) -> Vec<(G::Node, G::Edge)>where
    G: IndexNetwork<'a>,
    Weights: EdgeMap<'a, G, W>,

pub fn directed<Weights>(
    &mut self,
    weights: Weights,
    src: G::Node,
    snk: Option<G::Node>
) -> Vec<(G::Node, G::Edge)>where
    G: Digraph<'a>,
    Weights: EdgeMap<'a, G, W>,

Auto Trait Implementations

impl<'a, G, W, N, E, H> RefUnwindSafe for Dijkstra<'a, G, W, N, E, H>where
    G: RefUnwindSafe,
    H: RefUnwindSafe,
    N: RefUnwindSafe,

impl<'a, G, W, N, E, H> Send for Dijkstra<'a, G, W, N, E, H>where
    G: Sync,
    H: Send,
    N: Send,

impl<'a, G, W, N, E, H> Sync for Dijkstra<'a, G, W, N, E, H>where
    G: Sync,
    H: Sync,
    N: Sync,

impl<'a, G, W, N, E, H> Unpin for Dijkstra<'a, G, W, N, E, H>where
H: Unpin,
N: Unpin,

impl<'a, G, W, N, E, H> UnwindSafe for Dijkstra<'a, G, W, N, E, H>where
    G: RefUnwindSafe,
    H: UnwindSafe,
    N: UnwindSafe,

Blanket Implementations

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

fn type_id(&self) -> TypeId

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

fn borrow(&self) -> &T

impl<T> BorrowMut<T> for Twhere
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 Twhere
U: From<T>,

fn into(self) -> U

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

type Error = Infallible

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

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

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

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

Struct rs_graph::shortestpath::dijkstra::Dijkstra

Implementations

impl<'a, G, W, N, E, H> Dijkstra<'a, G, W, N, E, H>where G: 'a + IndexGraph<'a, Node = N, Edge = E>, N: 'a + Node + Hash, E: 'a + Edge, W: NumAssign + Ord + Copy, H: Heap<Key = NodeItem<G::Node, G::Edge, W>, Item = usize>,

pub fn new(g: &'a G) -> Self

pub fn undirected<Weights>( &mut self, weights: Weights, src: G::Node, snk: Option<G::Node>) -> Vec<(G::Node, G::Edge)>where Weights: EdgeMap<'a, G, W>,

pub fn bidirected<Weights>( &mut self, weights: Weights, src: G::Node, snk: Option<G::Node>) -> Vec<(G::Node, G::Edge)>where G: IndexNetwork<'a>, Weights: EdgeMap<'a, G, W>,

pub fn directed<Weights>( &mut self, weights: Weights, src: G::Node, snk: Option<G::Node>) -> Vec<(G::Node, G::Edge)>where G: Digraph<'a>, Weights: EdgeMap<'a, G, W>,

pub fn generic<Weights, F, Neighs, It>( &mut self, weights: Weights, src: G::Node, snk: Option<G::Node>, accum: F, neighs: Neighs) -> Vec<(G::Node, G::Edge)>where Weights: EdgeMap<'a, G, W>, F: Fn(W, W) -> W, Neighs: Fn(&'a G, G::Node) -> It, It: Iterator<Item = (G::Edge, G::Node)>,

Auto Trait Implementations

impl<'a, G, W, N, E, H> RefUnwindSafe for Dijkstra<'a, G, W, N, E, H>where G: RefUnwindSafe, H: RefUnwindSafe, N: RefUnwindSafe,

impl<'a, G, W, N, E, H> Send for Dijkstra<'a, G, W, N, E, H>where G: Sync, H: Send, N: Send,

impl<'a, G, W, N, E, H> Sync for Dijkstra<'a, G, W, N, E, H>where G: Sync, H: Sync, N: Sync,

impl<'a, G, W, N, E, H> Unpin for Dijkstra<'a, G, W, N, E, H>where H: Unpin, N: Unpin,

impl<'a, G, W, N, E, H> UnwindSafe for Dijkstra<'a, G, W, N, E, H>where G: RefUnwindSafe, H: UnwindSafe, N: UnwindSafe,

Blanket Implementations

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

fn type_id(&self) -> TypeId

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

fn borrow(&self) -> &T

impl<T> BorrowMut<T> for Twhere 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 Twhere U: From<T>,

fn into(self) -> U

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

type Error = Infallible

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

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

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

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

impl<'a, G, W, N, E, H> Dijkstra<'a, G, W, N, E, H>where
G: 'a + IndexGraph<'a, Node = N, Edge = E>,
N: 'a + Node + Hash,
E: 'a + Edge,
W: NumAssign + Ord + Copy,
H: Heap<Key = NodeItem<G::Node, G::Edge, W>, Item = usize>,

pub fn undirected<Weights>(
&mut self,
weights: Weights,
src: G::Node,
snk: Option<G::Node>
) -> Vec<(G::Node, G::Edge)>where
Weights: EdgeMap<'a, G, W>,

pub fn bidirected<Weights>(
&mut self,
weights: Weights,
src: G::Node,
snk: Option<G::Node>
) -> Vec<(G::Node, G::Edge)>where
G: IndexNetwork<'a>,
Weights: EdgeMap<'a, G, W>,

pub fn directed<Weights>(
&mut self,
weights: Weights,
src: G::Node,
snk: Option<G::Node>
) -> Vec<(G::Node, G::Edge)>where
G: Digraph<'a>,
Weights: EdgeMap<'a, G, W>,

pub fn generic<Weights, F, Neighs, It>(
&mut self,
weights: Weights,
src: G::Node,
snk: Option<G::Node>,
accum: F,
neighs: Neighs
) -> Vec<(G::Node, G::Edge)>where
Weights: EdgeMap<'a, G, W>,
F: Fn(W, W) -> W,
Neighs: Fn(&'a G, G::Node) -> It,
It: Iterator<Item = (G::Edge, G::Node)>,

impl<'a, G, W, N, E, H> RefUnwindSafe for Dijkstra<'a, G, W, N, E, H>where
G: RefUnwindSafe,
H: RefUnwindSafe,
N: RefUnwindSafe,

impl<'a, G, W, N, E, H> Send for Dijkstra<'a, G, W, N, E, H>where
G: Sync,
H: Send,
N: Send,

impl<'a, G, W, N, E, H> Sync for Dijkstra<'a, G, W, N, E, H>where
G: Sync,
H: Sync,
N: Sync,

impl<'a, G, W, N, E, H> Unpin for Dijkstra<'a, G, W, N, E, H>where
H: Unpin,
N: Unpin,

impl<'a, G, W, N, E, H> UnwindSafe for Dijkstra<'a, G, W, N, E, H>where
G: RefUnwindSafe,
H: UnwindSafe,
N: UnwindSafe,

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

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

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

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

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

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