Metadata-Version: 2.4
Name: ursa-graph
Version: 0.1.0
Classifier: Development Status :: 2 - Pre-Alpha
Classifier: Programming Language :: Rust
Classifier: Programming Language :: Python :: 3
Classifier: Topic :: Scientific/Engineering
Requires-Dist: typing-extensions>=4.0 ; python_full_version < '3.11'
Requires-Dist: polars>=1.0 ; extra == 'polars'
Provides-Extra: polars
License-File: LICENSE-APACHE
License-File: LICENSE-MIT
Summary: Polars-shaped dataframes for graph data — a Rust/Arrow/DataFusion graph analytics library.
Keywords: graph,analytics,arrow,datafusion,polars,dataframe
Author: Ursa contributors
License: MIT OR Apache-2.0
Requires-Python: >=3.10
Description-Content-Type: text/markdown; charset=UTF-8; variant=GFM
Project-URL: Homepage, https://github.com/cldixon/ursa
Project-URL: Issues, https://github.com/cldixon/ursa/issues
Project-URL: Repository, https://github.com/cldixon/ursa

# 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`](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.

```python
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.

| Layer | State |
|---|---|
| **`ursa-core`** — CSR topology index + kernels | ✅ **Real & unit-tested.** Dense `u32` indexing, lazy-transpose CSR with the `edge_ids` permutation, and working `degree` / `pagerank` (pull-based) / `connected_components` (union-find) / `triangle_count` / `clustering_coefficient` (sorted-adjacency intersection) / `bfs` (frontier) / `closeness` / `betweenness` (Brandes, with source sampling) / `label_propagation` / `louvain` (modularity) kernels. Weighted variants are the remaining kernel work. |
| **`ursa-plan`** — DataFusion engine | ✅ **Unified plan.** Each `collect()` is **one** DataFusion `LogicalPlan` — `Limit → Sort → Filter → GraphAlgorithmNode` — where `GraphAlgorithmNode` is a real `UserDefinedLogicalNode` lowered to `GraphAlgorithmExec` by our own `ExtensionPlanner`. Graph ops are first-class citizens of the plan (not orchestrated from outside), which is where future optimizer rules register. A DataFusion scan reads Parquet/CSV edge/node files, local or from object storage (`s3://` / `gs://` / `az://`), with the column projection pushed into the file. |
| **`ursa-py`** — PyO3 bindings | ✅ **Wired.** Arrow in/out zero-copy (PyCapsule), GIL released during compute. |
| **Python dialect + `collect()`** | ✅ **Live & executing.** The Polars-shaped expression/plan builder, plus `collect()` for a standalone algorithm, a composed `with_columns(...).filter(...).sort(...).head(n)` pipeline, **node-attribute enrichment** (in-memory *or* `scan_nodes` file-backed tables joined by id, `ur.col("attr")` usable in filter/sort), **`neighbors().agg()`** over numeric *and* string attributes, the **traversals** `hop()` and `shortest_path()` (first-class `HopNode`/`ShortestPathNode` returning EdgeFrames) plus `random_walk()` (a `RandomWalkNode` returning a `(walk_id, step, node)` frame), and the whole-graph stats **`describe()`** / **`density()`** / **`avg_path_length()`** / **`diameter()`**. Over in-memory or `scan_edges`/`scan_nodes` sources — local files **or object storage** (`s3://` / `gs://` / `az://`, with `storage_options={...}`). |

```python
import ursa as ur, pyarrow as pa

edges = ur.from_arrow(pa.table({"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()

# 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.from_arrow(pa.table({"s": ["u1", "u1", "u2"], "d": ["u2", "u3", "u3"]}), src="s", dst="d")
ur.pagerank(str_edges).collect().to_polars()   # id column is Utf8
```

## 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](https://docs.astral.sh/uv/); linting and
formatting use [ruff](https://docs.astral.sh/ruff/) and type-checking uses
[ty](https://github.com/astral-sh/ty).

```bash
# 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](https://docs.astral.sh/uv/#installation); the Rust toolchain is pinned in
[`rust-toolchain.toml`](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.

Next, in rough priority order:

1. The direction-optimizing (top-down/bottom-up) BFS switch and weighted SSSP via
   delta-stepping, for scale.
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** — benchmarks vs NetworkX/rustworkx/igraph, a published docs site.
   (String/UUID node ids alongside int64 are already supported, auto-detected
   from the column type.)

## License

MIT OR Apache-2.0.

