Skip to content

API reference

Reference generated from the docstrings of the graphfinder package.

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

search(domain, start=None, goal=None, **kwargs)

Convenience dispatcher over the domain type.

  • domain is a str → treated as an ASCII maze map (search_grid).
  • domain is callable → an implicit graph successor function (search_implicit); start and goal are 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 19 = 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(num_nodes, edges, source, undirected=False)

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(num_nodes, edges, undirected=False)

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

sample_maze(name)

A named sample maze as an ASCII map. name is "open" or "wall".

random_maze_ascii builtin

random_maze_ascii(width, height, obstacle_density, seed)

A reproducible random maze rendered as an ASCII map (with S/G).

gen_erdos_renyi builtin

gen_erdos_renyi(n, p, seed)

Erdős–Rényi G(n, p) random graph → edge list.

gen_barabasi_albert builtin

gen_barabasi_albert(n, m, seed)

Barabási–Albert scale-free graph → edge list.

gen_watts_strogatz builtin

gen_watts_strogatz(n, k, beta, seed)

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 19 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_grid(map, result, interval=60, show_path=True) -> matplotlib.animation.FuncAnimation

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 record=True (needs the trace).

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 HTML(anim.to_jshtml())).

plot_grid

plot_grid(map, result, ax: Axes | None = None) -> matplotlib.axes.Axes

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 search_grid_costs.

required
result SearchResult

from a search run with record=True.

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

plot_costs(map, ax: Axes | None = None) -> matplotlib.axes.Axes

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(result, ax: Axes | None = None, label=None) -> matplotlib.axes.Axes

Plot frontier size per expansion step — the memory profile of the search (the graph-search analogue of a convergence curve).

compare

compare(results) -> matplotlib.figure.Figure

Bar charts comparing algorithms on the same problem.

Parameters:

Name Type Description Default
results dict[str, SearchResult]

{algorithm_name: result}.

required

Returns:

Type Description
Figure

matplotlib.figure.Figure: two panels — nodes expanded, and path cost.

plot_graph

plot_graph(num_nodes, edges, result, ax: Axes | None = None, node_size=80) -> matplotlib.axes.Axes

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 0..num_nodes).

required
edges list

(u, v, weight) tuples (as returned by the generators).

required
result SearchResult

from search_graph (run with record=True).

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(graph, source, target, algorithm='dijkstra', weight='weight', **kwargs)

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

to_edgelist(graph, weight='weight')

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(matrix, source, target, algorithm='dijkstra', directed=True, **kwargs)

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

trace_dataframe(result)

A tidy DataFrame of the per-expansion trace: step, node, g, frontier_size. The search must have been run with record=True.

compare_dataframe

compare_dataframe(results)

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:search runs A between two nodes of a geographic* networkx graph — one whose nodes carry x (longitude) and y (latitude) attributes, as OSMnx graphs do — using a great-circle (haversine) heuristic. It only needs networkx.
  • :func:route and :func:plot_route are convenience wrappers around OSMnx (nearest-node lookup from lat/lon points, and map plotting). They require osmnx (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

search(graph, orig, dest, weight='length', x='x', y='y', algorithm='astar', **kwargs)

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(graph, orig_point, dest_point, weight='length', **kwargs)

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_route(graph, result, **kwargs)

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

haversine(lat1, lon1, lat2, lon2)

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_router builds a plain, dependency-free router(source, target, algorithm=None) -> dict bound to a fixed graph. It validates inputs, caps the work with max_nodes and restricts the algorithm to a safe allow-list, so it is safe to hand to an autonomous agent.
  • :func:as_langchain_tool wraps that router as a LangChain StructuredTool (requires langchain-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

make_router(edges, directed=False, default_algorithm='dijkstra', max_nodes=200000)

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

as_langchain_tool(edges, name='find_route', description=None, directed=False, **router_kwargs)

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 19 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

optimal_path(env)

The A* shortest path of cells from the agent's current position to the goal (None if unreachable).

optimal_action

optimal_action(env)

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

to_dot(edges, result=None, directed=False, name='G')

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

source(edges, result=None, directed=False, name='G')

Return a graphviz.Source for the graph (renderable / notebook-display). Requires the graphviz package (pip install "graphfinder[graphviz]").