API reference¶
Reference generated from the docstrings of the graphfinder package.
Search¶
graphfinder ¶
graphfinder — graph traversal & pathfinding with a Rust core, Python API.
The computation runs in Rust (native module graphfinder_native); this Python
layer adds an ergonomic search dispatcher and (Phase 4) visualization.
Example
import graphfinder as gf r = gf.search(gf.sample_maze("open"), algorithm="astar") r.found True
explicit weighted graph¶
edges = gf.gen_barabasi_albert(100, 3, seed=1) r = gf.search_graph(100, edges, start=0, goal=99, algorithm="bidirectional")
implicit graph (states are ints or tuples of ints)¶
def succ(s): ... return [(s + 1, 1.0), (s * 2, 1.0)] if s < 50 else [] r = gf.search(succ, start=1, goal=27, algorithm="bfs")
weighted terrain: digits 1-9 are costs, or a full matrix¶
gf.search("S99G
1111", algorithm="ucs").cost # 5.0 >>> gf.search_grid_costs([[1, 1], [9, 1]], (0, 0), (1, 1))
Algorithms (algorithm=): "bfs", "dfs", "ucs"/"dijkstra", "greedy", "astar",
"weighted_astar", "iddfs", "dls", "ida_star", "beam", "bidirectional".
Heuristics (heuristic=): a built-in grid name ("zero", "manhattan",
"euclidean", "octile") or a custom callable h(node, goal) -> float (works
in any domain — grids, explicit graphs and implicit graphs).
For graphs with negative edge weights (where Dijkstra/A* do not apply) use
:func:bellman_ford (single source, detects negative cycles) and
:func:floyd_warshall (all pairs):
>>> sp = gf.bellman_ford(3, [(0, 1, 4.0), (0, 2, 5.0), (1, 2, -3.0)], source=0)
>>> sp.dist[2], sp.path_to(2) # (1.0, [0, 1, 2])
>>> ap = gf.floyd_warshall(3, [(0, 1, 4.0), (1, 2, -3.0)])
>>> ap.distance(0, 2), ap.path(0, 2)
search ¶
Convenience dispatcher over the domain type.
domainis astr→ treated as an ASCII maze map (search_grid).domainis callable → an implicit graph successor function (search_implicit);startandgoalare required.
For explicit graphs use :func:search_graph directly. Extra keyword
arguments are forwarded to the underlying function.
search_grid
builtin
¶
search_grid(map, algorithm='astar', heuristic=None, record=True, weight=2.0, beam_width=None, depth_limit=None, max_nodes=None, diagonal=False)
Search a 2-D maze given as an ASCII map (# wall, S start, G goal, a
digit 1–9 = a free cell with that terrain cost).
heuristic is a built-in name ("zero", "manhattan", "euclidean",
"octile") or a custom callable h((row, col), (row, col)) -> float.
search_grid_costs
builtin
¶
search_grid_costs(costs, start, goal, algorithm='astar', heuristic=None, record=True, weight=2.0, beam_width=None, depth_limit=None, max_nodes=None, diagonal=False)
Search a grid built from a matrix of terrain costs. costs[r][c] is the
movement cost of entering cell (r, c); a non-positive or non-finite value
marks a wall. start and goal are (row, col) tuples. Same heuristic
options as [search_grid].
search_graph
builtin
¶
search_graph(num_nodes, edges, start, goal, algorithm='bfs', heuristic=None, undirected=True, record=True, weight=2.0, beam_width=None, depth_limit=None, max_nodes=None)
Search an explicit weighted graph given as an edge list over 0..num_nodes.
heuristic defaults to the zero heuristic (so the informed algorithms behave
as their uninformed counterparts). Pass a custom callable
h(node, goal) -> float (nodes are ints) to run a real A* / Greedy — e.g.
straight-line distance when your nodes have coordinates. weight sets the
w for weighted_astar.
search_implicit
builtin
¶
search_implicit(successors, start, goal, algorithm='astar', heuristic=None, record=True, weight=2.0, beam_width=None, depth_limit=None, max_nodes=None)
Search an implicit graph defined by a Python successor callable
successors(state) -> [(state, cost), ...]. States are ints or tuples of
ints. heuristic, if given, is a callable h(state, goal) -> float.
Shortest paths¶
Negative-weight shortest-path algorithms. See Shortest paths.
graphfinder — graph traversal & pathfinding with a Rust core, Python API.
The computation runs in Rust (native module graphfinder_native); this Python
layer adds an ergonomic search dispatcher and (Phase 4) visualization.
Example
import graphfinder as gf r = gf.search(gf.sample_maze("open"), algorithm="astar") r.found True
explicit weighted graph¶
edges = gf.gen_barabasi_albert(100, 3, seed=1) r = gf.search_graph(100, edges, start=0, goal=99, algorithm="bidirectional")
implicit graph (states are ints or tuples of ints)¶
def succ(s): ... return [(s + 1, 1.0), (s * 2, 1.0)] if s < 50 else [] r = gf.search(succ, start=1, goal=27, algorithm="bfs")
weighted terrain: digits 1-9 are costs, or a full matrix¶
gf.search("S99G
1111", algorithm="ucs").cost # 5.0 >>> gf.search_grid_costs([[1, 1], [9, 1]], (0, 0), (1, 1))
Algorithms (algorithm=): "bfs", "dfs", "ucs"/"dijkstra", "greedy", "astar",
"weighted_astar", "iddfs", "dls", "ida_star", "beam", "bidirectional".
Heuristics (heuristic=): a built-in grid name ("zero", "manhattan",
"euclidean", "octile") or a custom callable h(node, goal) -> float (works
in any domain — grids, explicit graphs and implicit graphs).
For graphs with negative edge weights (where Dijkstra/A* do not apply) use
:func:bellman_ford (single source, detects negative cycles) and
:func:floyd_warshall (all pairs):
>>> sp = gf.bellman_ford(3, [(0, 1, 4.0), (0, 2, 5.0), (1, 2, -3.0)], source=0)
>>> sp.dist[2], sp.path_to(2) # (1.0, [0, 1, 2])
>>> ap = gf.floyd_warshall(3, [(0, 1, 4.0), (1, 2, -3.0)])
>>> ap.distance(0, 2), ap.path(0, 2)
bellman_ford
builtin
¶
Bellman–Ford single-source shortest paths on an explicit weighted graph.
Unlike Dijkstra/A*, this tolerates negative edge weights and reports a
reachable negative cycle. Edges are (u, v, w) over 0..num_nodes.
undirected defaults to False: negative weights are the whole point,
and an undirected negative edge is itself a trivial negative cycle.
floyd_warshall
builtin
¶
Floyd–Warshall all-pairs shortest paths on an explicit weighted graph.
O(V³) — for small/medium or dense graphs where you want every distance
at once. Tolerates negative edges and flags any negative cycle. Edges are
(u, v, w) over 0..num_nodes; undirected defaults to False.
Instances¶
graphfinder — graph traversal & pathfinding with a Rust core, Python API.
The computation runs in Rust (native module graphfinder_native); this Python
layer adds an ergonomic search dispatcher and (Phase 4) visualization.
Example
import graphfinder as gf r = gf.search(gf.sample_maze("open"), algorithm="astar") r.found True
explicit weighted graph¶
edges = gf.gen_barabasi_albert(100, 3, seed=1) r = gf.search_graph(100, edges, start=0, goal=99, algorithm="bidirectional")
implicit graph (states are ints or tuples of ints)¶
def succ(s): ... return [(s + 1, 1.0), (s * 2, 1.0)] if s < 50 else [] r = gf.search(succ, start=1, goal=27, algorithm="bfs")
weighted terrain: digits 1-9 are costs, or a full matrix¶
gf.search("S99G
1111", algorithm="ucs").cost # 5.0 >>> gf.search_grid_costs([[1, 1], [9, 1]], (0, 0), (1, 1))
Algorithms (algorithm=): "bfs", "dfs", "ucs"/"dijkstra", "greedy", "astar",
"weighted_astar", "iddfs", "dls", "ida_star", "beam", "bidirectional".
Heuristics (heuristic=): a built-in grid name ("zero", "manhattan",
"euclidean", "octile") or a custom callable h(node, goal) -> float (works
in any domain — grids, explicit graphs and implicit graphs).
For graphs with negative edge weights (where Dijkstra/A* do not apply) use
:func:bellman_ford (single source, detects negative cycles) and
:func:floyd_warshall (all pairs):
>>> sp = gf.bellman_ford(3, [(0, 1, 4.0), (0, 2, 5.0), (1, 2, -3.0)], source=0)
>>> sp.dist[2], sp.path_to(2) # (1.0, [0, 1, 2])
>>> ap = gf.floyd_warshall(3, [(0, 1, 4.0), (1, 2, -3.0)])
>>> ap.distance(0, 2), ap.path(0, 2)
sample_maze
builtin
¶
A named sample maze as an ASCII map. name is "open" or "wall".
random_maze_ascii
builtin
¶
A reproducible random maze rendered as an ASCII map (with S/G).
gen_barabasi_albert
builtin
¶
Barabási–Albert scale-free graph → edge list.
gen_watts_strogatz
builtin
¶
Watts–Strogatz small-world graph → edge list.
Visualization¶
graphfinder.viz ¶
Visualization helpers. Consume the SearchResult from the Rust core.
Requires matplotlib (pip install graphfinder[viz]). Functions:
- animate_grid(map, result) # the flagship: watch the search explore
- plot_grid(map, result, ax=None) # static snapshot (terrain + visited + path)
- plot_costs(map, ax=None) # terrain-cost heatmap with a colourbar
- plot_frontier(result, ax=None) # frontier size per expansion (memory)
- compare(results) # bar charts across algorithms
- plot_graph(n, edges, result) # general graph, nodes coloured by state
Grid helpers accept either an ASCII map (digits 1–9 are terrain costs) or
the terrain-cost matrix passed to search_grid_costs.
matplotlib is imported lazily inside each function, so importing this module is cheap and never required for the core search API.
animate_grid ¶
Animate the search exploring the maze, then trace the final path.
Each frame marks the next expanded cell; once the frontier has been replayed, the solution path is drawn cell by cell. This is the flagship "watch A* explore" visualization.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
map
|
str
|
the ASCII map searched. |
required |
result
|
SearchResult
|
run with |
required |
interval
|
int
|
milliseconds between frames. |
60
|
show_path
|
bool
|
append the path-drawing frames at the end. |
True
|
Returns:
| Type | Description |
|---|---|
FuncAnimation
|
matplotlib.animation.FuncAnimation: the animation (in a notebook, |
FuncAnimation
|
display it with |
plot_grid ¶
Static snapshot: terrain shading, expanded cells, and the path on top.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
map
|
str | list[list[float]]
|
the ASCII map, or the terrain-cost matrix
passed to |
required |
result
|
SearchResult
|
from a search run with |
required |
ax
|
Axes
|
axes to draw on; created if omitted. |
None
|
Returns:
| Type | Description |
|---|---|
Axes
|
matplotlib.axes.Axes: the axes the grid was drawn on. |
plot_costs ¶
Heatmap of the terrain costs (walls left blank), with a colourbar.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
map
|
str | list[list[float]]
|
ASCII map (digits = costs) or cost matrix. |
required |
ax
|
Axes
|
axes to draw on; created if omitted. |
None
|
Returns:
| Type | Description |
|---|---|
Axes
|
matplotlib.axes.Axes: the axes the heatmap was drawn on. |
plot_frontier ¶
Plot frontier size per expansion step — the memory profile of the search (the graph-search analogue of a convergence curve).
compare ¶
Bar charts comparing algorithms on the same problem.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
results
|
dict[str, SearchResult]
|
|
required |
Returns:
| Type | Description |
|---|---|
Figure
|
matplotlib.figure.Figure: two panels — nodes expanded, and path cost. |
plot_graph ¶
Draw an explicit graph with nodes coloured by their role in the search: grey = untouched, blue = expanded, gold = on the path, green/red = start/goal.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
num_nodes
|
int
|
number of nodes (ids |
required |
edges
|
list
|
|
required |
result
|
SearchResult
|
from |
required |
ax
|
Axes
|
axes to draw on; created if omitted. |
None
|
node_size
|
int
|
scatter marker size. |
80
|
Returns:
| Type | Description |
|---|---|
Axes
|
matplotlib.axes.Axes: the axes the graph was drawn on. |
Integrations¶
See Integrations for usage. Each returns a LabeledResult.
graphfinder.integrations ¶
Optional ecosystem integrations for graphfinder.
Each submodule bridges a popular library to graphfinder's search, and has its own optional dependency:
pip install "graphfinder[networkx]" # search over networkx graphs
pip install "graphfinder[scipy]" # search over scipy.sparse adjacency
pip install "graphfinder[pandas]" # edge-list DataFrames + result tables
Imports are lazy: importing this package pulls in none of the extras. Access a
submodule by attribute (gf.integrations.networkx) or import it directly
(from graphfinder.integrations import networkx). The heavy dependency is only
needed when you actually call a function.
All search helpers return a :class:LabeledResult, which maps the path back
to your original node labels while keeping the native SearchResult in
.raw (for metrics and graphfinder.viz).
LabeledResult
dataclass
¶
A search result with nodes mapped back to their original labels.
Mirrors the native SearchResult fields, but path uses your labels
(networkx nodes, DataFrame ids, …). The native result is kept in raw
(its path/trace use the internal integer ids).
graphfinder.integrations.networkx ¶
NetworkX integration: run graphfinder's search over a networkx graph.
from graphfinder.integrations import networkx as gfnx
path = gfnx.search(G, source, target, algorithm="astar",
heuristic=lambda u, v: ...).path
Requires networkx (pip install "graphfinder[networkx]").
search ¶
Search for a path from source to target in a networkx graph.
A drop-in alternative to nx.shortest_path / nx.astar_path that also
reports search instrumentation. Directed graphs are honoured automatically.
Extra keyword arguments (heuristic, weight of weighted_astar,
beam_width, max_nodes, record, …) pass through to
:func:graphfinder.search_graph.
Returns a :class:graphfinder.integrations.LabeledResult whose path uses
the original networkx node labels.
to_edgelist ¶
Map a networkx graph to graphfinder's edge-list form.
Returns (num_nodes, edges, index, labels, directed) where index maps
each node label to an integer id and labels is the reverse list. Edge
weights are read from the weight attribute (default 1.0).
graphfinder.integrations.scipy ¶
SciPy integration: run graphfinder's search over a scipy.sparse adjacency
matrix — a drop-in alternative to scipy.sparse.csgraph shortest-path routines
that also reports search instrumentation.
from graphfinder.integrations import scipy as gfsp
r = gfsp.search(adjacency_csr, source=0, target=n - 1, algorithm="dijkstra")
Requires scipy (pip install "graphfinder[scipy]"). Node ids are the
matrix indices 0..n-1.
search ¶
Search for a path in a scipy.sparse adjacency matrix.
directed defaults to True (matching scipy.sparse.csgraph); set it
to False to treat the matrix as undirected. Extra keyword arguments pass
through to :func:graphfinder.search_graph.
Returns a :class:graphfinder.integrations.LabeledResult (node ids are the
matrix indices).
graphfinder.integrations.pandas ¶
pandas integration: build a graph from an edge-list DataFrame and turn
search results into tidy tables.
from graphfinder.integrations import pandas as gfpd
r = gfpd.search(df, "A", "F", source="from", target="to", weight="cost")
gfpd.trace_dataframe(r) # per-expansion table
gfpd.compare_dataframe(results) # one row per algorithm
Requires pandas (pip install "graphfinder[pandas]").
search ¶
search(df, source_node, target_node, source='source', target='target', weight=None, directed=False, algorithm='dijkstra', **kwargs)
Search a graph described by an edge-list DataFrame.
source_node/target_node are the start/goal labels; source/
target/weight are column names. Extra keyword arguments pass through
to :func:graphfinder.search_graph. Returns a
:class:graphfinder.integrations.LabeledResult with the original labels.
trace_dataframe ¶
A tidy DataFrame of the per-expansion trace: step, node, g,
frontier_size. The search must have been run with record=True.
compare_dataframe ¶
One row per algorithm: found, cost, nodes_expanded, nodes_generated,
max_frontier_size, path_len. results is a {name: result} dict of
LabeledResult or native SearchResult.
graphfinder.integrations.osm ¶
Geographic routing on road networks (OSMnx).
Two layers:
- :func:
searchruns A between two nodes of a geographic* networkx graph — one whose nodes carryx(longitude) andy(latitude) attributes, as OSMnx graphs do — using a great-circle (haversine) heuristic. It only needsnetworkx. - :func:
routeand :func:plot_routeare convenience wrappers around OSMnx (nearest-node lookup from lat/lon points, and map plotting). They requireosmnx(pip install "graphfinder[osm]").
The haversine heuristic is admissible when the edge weight is physical length
in metres (OSMnx's length), so A* returns the shortest route.
search ¶
A* between node ids orig and dest on a geographic networkx graph.
Edge cost is read from the weight attribute (default "length"); the
heuristic is the haversine distance from each node's x/y (lon/lat)
attributes to the goal. Directed graphs are honoured. Extra keyword arguments
(record, max_nodes, the weight multiplier of weighted_astar,
…) pass through to :func:graphfinder.search_graph.
Returns a :class:graphfinder.integrations.LabeledResult whose path uses
the original (OSM) node ids.
route ¶
Route between two (lat, lon) points on an OSMnx graph.
Snaps each point to its nearest graph node (via osmnx) and then calls
:func:search. Requires osmnx.
plot_route ¶
Plot a route over the OSMnx graph. result is a
:class:~graphfinder.integrations.LabeledResult (or a list of node ids).
Requires osmnx; extra keyword arguments pass to ox.plot_graph_route.
haversine ¶
Great-circle distance in metres between two (lat, lon) points.
graphfinder.integrations.agents ¶
Agent integration: expose graphfinder routing as a safe LLM tool.
Two layers:
- :func:
make_routerbuilds a plain, dependency-freerouter(source, target, algorithm=None) -> dictbound to a fixed graph. It validates inputs, caps the work withmax_nodesand restricts the algorithm to a safe allow-list, so it is safe to hand to an autonomous agent. - :func:
as_langchain_toolwraps that router as a LangChainStructuredTool(requireslangchain-core;pip install "graphfinder[agents]").
The graph is bound at tool-creation time; the agent only chooses source and
target (and optionally an allowed algorithm).
make_router ¶
Build a bound router(source, target, algorithm=None) -> dict.
edges is a list of (u, v) or (u, v, weight) with arbitrary
hashable labels. The returned function maps labels internally, runs the
search with a hard max_nodes budget, and returns a JSON-friendly dict:
{found, path, cost, nodes_expanded, stop_reason} (or {error: ...} for
bad input) — never raises, so it is safe inside an agent loop.
as_langchain_tool ¶
Wrap :func:make_router as a LangChain StructuredTool.
The graph is bound now; the agent supplies source/target (and an
optional allowed algorithm). Requires langchain-core.
graphfinder.integrations.gym ¶
Gymnasium integration: a GridWorld reinforcement-learning environment backed by a graphfinder grid, plus an A* oracle.
from graphfinder.integrations import gym as gfgym
env = gfgym.GridWorldEnv("S....\n.###.\n....G")
obs, info = env.reset()
action = gfgym.optimal_action(env) # what A* would do from here
The oracle (optimal_path / optimal_action) makes the environment useful
for imitation learning, reward shaping, or scoring an RL agent against the
optimal policy. Requires gymnasium (pip install "graphfinder[gym]").
GridWorldEnv ¶
Bases: Env
A grid navigation environment over a graphfinder map.
The agent starts at S and must reach G. Walls are #; a digit
1–9 is terrain that costs that much to enter. Observations are the
flattened cell index (Discrete(H*W)); actions are moves
(Discrete(4), or Discrete(8) with diagonal=True). The reward is
the negative cost of entering the target cell (×√2 diagonally); an
illegal move (into a wall or off-grid) keeps the agent in place with reward
-1. Episodes end on reaching the goal, or truncate at max_steps.
optimal_path ¶
The A* shortest path of cells from the agent's current position to the
goal (None if unreachable).
optimal_action ¶
The action index A* would take from the agent's current position
(None at the goal or if unreachable).
graphfinder.integrations.graphviz ¶
Graphviz integration: export a graph (and a found path) to DOT / SVG.
from graphfinder.integrations import graphviz as gfgv
dot = gfgv.to_dot(edges, result) # a DOT string — no dependency
gfgv.source(edges, result).render("route", format="svg") # needs graphviz
to_dot builds the DOT text itself, so it needs nothing; source wraps it in
a graphviz.Source you can render or display in a notebook (requires the
graphviz Python package, and the Graphviz dot binary to render).
to_dot ¶
Build a Graphviz DOT string for an edge-list graph, highlighting the path
from result (a LabeledResult or anything with a .path).
Nodes on the path are gold, the start green and the goal red; path edges are drawn thick. Edge weights (the optional 3rd item of each edge) become labels.
source ¶
Return a graphviz.Source for the graph (renderable / notebook-display).
Requires the graphviz package (pip install "graphfinder[graphviz]").