[−][src]Function rs_graph::search::astar::start_with_data

ⓘImportant traits for AStar<'a, A, D, W, M, P, H, Accum>
pub fn start_with_data<'a, A, D, W, H, M, P>(
    adj: A, 
    src: A::Node, 
    weights: W, 
    heur: H, 
    data: (M, P)
) -> AStar<'a, A, D, W, M, P, H, SumAccumulator> where
    A: Adjacencies<'a>,
    D: Copy + PartialOrd + Zero,
    W: Fn(A::Edge) -> D,
    H: AStarHeuristic<A::Node>,
    H::Result: Add<D, Output = D>,
    M: ItemMap<A::Node, Option<P::Item>>,
    P: ItemPriQueue<A::Node, Data<A::Edge, D, H::Result>>, 

Start and return an A*-iterator with custom data structures.

The returned iterator traverses the edges in the order of an A*-search. The iterator returns the next node, its incoming edge and the distance to the start node.

The heuristic is a assigning a potential to each node. The potential of all nodes must be so that $w(u,v) - h(u) + h(v) \ge 0$ for all edges $(u,v) \in E$. If $t$ is the destination node of the path then $h(u) - h(t)$ is a lower bound on the distance from $u$ to $t$ for each node $u \in V$ (in this case one usually chooses $h(t) = 0$). The value returned by the heuristic must be compatible with the distance type, i.e., is must be possible to compute the sum of both.

Note that the start node is not returned by the iterator.

The algorithm requires a pair (M, P) with M implementing ItemMap<Node, Item>, and P implementing ItemPriQueue<Node, D> as internal data structures. The map is used to store information about the last edge on a shortest path for each reachable node. The priority queue is used the handle the nodes in the correct order. The data structures can be reused for multiple searches.

This function uses the default data structures returned by default_data.

Parameter

  • adj: adjacency information for the graph
  • src: the source node at which the search should start.
  • weights: the weight function for each edge
  • heur: the heuristic used in the search
  • data: the custom data structures