Skip to content

graphfinder

Graph traversal & pathfinding with a compute core in Rust and an API in Python. It covers both uninformed search (BFS, DFS, UCS/Dijkstra) and informed search (Greedy, A*, Weighted A*, IDA*, beam), and it is built for teaching: every algorithm is the same loop, and you can watch it run.

A* exploring a maze
A* exploring a maze — blue is the expanded frontier, gold is the final path. One line of Python: gf.viz.animate_grid(maze, result).

Install

pip install graphfinder          # Python (prebuilt wheels)
cargo add graphfinder-core       # Rust crate

Thirty seconds

import graphfinder as gf

r = gf.search(gf.sample_maze("wall"), algorithm="astar", heuristic="manhattan")
print(r)        # SearchResult(found=True, cost=20, expanded=25, frontier=3, stop=goal)

The one idea

Every algorithm here is the same loop — Russell & Norvig's GENERAL-SEARCH — differing only in the frontier (which node comes out next) and the evaluation function priority = g_coeff·g(n) + h_coeff·h(n):

Algorithm Frontier g_coeff h_coeff Optimal?
BFS FIFO queue 1 0 only on unit costs
DFS LIFO stack 1 0 no
UCS/Dijkstra min-priority 1 0 yes
Greedy min-priority 0 1 no
A* min-priority 1 1 yes (admissible h)
Weighted A* min-priority 1 w within w× optimal

Run the same maze through each and the difference is immediate:

Six algorithms on the same maze

BFS and UCS flood the whole map; DFS wanders to a long path; Greedy beelines but overshoots the optimum; A* gets the optimal cost while exploring a fraction of what UCS does; Weighted A* trades a little optimality for even less work.

What's inside

  • Uninformed: BFS, DFS, UCS/Dijkstra, depth-limited (DLS), iterative deepening (IDDFS), bidirectional BFS.
  • Informed: Greedy best-first, A*, Weighted A*, IDA*, beam search.
  • Negative weights: Bellman–Ford (single-source, with negative-cycle detection) and Floyd–Warshall (all-pairs) — for the graphs Dijkstra/A* can't handle.
  • Domains: grid/maze worlds, explicit weighted graphs (CSR), implicit graphs via a Python successor callable, and random-graph generators (Erdős–Rényi, Barabási–Albert, Watts–Strogatz).
  • Heuristics: zero, Manhattan, Euclidean, octile.
  • Visualization: maze-search animation, static grids, frontier-size curves, work-vs-quality comparison, and general-graph plots.
  • Instrumentation: every run reports the path, cost, nodes expanded/ generated, peak frontier, stop reason, and a per-step trace.
  • Integrations: NetworkX, SciPy sparse adjacency, pandas DataFrames, OSMnx road networks, a safe LangChain routing tool, a Gymnasium GridWorld env with an A* oracle, and Graphviz export.
  • Reproducibility: seeded generators and deterministic tie-breaking.

Where to next

How is this different from networkx / rustworkx?

Those are excellent general graph libraries. graphfinder's niche is search pedagogy, step-by-step visualization and algorithm comparison, with a fast Rust core and GIL-free implicit state-space search (puzzles, large grids) as supporting features rather than the headline.

Author

graphfinder is created and maintained by Jose L. Salmeron (ORCID), CUNEF Universidad.

Citing

If you use graphfinder in academic work, please cite it — see the CITATION.cff in the repository. Licensed under MIT © Jose L. Salmeron.