rxgraph

High-performance graph traversal and graph algorithms for Python, implemented in Rust with an ergonomic object API and Polars expression support.

rxgraph supports:

1. Efficient graph construction leveraging Arrow-backed DataFrames as inputs
2. Optimized stateful search, where the traversal predicates are expressed with Poalrs expressions
3. Common graph algorithms like BFS, DFS, shortest path, weakly connected components, etc.

From initial benchmarks, rxgraph is comparable in performance and CPU/memory consumption (and very possibly better in some cases) with igraph and networkx.

The place where rxgraph really shines is stateful search - you can use rxgraph for stateful blind search across a very large graph. See the traversal example in Quickstart.

The main focus of this library is Python and its Python bindings, but its Rust core is also published as a crate to crates.io.

Installation

# uv
uv add rxgraph polars

# pip
pip install rxgraph polars

Quick Start

import rxgraph as rxg

graph = rxg.Graph.from_edges(
    [("a", "b"), ("a", "c"), ("b", "d"), ("c", "d")],
    nodes=["a", "b", "c", "d", "isolated"],
)

assert graph.node_count == 5
assert graph.edge_count == 4
assert graph.bfs("a") == ["a", "b", "c", "d"]
assert graph.shortest_path("a", "d") == ["a", "b", "d"]
assert graph.reachable_nodes("isolated") == ["isolated"]

For the most powerful capability of rxgraph, see the Stateful Search example.

Data Model

For small or Python-native graphs, use Graph.from_edges with hashable node labels:

routes = rxg.Graph.from_edges(
    [
        ("a", "b", {"price": 5, "kind": "route"}),
        ("b", "c", {"price": 6, "kind": "route"}),
        ("a", "c", {"price": 100, "kind": "skip"}),
    ],
    nodes=[
        ("a", {"closed": False}),
        ("b", {"closed": False}),
        ("c", {"closed": False}),
    ],
)

For table-backed graphs, pass Polars DataFrames directly:

import polars as pl
import rxgraph as rxg

nodes = pl.DataFrame(
    {"id": [10, 20, 30]},
    schema={"id": pl.UInt64},
)
edges = pl.DataFrame(
    {"id": [1, 2], "src": [10, 20], "dest": [20, 30]},
    schema={"id": pl.UInt64, "src": pl.UInt64, "dest": pl.UInt64},
)

table_graph = rxg.Graph(nodes, edges)
assert table_graph.shortest_path(10, 30) == [10, 20, 30]

Node tables require an id column. Edge tables require id, src, and dest. All identity columns must be either unsigned integers or strings. Extra columns remain available to traversal expressions.

Algorithms

The high-level object API includes:

• bfs(start, max_depth=None)
• dfs(start, max_depth=None)
• reachable_nodes(start)
• shortest_path(source, target)
• out_degrees(), in_degrees(), and degrees()
• weakly_connected_components()

These methods return the same labels or IDs used to build the graph.

Stateful Search

Graph.search evaluates Polars expressions against candidate edges. Expressions can read source-node fields (src.*), destination-node fields (dest.*), edge fields (edge.*), and path state (state.*).

Using the routes graph from the data model example:

s = lambda name: rxg.col(f"state.{name}")
d = lambda name: rxg.col(f"dest.{name}")
e = lambda name: rxg.col(f"edge.{name}")

result = routes.search(
    start_nodes=["a"],
    visit=(~d("closed")) & (e("kind") != "skip") & ((s("spent") + e("price")) < 20),
    next_state={"spent": s("spent") + e("price")},
    stop=rxg.col("dest.id") == rxg.lit(routes.node_id("c")),
    initial_state={"spent": 0},
    max_depth=3,
    max_paths=10,
)

path = result.paths[0]
assert path.nodes == ["a", "b", "c"]
assert path.edges == [0, 1]
assert path.state == {"spent": 11}

Search supports DFS or BFS ordering, optional Rayon-backed parallel traversal, depth/path limits, and optional intermediate state materialization.

Search kernels evaluate supported Polars scalar, list, and struct expressions natively in Rust. List and struct columns/state can be read and updated inside visit, next_state, and stop. Polars JSON list literals are intentionally not decoded yet; use list columns or list state for list-valued operands.

See examples/nyc_taxi_zone_search.py for a public NYC TLC trip-record example that uses list and struct state over millions of raw trip edges.

Native Rust kernels

While the Polars expression DSL covers most stateful searches with no compilation step, when you need arbitrary state types, logic the DSL cannot express, or the last bit of performance, you can supply a native Rust kernel instead. A plugin package imports like rxgraph, but binds the Python API to its own native backend:

import rxgraph_hop_budget as rxg

graph = rxg.Graph.from_edges([("a", "b"), ("b", "c")])
result = graph.search(
    start_nodes=["a"],
    kernel="hop_budget",
    params={"max_hops": 3, "target_col": "target"},
)

File-backed graphs use the same plugin path and keep Python out of the search loop:

graph = rxg.Graph.from_parquet(
    nodes="nodes.parquet",
    edges="edges.parquet",
    payloads="lazy",
)

The consumer's crate depends on rxgraph with the python feature (their own crate is the cdylib that needs pyo3's extension-module; rxgraph's python feature deliberately does not enable it):

[dependencies]
rxgraph = { version = "0.6", features = ["python"] }
pyo3 = { version = "0.28", features = ["extension-module"] }

The Rust side implements rxgraph::TypedKernel, decodes payload structs with TryFrom<rxgraph::ArrowRow<'_>>, and ends with a small macro call:

rxgraph::typed_plugin! {
    module = _native;
    "hop_budget" => HopBudget::from_params,
}

See examples/rust-kernel-plugin/ for the full guide, including the typed payload shape and the maturin build.

Streaming native searches

Use search_batches with a named native kernel to pull results incrementally:

with graph.search_batches(
    start_nodes=["a"],
    kernel="hop_budget",
    params={"max_hops": 3, "profile_col": "profile", "policy_col": "policy"},
    batch_size=1024,
) as stream:
    for paths in stream:
        for path in paths:
            print(path.nodes, path.state)
    print(stream.stats)

The example assumes graph comes from a plugin registering hop_budget. Batches contain at most batch_size paths and may be smaller. No traversal runs between pulls. Typed decoding and lazy file setup happen on the first pull. Closing releases the session's graph references and lazy caches; paths already returned remain usable. Shared eager decode caches stay available for later searches. Use the context manager when breaking early. stats is cumulative and remains readable after close.

Serial DFS/BFS ordering and the global max_paths limit are preserved. Parallel ordering is unspecified. Typed eager and lazy Parquet stores currently execute serially, as they do with search. DSL streaming is deferred. Custom native runners must implement the optional streaming capability; standard plugin wrappers provide it automatically when rebuilt against this version.

Streaming bounds retained output, not BFS frontier size or payload-cache memory. A graph's payload tables cannot be replaced while a stream retains them. batch_size=1 favors latency; the default is 1024 to amortize Python overhead. Performance results and the explicit acceptance gates are documented in benches/NATIVE_PERFORMANCE.md.

Architecture

The Python package is backed by a Rust core. Internally, rxgraph stores node and edge tables as Arrow RecordBatch values, validates graph identity columns once, and builds compact CSR topology for traversal. User columns stay in columnar form and remain available to stateful search expressions.

Rust Crate

The Rust engine is published as the rxgraph crate and exposes the same traversal kernel model used by the Python bindings.

See crates/rxgraph/README.md for crate-specific usage.