Skip to content

Design & internals

graphfinder is a small Rust core with a thin Python binding. Its guiding principle: the search loop knows nothing about any concrete algorithm. Everything that distinguishes BFS from A* lives behind three traits.

Layout

crates/graphfinder-core/   Rust core — traits, the loop, domains, strategies
  src/traits.rs            Graph, Frontier, Heuristic
  src/search.rs            the single GENERAL-SEARCH loop + Algorithm +
                           SearchOptions + SearchResult
  src/state.rs             per-node bookkeeping (g, parent, closed), kept out of
                           the loop; hash-map and flat-vector backends
  src/frontier/            Fifo (BFS), Lifo (DFS), PriorityQueue (UCS/Greedy/A*)
  src/graph/               GridGraph (Cell), CsrGraph
  src/heuristic.rs         Zero, Manhattan, Euclidean, Octile
  src/strategies.rs        dls, iddfs, ida_star, beam_search, bidirectional
  src/domains/             maze + random-graph generators
  benches/search.rs        criterion benchmarks
  tests/properties.rs      property-based tests (proptest)
crates/graph-py/           PyO3 binding → the native module graphfinder_native
python/graphfinder/        Python API (dispatcher) + viz (matplotlib)

The three traits

pub trait Graph {
    type Node: Clone + Eq + Hash;
    fn neighbors(&self, node: &Self::Node) -> Vec<(Self::Node, f64)>;

    // Both optional, both defaulted: an allocation-free successor walk, and a
    // dense numbering of the nodes. See "Performance" below.
    fn neighbors_into(&self, node: &Self::Node, out: &mut Vec<(Self::Node, f64)>) { .. }
    fn dense_index(&self, node: &Self::Node) -> Option<usize> { None }
}

pub trait Heuristic<N> {
    fn estimate(&self, node: &N, goal: &N) -> f64;
}

pub trait Frontier<N> {
    fn push(&mut self, node: N, priority: f64);
    fn pop(&mut self) -> Option<N>;
    fn len(&self) -> usize;
}
  • Graph is the domain. Implement neighbors and every algorithm works on your type — grids, CSR graphs, implicit state spaces.
  • Heuristic is h(n). Zero works for any node type; the geometric ones are defined for grid Cells.
  • Frontier is the open list, and the single choice that names the algorithm: FIFO → BFS, LIFO → DFS, min-priority → UCS/Greedy/A*.

One loop to rule them all

An Algorithm bundles (frontier_kind, g_coeff, h_coeff). The loop pushes priority = g_coeff·g(n) + h_coeff·h(n) and lets the frontier decide order. That table is the library:

Algorithm Frontier g h
BFS FIFO 1 0
DFS LIFO 1 0
UCS Priority 1 0
Greedy Priority 0 1
A* Priority 1 1
Weighted A* Priority 1 w

Iterative-deepening and bidirectional search need their own thin driver around the same primitives — see src/strategies.rs — but never touch the inner loop.

Algorithm vs. options

Algorithm says which algorithm; SearchOptions says how to run it — instrumentation (record), a node budget (max_nodes), node reopening (reopen), and the bookkeeping backend (dense_state). Keeping them apart is what lets a new knob appear without breaking every caller:

use graphfinder_core::{search_with_options, Algorithm, GridGraph, Manhattan, SearchOptions};

let (grid, start, goal) = GridGraph::from_ascii("S..\n.#.\n..G");
let opts = SearchOptions::default().record(true).max_nodes(10_000);
let r = search_with_options(&grid, start, goal, Algorithm::astar(), &Manhattan, opts);

From Python the same knobs are keyword arguments (record=, max_nodes=, reopen=).

The Rust ↔ Python boundary

The binding (crates/graph-py) exposes three entry points:

  • search_grid / search_graph run native domains with the GIL released (py.allow_threads) for full speed.
  • search_implicit wraps a Python successor callable in a Graph impl that reacquires the GIL once per expansion — the same pattern lets you bring an arbitrary state space while the loop stays in Rust.

Results carry the path, metrics and the per-step trace back across the boundary as plain Python objects.

Instrumentation by default

Every run records nodes_expanded, nodes_generated, nodes_reopened, max_frontier_size, elapsed, stop_reason, and (with record=True) a per-step trace and search tree. Visualization is a first-class goal, so the trace is the contract the viz layer builds on.

nodes_expanded is the machine-independent measure of work — the one to quote when comparing algorithms. elapsed is what the run actually cost on this machine, in this build profile; it is the honest answer to "which is faster here", and nothing more.

In the per-step trace, g is the cost from the start when the node was expanded — or None where the question has no answer: bidirectional expands half of its nodes in a frontier growing backwards from the goal.

Performance

Performance is the fourth priority here, after visualization, comparison and clarity — so the rule is that it may not cost any of those three. Three changes carry almost all of it, and none is visible in the API:

  • the per-node bookkeeping hashes with FxHash rather than std's DoS-resistant SipHash: a pathfinding library's keys come from the caller's own graph, not from the network;
  • g, best parent and the closed flag live in one entry (src/state.rs), so a relaxation hashes the node once instead of up to four times;
  • successors are appended to one reused buffer through Graph::neighbors_into, instead of a fresh Vec per expansion.

Together those are 2–9× faster than 0.12.x, depending on the domain. There is one opt-in knob, SearchOptions::dense_state, which swaps the hash map for flat vectors indexed by Graph::dense_index:

search hash map flat vectors
BFS sweep of a 200×200 maze (~32 k cells) 2.11 ms 1.21 ms
BFS over a 50 k-node scale-free graph 4.81 ms 3.11 ms
A* down a corridor of a 1000×1000 grid (~2 k cells) 0.14 ms 4.24 ms

The last row is why it is opt-in: the vectors span every index up to the largest one touched, so a query that walks 2 000 cells to a far corner pays for a million slots. Turn it on for sweeps, leave it off for point-to-point queries. (It is not exposed in the Python API, where the typical call is that query.)

Reproduce any of this with:

cargo bench -p graphfinder-core --bench search -- --save-baseline before
# ...change something...
cargo bench -p graphfinder-core --bench search -- --baseline-lenient before

Correctness: properties, not just examples

Alongside the per-feature tests, tests/properties.rs checks the defining invariants over hundreds of random instances (proptest): the optimal algorithms agree on cost, A* never expands more than UCS, every returned path is walkable and priced exactly as reported, Weighted A* stays inside its w bound, Bellman–Ford and Floyd–Warshall agree with UCS where all three apply, node budgets are hard ceilings, results are reproducible, and the two bookkeeping backends give byte-identical answers. It exists so the loop can be optimised without anybody having to take "still correct" on trust.

Reproducibility

Random instances take a seed (ChaCha8 RNG). The priority queue breaks ties deterministically (FIFO on insertion order), so the same inputs always produce the same expansions — the tests depend on it.

Extending

  • New algorithm → usually just a constructor on Algorithm; a genuinely new discipline (e.g. iterative deepening) gets a driver in strategies.rs.
  • New domain → impl Graph.
  • New heuristic → impl Heuristic<N>.

Each addition ships a runnable example and a test asserting its defining property. See CONTRIBUTING.md and the API reference.