Struct AStarSearch 

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

An A* Search algorithm implementation for hypergraphs

Implementations

impl<'a, N, E, A, F, H, S, K, Idx> AStarSearch<'a, N, E, A, F, H, S>

where A: GraphProps<Ix = Idx, Kind = K>, H: HyperGraph<N, E, A>, F: Heuristic<Idx>, S: BuildHasher, K: GraphType, Idx: RawIndex,

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

where S: Default,

Create a new A* search instance with the given heuristic function

pub fn with_heuristic<G>( self, heuristic: G, ) -> AStarSearch<'a, N, E, A, G, H, S>

where G: Heuristic<Idx, Output = F::Output>,

consumes the current instance to create another from the given heuristic function; note: while the functions may be different, the output type of both must match.

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

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

returns a mutable reference to the map of vertices that have been processed

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

returns an immutable reference to the closed set of vertices

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

returns a mutable reference to the closed set of vertices

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

returns an immutable reference to the f_score map

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

returns a mutable reference to the f_score map

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

returns an immutable reference to the g_score map

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

returns a mutable reference to the g_score map

pub const fn heuristic(&self) -> &F

returns an immutable reference to the heuristic function of the algorithm

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

returns an immutable reference to the set of vertices that have been visited

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

returns amutable reference to the open set of vertices

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

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

returns true if the given vertex has a f_score

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

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

returns true if the given vertex has a g_score

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

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

returns true if the given vertex has been visited

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

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

returns true if the given vertex is in the open set

pub fn move_open_to_closed(&mut self, vertex: &VertexId<Idx>)

where Idx: Copy + Eq + Hash,

moves the vertex from the open set before inserting it into the closed set; this is useful for updating the state, marking a node as processed.

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

reset the state

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

where Self: PathFinder<Idx>,

find a path between two nodes

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

where Self: Search<VertexId<Idx>>,

a convience method to perform a search

Trait Implementations

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

where A: GraphProps, H: HyperGraph<N, E, A>, F: Heuristic<A::Ix, Output = f64>, S: BuildHasher, A::Ix: HyperIndex, for<'b> &'b <H::Edge<E> as RawLayout>::Store: IntoIterator<Item = &'b VertexId<A::Ix>>,

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

Find the shortest path between start and goal vertices

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

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

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

where A: GraphProps, F: Heuristic<A::Ix, Output = f64>, H: HyperGraphIter<N, E, A>, S: BuildHasher, A::Ix: HyperIndex, for<'b> &'b <H::Edge<E> as RawLayout>::Store: IntoIterator<Item = &'b 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, F, A, H, S> Traversal<IndexBase<<A as GraphProps>::Ix>> for AStarSearch<'a, N, E, A, F, H, S>

where A: GraphProps, F: Heuristic<A::Ix, Output = f64>, H: HyperGraph<N, E, A>, S: BuildHasher, A::Ix: Eq + Hash,

type Store<U> = HashSet<U, 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