Module rs_graph::search::astar

source ·
Expand description

A* search.

This module implements an A*-search for finding a shortest paths from some node to all other nodes. Each node may be assigned a potential (or “heuristic value”) estimating the distance to the target node. The potential $h\colon V \to \mathbb{R}$ must satisfy \[ w(u,v) - h(u) + h(v) \ge 0, (u,v) \in E \] where $w\colon E \to \mathbb{R}$ are the weights (or lengths) of the edges. (The relation must hold for both directions in case the graph is undirected).

If $s \in V$ is the start node and $t$ some destination node, then $h(u) - h(t)$ is a lower bound on the distance from $u$ to $t$ for all nodes $u \in V$. Hence, f the shortest path to some specific destination node $t$ should be found the canonical choice for $h$ is such that $h(t) = 0$ and $h(u)$ is a lower bound on the distance from $u$ to $t$.

Example

use rs_graph::traits::*;
use rs_graph::search::astar;
use rs_graph::string::{from_ascii, Data};
use rs_graph::LinkedListGraph;

let Data {
    graph: g,
    weights,
    nodes,
} = from_ascii::<LinkedListGraph>(
    r"
    *--1--*--1--*--1--*--1--*--1--*--1--*--1--*
    |     |     |     |     |     |     |     |
    1     1     1     1     1     1     1     1
    |     |     |     |     |     |     |     |
    *--1--*--2--*--1--*--2--e--1--f--1--t--1--*
    |     |     |     |     |     |     |     |
    1     1     1     1     1     2     1     1
    |     |     |     |     |     |     |     |
    *--1--*--1--*--2--c--1--d--1--*--2--*--1--*
    |     |     |     |     |     |     |     |
    1     1     1     1     1     1     1     1
    |     |     |     |     |     |     |     |
    *--1--s--1--a--1--b--2--*--1--*--1--*--1--*
    |     |     |     |     |     |     |     |
    1     1     1     1     1     1     1     1
    |     |     |     |     |     |     |     |
    *--1--*--1--*--1--*--1--*--1--*--1--*--1--*
    ",
)
.unwrap();

let s = g.id2node(nodes[&'s']);
let t = g.id2node(nodes[&'t']);

// nodes are numbered row-wise -> get node coordinates
let coords = |u| ((g.node_id(u) % 8) as isize, (g.node_id(u) / 8) as isize);

let (xs, ys) = coords(s);
let (xt, yt) = coords(t);

// manhatten distance heuristic
let manh_heur = |u| {
    let (x, y) = coords(u);
    ((x - xt).abs() + (y - yt).abs()) as usize
};

// verify that we do not go in the "wrong" direction
for (v, _, _) in astar::start(g.neighbors(), s, |e| weights[e.index()], manh_heur) {
    let (x, y) = coords(v);
    assert!(x >= xs && x <= xt && y >= yt && y <= ys);
    if v == t {
        break;
    }
}

// obtain the shortest path directly
let (path, dist) = astar::find_undirected_path(&g, s, t, |e| weights[e.index()], manh_heur).unwrap();

assert_eq!(dist, 7);

let mut pathnodes = vec![s];
for e in path {
    let uv = g.enodes(e);
    if uv.0 == *pathnodes.last().unwrap() {
        pathnodes.push(uv.1);
    } else {
        pathnodes.push(uv.0);
    }
}
assert_eq!(pathnodes, "sabcdeft".chars().map(|c| g.id2node(nodes[&c])).collect::<Vec<_>>());

Structs

  • AStar
    A* search iterator.
  • Data
    The data stored with an edge during the search.
  • SumAccumulator
    Accumulates by adding distance and weight.

Traits

  • AStarHeuristic
    A heuristic providing a node potential.
  • Accumulator
    A binary operation used to accumulate edge weight and distance.

Functions

  • find_directed_path
    Run an A*-search on a directed graph and return the path.
  • find_undirected_path
    Run an A*-search on an undirected graph and return the path.
  • start
    Start and return an A*-iterator using default data structures.
  • start_directed
    Start an A*-search on a directed graph.
  • start_generic
    Start and return an A*-iterator with a custom accumulator and custom data structures.
  • start_undirected
    Start an A*-search on a undirected graph.
  • start_with_data
    Start and return an A*-iterator with custom data structures.

Type Aliases