Module rs_graph::search::biastar

Bidirectional A*-search.

This module implements a bidirectional A*-search for finding a shortest path between two nodes starting from both endpoints. Each node may be assigned a potential (or "heuristic value") estimating the distance to the target nodes. 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,t \in V$ are the start and destination nodes of the path, respectively, and $h_s\colon V \to \mathbb{R}$ and $h_t\colon V \to \mathbb{R}$ are lower bounds for the distance from each node $u \in V$ to $s$ and $t$, then the canonical choice of $h$ is \[ h\colon u \to \mathbb{R}, u \mapsto \frac12 (h_s(u) - h_t(u)). \]

Example

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

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

let s = nodes[&'s'];
let t = nodes[&'t'];

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

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

// Manhatten distance heuristic
let manh_heur = |u| {
    let (x, y) = coords(u);
    0.5 * (((x - xt).abs() + (y - yt).abs()) as f64 - ((x - xs).abs() + (y - ys).abs()) as f64)
};

let (path, dist) = biastar::find_undirected_path(&g, s, t, |e| weights[e.index()] as f64, manh_heur).unwrap();

assert!((dist - 14.0).abs() < 1e-6);

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| nodes[&c]).collect::<Vec<_>>());

// verify that we did not go too far in the "wrong" direction
for (v, _, _) in biastar::start_undirected(&g, s, t, |e| weights[e.index()] as f64, manh_heur) {
    let (x, y) = coords(v);
    assert!(x + 1 >= xs && x <= xt + 1 && y + 1 >= yt && y <= ys + 1);
}

Re-exports

pub use crate::search::astar::AStarHeuristic as Heuristic;

pub use super::astar::default_data;

Structs

BiAStar	Iterator for visiting edges in A*-order.
BiData	Predecessor edge information.

Enums

Direction

Direction of search.

Functions

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

Type Definitions

BiAStarDefault	BiAStar iterator with default data structures.
DefaultMap	Default map type to be used in an A* search.
DefaultPriQueue	Default priority queue type to be used in an A* search.