NetworkX Oracle Test Suite

Purpose: Verify YogEx algorithm outputs against NetworkX — the de-facto reference implementation for graph algorithms in Python — using property-based testing.

Overview

The oracle suite treats NetworkX as a ground-truth oracle. For every property test, a random graph is generated, fed to both YogEx and NetworkX, and the results are compared. If YogEx disagrees with NetworkX, the property fails and StreamData prints a deterministic seed so the failure is reproducible.

This is not a replacement for unit tests (those live in test/yog/) — it is a cross-implementation parity layer that catches semantic drift, edge-case mishandling, and subtle bugs that unit tests alone rarely reach.

Methodology

Harness Architecture

┌─────────────────┐     JSON payload      ┌──────────────────────┐
│  Elixir test    │ ─────────────────────>│  Python dispatcher   │
│  (ExUnit +      │  (graph + algorithm   │  (run_algorithm.py)  │
│   StreamData)   │   + options)          │                      │
│                 │                       │  ┌───────────────┐   │
│  YogEx result   │ <─────────────────────│  │  NetworkX     │   │
│     vs          │     JSON result       │  │  adapter      │   │
│  NetworkX result│                       │  └───────────────┘   │
└─────────────────┘                       └──────────────────────┘

1. Graph marshalling — Yog.Oracle.NetworkX.encode_graph/1 serialises a Yog.Graph to JSON. Atoms are converted to strings, and other JSON-compatible types (integers, strings) are passed through as-is.
2. Subprocess dispatch — System.cmd/3 spawns python3 run_algorithm.py <tmpfile>. Each call is isolated, debuggable, and avoids NIF complexity.
3. Result decoding — decode_result/2 reverses the encoding and normalises shapes (e.g. "__Inf__" → :infinity, nested dicts → %{node_id => value}).
4. Property assertion — ExUnit compares the decoded NetworkX result against the YogEx result.

Adapter Health Check

Before any oracle property runs, the harness executes 10 round-trip self-tests (NetworkX.adapter_health/0):

If any self-test fails, the entire oracle suite is skipped with a clear reason — never a silent pass.

NetworkX vs YogEx Parity Matrix

* Leiden uses Louvain as the NetworkX proxy because NetworkX does not ship a native Leiden implementation.

Legend

Outcome

Current Suite Statistics

Known Semantic Differences

These are intentional or documented divergences where YogEx and NetworkX use different conventions. The oracle adapters normalise where possible; otherwise the test generators avoid the divergence.

Centrality Deferral

The centrality category is split into two piles for the next re-engagement pass:

1. Numeric convention deltas — both sides terminate, but values differ by a documented factor or normalization option. Tractable with adapter-side flags or Elixir-side normalization.

   • Closeness on disconnected graphs (Wasserman-Faust correction)
   • Harmonic on isolated nodes
   • Betweenness normalization options

2. Convergence / stability failures — one side raises or values disagree non-deterministically. Requires the input generator to exclude pathological inputs.

   • Eigenvector on dominant-eigenvalue ambiguity
   • Katz when α · ρ(A) ≥ 1
   • PageRank on dangling nodes

Running the Oracle Suite

Prerequisites

# Python dependencies
pip install -r test/oracle/scripts/requirements.txt
# Contents: networkx==3.6.1, numpy>=1.24, scipy>=1.11

Fast suite (excludes oracle)

mix test

Oracle suite only

mix test --include oracle test/oracle/

Single oracle module

mix test --include oracle test/oracle/pathfinding_oracle_test.exs

CI Configuration

The project uses a split CI strategy:

File Layout

test/oracle/
├── README.md                       # This file
├── nx_oracle.ex                    # Elixir harness (marshal, spawn, decode)
├── nx_oracle_test.exs              # Adapter health check (10 self-tests)
├── pathfinding_oracle_test.exs     # 8 properties
├── flow_oracle_test.exs            # 3 properties
├── mst_oracle_test.exs             # 4 properties (arborescence deferred — 🔴 divergent root choice)
├── centrality_oracle_test.exs      # 3 properties (degree exact; rest deferred)
├── connectivity_oracle_test.exs    # 3 properties
├── properties_oracle_test.exs      # 5 properties
├── matching_oracle_test.exs        # 4 properties
├── traversal_oracle_test.exs       # 3 properties
└── scripts/
    ├── run_algorithm.py            # Python entry point
    ├── requirements.txt            # Pinned Python deps
    └── adapters/
        ├── __init__.py             # Dispatch table
        ├── centrality.py
        ├── connectivity.py
        ├── flow.py
        ├── matching.py
        ├── mst.py
        ├── pathfinding.py
        ├── properties.py
        └── traversal.py

Adding a New Oracle Property

1. Add the NetworkX adapter in test/oracle/scripts/adapters/<category>.py:

   def my_algorithm(graph, options):
       return nx.my_algorithm(graph, **options)

   Register it in the module's DISPATCH dict and in adapters/__init__.py.

2. Add the Elixir property in test/oracle/<category>_oracle_test.exs:

   @tag :oracle
   property "P-ORAC-CAT-NNN My algorithm agrees with NetworkX" do
     check all(graph <- my_generator(), max_runs: 50) do
       yog_result = Yog.MyModule.my_algorithm(graph)
       nx_result  = NetworkX.run("my_algorithm", graph, [])
       assert yog_result == nx_result
     end
   end

3. Run the suite:

   mix test --include oracle test/oracle/<category>_oracle_test.exs
   

References

• NetworkX Documentation
• StreamData Property-Based Testing
• ALGORITHMS.md — YogEx algorithm catalog