Ursa — Polars-shaped dataframes for graph data

Status: v0.1 in progress. An in-memory, single-machine graph analytics library with a dataframe-first API — what Polars is to tabular data, for graphs. The engine foundation is in place: real algorithm kernels, and collect() executing as one DataFusion plan with graph ops as first-class logical nodes. The full design lives in docs/SPEC.md; this README describes what is actually built right now and how the pieces fit.

Ursa is a Rust core (Apache Arrow throughout), a DataFusion query engine with graph operators as first-class plan nodes, and a fluent, Polars-shaped Python expression API. There is no Graph object — an EdgeFrame is the graph, and every operation returns a frame.

import ursa as ur

edges = ur.scan_edges("web-google.csv", src="FromNodeId", dst="ToNodeId")
top = (
    edges.nodes()
    .with_columns(
        pagerank  = ur.pagerank(edges, damping=0.85),
        in_degree = ur.degree(edges, direction="in"),
    )
    .sort("pagerank", descending=True)
    .head(20)
    .collect()          # runs as one DataFusion plan; results are Arrow
)

What works today

The architecture, crate boundaries, and load-bearing seams are all in place, and the parts that prove the design is sound are real and tested end-to-end.

import ursa as ur

# The EdgeFrame *is* the graph. Build one from native Python data — a list of
# row dicts, a dict of columns, a polars/pandas DataFrame, or pyarrow. No
# `import pyarrow` required; `src`/`dst` name the endpoint columns:
edges = ur.EdgeFrame(
    [{"s": 1, "d": 0}, {"s": 2, "d": 0}, {"s": 3, "d": 0}, {"s": 0, "d": 1}],
    src="s",
    dst="d",
)
# equivalently: ur.EdgeFrame({"s": [1, 2, 3, 0], "d": [0, 0, 0, 1]}, src="s", dst="d")

# Composed pipeline — runs through DataFusion end to end:
(
    edges.nodes()
    .with_columns(pr=ur.pagerank(edges), indeg=ur.degree(edges, direction="in"))
    .filter(ur.col("indeg") > 0)
    .sort("pr", descending=True)
    .head(10)
    .collect()
    .to_polars()
)

# ...or straight from a file (Parquet/CSV, projection pushed into the scan):
ur.pagerank(ur.scan_edges("edges.parquet", src="s", dst="d")).collect().to_polars()

# However the frame is built — constructor, from_polars/from_pandas/from_arrow,
# or scan_edges — it behaves identically from here on.

# Node ids may be int64 (the fast path) or strings (e.g. UUIDs) — auto-detected
# from the column type; results come back keyed by the original ids:
str_edges = ur.EdgeFrame({"s": ["u1", "u1", "u2"], "d": ["u2", "u3", "u3"]}, src="s", dst="d")
ur.pagerank(str_edges).collect().to_polars()   # id column is Utf8

NodeFrame(data, id=...) is the matching constructor for an attribute table (joined to the graph by id); a NodeFrame is optional — nodes are implicit in the edges (edges.nodes()), and attributes are a separate table you attach when you have them.

Architecture

ursa/
├── ursa-core/    # Topology (CSR) + algorithm kernels. Pure Rust: arrow + rayon.
│                 # NO DataFusion dependency. Independently testable.
├── ursa-plan/    # DataFusion extensions: custom logical node + ExecutionPlan
│                 # (-> ursa-core), the query builder, scan/session plumbing.
│                 # The ONE seam where our dialect lowers to DataFusion.
│                 # (optimizer rules + object_store: future work)
├── ursa-py/      # PyO3 bindings. Thin: plan builders, collect(), Arrow FFI.
└── python/ursa/  # Python package: dialect, frames, IO, graph verbs, stats.

Governing rule: Arrow at the boundaries, index in the middle. Every kernel takes Arrow columns plus a shared topology index in, and hands Arrow arrays out.

Why DataFusion (not the Polars crates): extensibility is the designed use case — graph ops must be first-class citizens of one query plan, not coordinated by a "traffic cop" around a closed planner. The accepted cost is that we own a Polars-shaped expression frontend; it is deliberately quarantined at one seam — python/ursa/_expr.py builds the dialect, and ursa-plan/src/query.rs lowers it (today a small JSON column IR + comparison filters) to a DataFusion plan.

Develop

The Python side is managed with uv; linting and formatting use ruff and type-checking uses ty.

# Rust core: real kernels, fast to build/test (arrow + rayon only)
cargo test -p ursa-core

# Whole workspace (compiles DataFusion; slower)
cargo check

# Python: uv creates the venv, builds the maturin extension, and installs the
# dev dependency group in one step.
uv sync

uv run pytest                     # pure-Python tests + native-kernel tests
uv run ruff check .               # lint
uv run ruff format .              # format
uv run ty check                   # type-check

uv run rebuilds the native extension as needed, so editing Rust and re-running uv run pytest picks up the change. Requirements: Python ≥ 3.10 and uv; the Rust toolchain is pinned in rust-toolchain.toml (rustup installs it automatically), so local cargo clippy uses the exact same lint set as CI.

Roadmap

The engine foundation is in place — every collect() is one DataFusion plan with custom graph logical nodes — and many features have fanned out on top of it: node-valued algorithms (pagerank, degree, connected_components, triangle_count, clustering_coefficient, closeness, betweenness, label_propagation, louvain), composed pipelines, scan_edges/scan_nodes sources, node-attribute enrichment (in-memory or file-backed tables joined by id), neighbors().agg() over numeric and string attributes, the traversals hop() and shortest_path() (each its own first-class logical node returning an EdgeFrame, on a shared single-source BFS kernel family) plus random_walk(), the eager whole-graph stats density / avg_path_length / diameter and the one-row describe, object-storage scans (s3:// / gs:// / az:// via object_store, with storage_options), and sink_parquet/sink_csv egress.

Weighted algorithms are live across the board: weight= is a per-operation expression over edge columns (weight=ur.col("amount") * ur.col("fx")), evaluated to an f64 per edge and gathered per CSR slot via the edge_ids permutation. Weighted PageRank, shortest_path (Dijkstra), closeness, betweenness (Dijkstra-Brandes), and louvain all ship.

A few relational verbs are modelled in the plan (so they compose and show in .explain()) but are not yet executable and raise a clear error when collected: sample, group_by().agg, join, and schema.

Next, in rough priority order:

1. Scale-oriented kernel refinements: the direction-optimizing (top-down/bottom-up) BFS switch, and delta-stepping for the (already shipping, Dijkstra-based) weighted SSSP.
2. Optimizer rules — push node-set filters before traversal, fuse neighbors().agg into a segmented CSR reduction. (The topology index is now built once and shared across ops over a frame — the index-preservation contract — which is the seam these rules register on.)
3. Breadth — a published docs site, and broadening the benchmark coverage. The cross-library benchmark flywheel is live in benchmarks/ — a typer/rich CLI that races Ursa against NetworkX, rustworkx, and igraph across nine algorithms, separates cold end-to-end from warm kernel time, cross-checks every result against the NetworkX oracle, and writes raw rows to Parquet so leaderboards and gap-hunting are re-renderable downstream steps. (String/UUID node ids alongside int64 are already supported, auto-detected from the column type.)

License

MIT OR Apache-2.0.