Struct Dijkstra 

pub struct Dijkstra<'a, N, E, A, H, S = DefaultHashBuilder>
where
    A: GraphProps,
    H: HyperGraph<N, E, A>,
{ /* private fields */ }

Dijkstra’s shortest path algorithm for hypergraphs

Implementations

impl<'a, N, E, A, H, S> Dijkstra<'a, N, E, A, H, S>

where A: GraphProps, H: HyperGraph<N, E, A>, S: BuildHasher, A::Ix: RawIndex,

pub fn new(graph: &'a H) -> Self

where S: Default,

Create a new Dijkstra instance

pub const fn graph(&self) -> &H

returns a reference to the graph

pub const fn distances(&self) -> &HashMap<VertexId<A::Ix>, E, S>

returns a reference to the distances

pub const fn distances_mut(&mut self) -> &mut HashMap<VertexId<A::Ix>, E, S>

returns a mutable reference to the distances

pub const fn previous(&self) -> &HashMap<VertexId<A::Ix>, VertexId<A::Ix>, S>

returns a reference to the previous history

pub const fn previous_mut( &mut self, ) -> &mut HashMap<VertexId<A::Ix>, VertexId<A::Ix>, S>

returns a mutable reference to the previous history

pub const fn visited(&self) -> &VertexSet<A::Ix, S>

returns a reference to the visited vertices

pub const fn visited_mut(&mut self) -> &mut VertexSet<A::Ix, S>

returns a mutable reference to the visited vertices

pub fn set_distances( &mut self, distances: HashMap<VertexId<A::Ix>, E, S>, ) -> &mut Self

update the distances and returns a mutable reference to the instance

pub fn set_previous( &mut self, previous: HashMap<VertexId<A::Ix>, VertexId<A::Ix>, S>, ) -> &mut Self

update the previous history and returns a mutable reference to the instance

pub fn set_visited(&mut self, visited: VertexSet<A::Ix, S>) -> &mut Self

update the visited vertices and returns a mutable reference to the instance

pub fn add_distance( &mut self, vertex: VertexId<A::Ix>, distance: E, ) -> &mut Self

where A::Ix: Eq + Hash,

add a new node to the distances

pub fn add_previous( &mut self, vertex: VertexId<A::Ix>, previous: VertexId<A::Ix>, ) -> &mut Self

where A::Ix: Eq + Hash,

add a vertex to the previous history

pub fn add_visited(&mut self, vertex: VertexId<A::Ix>) -> &mut Self

where A::Ix: Eq + Hash,

record a vertex as visited

pub fn find_path( &mut self, start: VertexId<A::Ix>, dest: VertexId<A::Ix>, ) -> Result<<Self as PathFinder<A::Ix>>::Path>

where Self: PathFinder<A::Ix>,

Find the shortest path from start to goal

pub fn search( &mut self, start: VertexId<A::Ix>, ) -> Result<<Self as Search<VertexId<A::Ix>>>::Output>

where Self: Search<VertexId<A::Ix>>,

search for a path starting from start to the vertex with the largest ID

pub fn has_visited<Q>(&self, vertex: &Q) -> bool

where Q: ?Sized + Eq + Hash, A::Ix: Eq + Hash, VertexId<A::Ix>: Borrow<Q>,

returns true if the vertex is visited

pub fn reset(&mut self) -> &mut Self

Reset the state for reuse

Trait Implementations

impl<'a, N, E, A, H, S> PathFinder<<A as GraphProps>::Ix> for Dijkstra<'a, N, E, A, H, S>

where E: Copy + Default + PartialOrd + FromPrimitive + Num + UpperBounded, A: GraphProps, H: HyperGraph<N, E, A>, S: BuildHasher, A::Ix: HyperIndex, <H::Edge<E> as RawLayout>::Store: Clone + IntoIterator<Item = VertexId<A::Ix>>,

type Path = Vec<IndexBase<<A as GraphProps>::Ix>>

fn find_path( &mut self, src: VertexId<A::Ix>, dest: VertexId<A::Ix>, ) -> Result<Self::Path>

returns a

fn reconstruct_path(&self, goal: VertexId<A::Ix>) -> Vec<VertexId<A::Ix>>

impl<'a, N, E, A, H> Search<IndexBase<<A as GraphProps>::Ix>> for Dijkstra<'a, N, E, A, H>

where E: Copy + Default + PartialOrd + FromPrimitive + Num + UpperBounded, A: GraphProps, H: HyperGraphIter<N, E, A>, A::Ix: HyperIndex, <H::Edge<E> as RawLayout>::Store: Clone + IntoIterator<Item = VertexId<A::Ix>>,

type Output = Vec<IndexBase<<A as GraphProps>::Ix>>

fn search(&mut self, start: VertexId<A::Ix>) -> Result<Self::Output>

begins a search of the graph, starting with the given index.

impl<'a, N, E, A, H, S> Traversal<IndexBase<<A as GraphProps>::Ix>> for Dijkstra<'a, N, E, A, H, S>

where A: GraphProps, H: HyperGraph<N, E, A>, S: BuildHasher, A::Ix: Eq + Hash,

type Store<I2> = HashSet<I2, S>

defines the associated container used to store visited vertices

fn has_visited(&self, vertex: &VertexId<A::Ix>) -> bool

Check if the search has visited a specific vertex

fn visited(&self) -> &Self::Store<VertexId<A::Ix>>

Get all vertices that have been visited during the search