Struct rs_graph::shortestpath::bidijkstra::BiDijkstra

pub struct BiDijkstra<'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>,  { /* fields omitted */ }

Bidirectional Dijkstra's shortest path algorithm.

Methods

impl<'a, G, W, N, E, H> BiDijkstra<'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>, 

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

Create new data structure for running Dijkstra on a graph.

fn undirected<'b>(
    &mut self,
    weights: &EdgeSlice<'a, 'b, G, W>,
    src: G::Node,
    snk: G::Node
) -> Vec<G::Edge>

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.

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

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.

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

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.

fn generic<Weights, Out, OutIt, In, InIt>(
    &mut self,
    weights: &Weights,
    src: G::Node,
    snk: G::Node,
    outedges: Out,
    inedges: In
) -> Vec<G::Edge> where
    Weights: Index<G::Edge, Output = W>,
    Out: Fn(&'a G, G::Node) -> OutIt,
    OutIt: Iterator<Item = (G::Edge, G::Node)>,
    In: Fn(&'a G, G::Node) -> InIt,
    InIt: Iterator<Item = (G::Edge, G::Node)>,