Metadata-Version: 2.4
Name: pygraphc
Version: 0.1.0
Summary: Fast graph algorithms with C kernels — connected components via union-find
Author-email: Lennart Jansen <lejansen.home@gmail.com>
License-Expression: MIT
Project-URL: Homepage, https://github.com/lejansenGitHub/networkc
Project-URL: Repository, https://github.com/lejansenGitHub/networkc
Project-URL: Issues, https://github.com/lejansenGitHub/networkc/issues
Keywords: graph,connected-components,union-find,c-extension
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Developers
Classifier: Programming Language :: C
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Topic :: Scientific/Engineering :: Mathematics
Classifier: Typing :: Typed
Requires-Python: >=3.11
Description-Content-Type: text/markdown
License-File: LICENSE
Provides-Extra: dev
Requires-Dist: pytest>=8.0; extra == "dev"
Requires-Dist: pytest-mock>=3.0; extra == "dev"
Requires-Dist: pytest-cov>=6.0; extra == "dev"
Requires-Dist: diff-cover>=9.0; extra == "dev"
Requires-Dist: ruff>=0.15; extra == "dev"
Requires-Dist: mypy>=1.14; extra == "dev"
Requires-Dist: pre-commit>=4.0; extra == "dev"
Provides-Extra: benchmark
Requires-Dist: pytest>=8.0; extra == "benchmark"
Requires-Dist: scipy>=1.14; extra == "benchmark"
Requires-Dist: numpy>=2.0; extra == "benchmark"
Dynamic: license-file

# networkc

Fast, general-purpose graph algorithm library implemented in C, callable from Python. Zero runtime dependencies.

Edges use **original node IDs** — no manual index mapping needed. A C-side hash map translates IDs to internal indices automatically.

## Benchmarks

### vs networkx (graph algorithms)

End-to-end from domain objects using split lists (gather + algorithm). Sparse random graphs, ~3 edges per node.

| Algorithm | Nodes | networkc | networkx | Speedup |
|-----------|------:|-------:|---------:|--------:|
| Connected Components | 1K | 0.0001s | 0.001s | **17x** |
| Connected Components | 10K | 0.001s | 0.011s | **21x** |
| Connected Components | 100K | 0.011s | 0.313s | **29x** |
| Connected Components | 1M | 0.150s | 6.83s | **46x** |
| Bridges | 1M | 0.401s | 21.42s | **53x** |
| Articulation Points | 1M | 0.350s | 8.97s | **26x** |
| BFS | 1M | 0.165s | 13.62s | **82x** |
| Dijkstra | 1M | 0.390s | 11.11s | **29x** |
| Edge paths (cutoff=5) | 80 | 0.00005s | 0.006s | **~100x** |
| SCC (directed) | 1M | 0.154s | 6.16s | **40x** |
| WCC (directed) | 1M | 0.033s | 2.06s | **62x** |
| Topological sort | 1M | 0.084s | 2.17s | **26x** |
| DAG longest path | 1M | 0.175s | 5.66s | **32x** |
| Cycle basis | 100K | 0.019s | 18.9s | **989x** |

### vs pgmpy (DAG structure learning)

Hill-climb with K2 scoring on binary variables. Both produce identical DAGs.

| Scenario | networkc | pgmpy | Speedup |
|----------|-------:|------:|--------:|
| 5 vars, 100 samples | 0.00003s | 0.021s | **~700x** |
| 5 vars, 1000 samples | 0.00007s | 0.012s | **~170x** |
| 10 vars, 100 samples | 0.00005s | 0.044s | **~900x** |
| 10 vars, 500 samples | 0.0001s | 0.045s | **~410x** |
| 10 vars, 1000 samples | 0.0002s | 0.046s | **~220x** |
| 15 vars, 500 samples | 0.0002s | 0.103s | **~430x** |
| 15 vars, 1000 samples | 0.0004s | 0.104s | **~270x** |
| 20 vars, 500 samples | 0.0005s | 0.192s | **~420x** |
| 20 vars, 1000 samples | 0.0007s | 0.192s | **~290x** |

**17x–900x faster** than the standard Python packages, with identical results. Zero construction overhead for directed graphs (forward + reverse CSR uses the same 2m memory as undirected).

## Installation

```bash
pip install -e .
```

Or from GitHub:

```bash
pip install git+https://github.com/lejansenGitHub/networkc.git
```

Requires a C compiler (the extension is compiled at install time with `-O3`).

## API

### Structural algorithms

```python
from networkc import (
    connected_components,
    bridges,
    articulation_points,
    biconnected_components,
    bfs,
    two_edge_connected_components,
    nodes_on_simple_paths,
)

node_ids = [100, 200, 300, 400]
edges = [(100, 200), (300, 400)]  # pairs of original node IDs

# Connected components
for component in connected_components(node_ids, edges):
    print(component)  # {100, 200}, {300, 400}

# Bridge edges
bridges(node_ids, edges)  # [(100, 200), (300, 400)]

# Articulation points
articulation_points(node_ids, edges)  # set()

# Biconnected components
list(biconnected_components(node_ids, edges))  # [{100, 200}, {300, 400}]

# BFS traversal
bfs(node_ids, edges, 100)  # [100, 200]

# 2-edge-connected components (bridges removed, then CC)
list(two_edge_connected_components(node_ids, edges))

# Nodes on any simple path from source to targets (block-cut tree)
nodes_on_simple_paths(node_ids, edges, source=100, targets=[400])
```

### Connected components with branch IDs

Track which branch IDs belong to each connected component:

```python
from networkc import connected_components_with_branch_ids

node_ids = [100, 200, 300, 400]
edges = [(100, 200), (300, 400)]
branch_ids = [901, 902]  # one per edge

for nodes, branches in connected_components_with_branch_ids(node_ids, edges, branch_ids):
    print(nodes, branches)
# {100, 200} {901}
# {300, 400} {902}
```

Also available on `Graph` and `GraphView`. Pass `branch_ids` at construction, then exclude by domain ID:

```python
g = Graph([1, 2, 3], [(1, 2), (2, 3)], branch_ids=[100, 200])
list(g.connected_components_with_branch_ids())
# [({1, 2, 3}, {100, 200})]

# Exclude branches by ID — dropped from connectivity and branch sets
view = g.without_branches([200])  # exclude branch 200 (edge 2--3)
list(view.connected_components_with_branch_ids())
# [({1, 2}, {100}), ({3}, set())]

# Exclude nodes by ID — breaks connectivity, but incident edge branch IDs
# are still collected in the non-excluded endpoint's CC
view = g.without_nodes([2])
list(view.connected_components_with_branch_ids())
# [({1}, {100}), ({3}, {200})]  — node 2 breaks the chain

# Combine both — exclude branches and nodes by their domain IDs
view = g.without_branches([200]).without_nodes([1])
list(view.connected_components_with_branch_ids())
# [({2}, {100}), ({3}, set())]
```

### Weighted algorithms

```python
from networkc import (
    shortest_path,
    shortest_path_lengths,
    multi_source_shortest_path_lengths,
    eccentricity,
)

node_ids = [0, 1, 2, 3]
edges = [(0, 1), (1, 2), (2, 3)]
weights = [1.0, 2.0, 3.0]

# Shortest path (Dijkstra with C binary heap)
shortest_path(node_ids, edges, weights, source=0, target=3)  # [0, 1, 2, 3]

# Single-source shortest path lengths (with optional cutoff)
shortest_path_lengths(node_ids, edges, weights, source=0)
# {0: 0.0, 1: 1.0, 2: 3.0, 3: 6.0}

# Multi-source shortest path lengths
multi_source_shortest_path_lengths(node_ids, edges, weights, sources=[0, 3])

# Eccentricity (max shortest-path distance from source)
eccentricity(node_ids, edges, weights, source=0)  # 6.0
```

### Graph class (parse once, run many algorithms)

When running multiple algorithms on the same graph, use the `Graph` class to avoid re-parsing the input each time:

```python
from networkc import Graph

node_ids = [0, 1, 2, 3, 4, 5]
edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3)]

g = Graph(node_ids, edges)

# All calls reuse the same parsed C structures (IntMap + EdgeList + CSR adjacency list)
g.bridges()                    # [(2, 3)]
g.articulation_points()        # {2, 3}
list(g.connected_components()) # [{0, 1, 2, 3, 4, 5}]
g.bfs(0)                       # [0, 1, 2, ...]

# Weighted algorithms (weights still passed per-call)
weights = [1.0, 2.0, 1.0, 5.0, 1.0, 2.0, 1.0]
g.shortest_path(weights, source=0, target=5)
g.shortest_path_lengths(weights, source=0)

# Composite algorithms
list(g.two_edge_connected_components())
g.nodes_on_simple_paths(source=0, targets=[5])
```

Split-list constructor is also supported: `Graph(node_ids, src, dst)`.

On a 100K-node graph, running 3 algorithms via `Graph` is ~2x faster than 3 separate free-function calls, since input parsing and adjacency-list construction happen only once.

### Edge-masked views (exclude edges without rebuilding)

Create lightweight views that exclude edges from the graph without rebuilding the CSR. The base graph is never mutated — views overlay a byte mask on the shared adjacency structure.

```python
from networkc import Graph, GraphView, for_each_edge_excluded

g = Graph(node_ids, edges)

# Exclude edges by index (position in the original edge list)
view = g.without_edges([3])          # exclude edge at index 3
list(view.connected_components())    # runs on the masked graph
view.bridges()
view.bfs(0)
view.shortest_path(weights, source=0, target=5)

# Look up edge indices by node pair
idx = g.edge_indices(2, 3)           # -> [3]  (list, for multigraph support)
view = g.without_edges(idx)

# Run an algorithm for each edge excluded, one at a time
for edge_idx, components in for_each_edge_excluded(g, "connected_components"):
    print(f"Without edge {edge_idx}: {len(components)} components")
```

**Mask overhead** is 2–8% vs an unmasked `Graph` call — negligible in absolute terms. The check compiles to a single byte load + branch per edge, trivially predicted. When no mask is used (`Graph` methods), the `NULL` pointer check is predicted away at zero cost.

Sparse random graph, 100K nodes (~3 edges per node), best of 20 runs:

| Algorithm | No mask | With mask | Overhead |
|-----------|--------:|----------:|---------:|
| Connected Components | 1.4ms | 1.5ms | +3% |
| Bridges | 1.5ms | 1.6ms | +7% |
| Articulation Points | 1.6ms | 1.7ms | +8% |
| Biconnected Components | 9.9ms | 10.6ms | +7% |
| BFS | 2.3ms | 2.5ms | +8% |
| Dijkstra (single pair) | 6.9ms | 7.3ms | +7% |
| SSSP lengths | 13.6ms | 13.8ms | +2% |

The key win is avoiding O(V + E) graph rebuild per edge modification.

Parallel edges are supported — each edge is tracked by ID, so two edges between the same pair of nodes are handled correctly (e.g. for bridges, Dijkstra weight selection).

### MultiGraph support

networkc natively supports parallel edges (multigraphs). Each duplicate edge gets a unique index — no deduplication. All algorithms handle them correctly:

```python
from networkc import Graph

g = Graph([1, 2, 3], [(1, 2), (1, 2), (2, 3)])

g.is_multigraph                  # True
g.edge_count                     # 3
g.edge_indices(1, 2)             # [0, 1] — both parallel edges

# Bridges: (1,2) is NOT a bridge because a parallel edge exists
g.bridges()                      # [(2, 3)]

# Masking one parallel edge keeps the other active
view = g.without_edges([0])
list(view.connected_components())  # [{1, 2, 3}] — still connected via edge 1
```

### Node-masked views (exclude nodes without rebuilding)

Exclude nodes without rebuilding the CSR. Traversal stops at excluded nodes — they break connectivity. For `connected_components_with_branch_ids`, incident edge branch IDs are still collected in the non-excluded endpoint's CC. Chainable with edge masks.

```python
g = Graph([0, 1, 2, 3, 4], [(0, 1), (1, 2), (2, 3), (3, 4)])

# Exclude node 2 — breaks connectivity at node 2
view = g.without_nodes([2])
list(view.connected_components())  # [{0, 1}, {3, 4}]

# With branch IDs: incident edges tracked in non-excluded endpoint's CC
g2 = Graph([1, 2, 3], [(1, 2), (2, 3)], branch_ids=[100, 200])
view2 = g2.without_nodes([2])
list(view2.connected_components_with_branch_ids())
# [({1}, {100}), ({3}, {200})]  — connectivity broken, branch IDs preserved

# Chain with edge masks
view = g.without_edges([0]).without_nodes([3])
view.bfs(1)                        # [1, 2]

# BFS/Dijkstra raise ValueError if source is excluded
view = g.without_nodes([0])
view.bfs(0)                        # ValueError: source node is excluded
```

### Node splitting (reroute edges to a new node)

Split a node into two by choosing which edges stay on the original and which move to a new node. Composes `without_edges` + `with_edges` internally — no new C code needed.

```python
g = Graph([0, 1, 2, 3], [(0, 1), (1, 2), (1, 3)])
# edges: 0:(0,1), 1:(1,2), 2:(1,3)

# Split node 1: reroute edge 2 (1,3) to new node 99
view = g.split_node(node_id=1, new_node_id=99, edge_indices_to_new_node=[2])
# Result: edges (0,1), (1,2), (99,3) — node 1 keeps edges 0 and 1
list(view.connected_components())  # [{0, 1, 2, 99, 3}] — still connected

# Split the middle of a chain to disconnect
g2 = Graph([0, 1, 2], [(0, 1), (1, 2)])
view2 = g2.split_node(node_id=1, new_node_id=99, edge_indices_to_new_node=[1])
sorted(view2.connected_components(), key=min)  # [{0, 1}, {2, 99}]

# Works on views too (chainable)
view3 = g.without_edges([0]).split_node(node_id=1, new_node_id=99, edge_indices_to_new_node=[2])
```

### DAG structure learning (Bayesian networks)

Learn directed acyclic graph (DAG) structures from discrete data using greedy hill-climb search with K2 Bayesian scoring. Implemented in C — drop-in replacement for pgmpy's `HillClimbSearch` with identical results and orders of magnitude faster.

The algorithm:
1. Start with an empty DAG (no edges)
2. Each iteration, evaluate all legal single-edge operations (add, remove, flip) and pick the one with the highest K2 score improvement
3. A tabu list prevents cycling by forbidding recently reversed operations
4. Stop when no operation improves the score by more than `epsilon`

```python
from networkc import hill_climb_k2, estimate_cpds, k2_local_score

# Dataset: rows of discrete observations, values in [0, cardinality)
data = [
    [0, 0, 1],
    [1, 1, 0],
    [0, 1, 0],
    [1, 0, 1],
    [0, 0, 0],
]
cardinalities = [2, 2, 2]  # all binary

# Learn DAG structure
edges = hill_climb_k2(data, cardinalities, max_indegree=2)
# e.g. [(0, 2), (1, 2)] — variable 2 depends on variables 0 and 1

# Estimate conditional probability distributions (Laplace smoothing)
cpds = estimate_cpds(data, cardinalities, edges)
# {0: [[0.43, 0.57]], 2: [[0.75, 0.25], [0.25, 0.75], ...]}
# cpds[var] = list of distributions, one per parent configuration

# Compute K2 local score for a single variable given its parents
score = k2_local_score(data, cardinalities, child=2, parents=[0, 1])
```

Parameters for `hill_climb_k2`:
- `max_indegree` — maximum parents per node (default 1)
- `tabu_length` — circular buffer size for forbidden operations (default 100)
- `epsilon` — minimum score improvement to continue (default 1e-4)
- `max_iter` — iteration cap (default 1,000,000)

Complexity per iteration: O(n^2 * n_samples) where n = number of variables.

### Directed graphs

All graph algorithms support directed graphs via `directed=True`. Edges `(u, v)` are treated as `u -> v`. A forward and reverse CSR are built, using the same total memory as undirected (2m entries).

```python
from networkc import Graph, strongly_connected_components, weakly_connected_components

node_ids = [1, 2, 3, 4, 5]
edges = [(1, 2), (2, 3), (3, 1), (4, 5)]  # 1->2->3->1 cycle, 4->5

g = Graph(node_ids, edges, directed=True)

# Strongly connected components (mutually reachable nodes)
list(g.strongly_connected_components())
# [{1, 2, 3}, {4}, {5}]

# Weakly connected components (ignoring direction)
list(g.weakly_connected_components())
# [{1, 2, 3}, {4, 5}]

# Topological sort (DAGs only — raises ValueError on cycles)
dag = Graph([1, 2, 3, 4], [(1, 2), (1, 3), (3, 4)], directed=True)
dag.topological_sort()  # [1, 3, 4, 2] (one valid ordering)

# BFS follows outgoing edges only
g.bfs(source=1)  # [1, 2, 3] — cannot reach 4 or 5

# Dijkstra respects direction
dag = Graph([1, 2, 3], [(1, 2), (2, 3)], directed=True)
dag.shortest_path(weights=[1.0, 2.0], source=1, target=3)  # [1, 2, 3]
dag.shortest_path(weights=[1.0, 2.0], source=3, target=1)  # [] — no path

# Free-function shorthand
list(strongly_connected_components(node_ids, edges))
list(weakly_connected_components(node_ids, edges))
```

**Query methods** on directed graphs:

```python
g = Graph([1, 2, 3], [(1, 2), (2, 3), (3, 1)], directed=True)

g.neighbors(1)       # {2} — successors only
g.successors(1)      # {2}
g.predecessors(1)    # {3}
g.degree(1)          # 1 (out-degree)
g.out_degree(1)      # 1
g.in_degree(1)       # 1
g.edge_indices(1, 2) # [0] — direction matters: edge_indices(2, 1) == []
```

**GraphView masking** works identically on directed graphs:

```python
g = Graph([1, 2, 3], [(1, 2), (2, 3), (3, 1)], directed=True)
view = g.without_edges([2])  # remove 3->1
list(view.strongly_connected_components())  # [{1}, {2}, {3}]
```

**Method availability:**

| Method | Undirected | Directed |
|--------|:---------:|:--------:|
| `connected_components` | yes | TypeError |
| `strongly_connected_components` | TypeError | yes |
| `weakly_connected_components` | TypeError | yes |
| `topological_sort` | TypeError | yes |
| `bridges` / `articulation_points` / `biconnected_components` | yes | TypeError |
| `bfs` / `shortest_path` / `dijkstra` | yes | yes |
| `all_edge_paths` | yes | yes |
| `successors` / `predecessors` / `in_degree` / `out_degree` | TypeError | yes |

### Cycle basis (fundamental cycles)

Detect all fundamental cycles in an undirected graph. The number of cycles equals the circuit rank: `m - n + c` where `c` is the number of connected components.

```python
from cgraph import Graph, cycle_basis

# Triangle
g = Graph([1, 2, 3], [(1, 2), (2, 3), (3, 1)])
g.cycle_basis()  # [[3, 2, 1]]

# Figure-8 (two cycles sharing node 3)
g = Graph([1, 2, 3, 4, 5], [(1, 2), (2, 3), (3, 1), (3, 4), (4, 5), (5, 3)])
g.cycle_basis()  # [[3, 2, 1], [5, 4, 3]]

# Tree (no cycles)
g = Graph([1, 2, 3], [(1, 2), (2, 3)])
g.cycle_basis()  # []

# Free function
cycle_basis([1, 2, 3], [(1, 2), (2, 3), (3, 1)])  # [[3, 2, 1]]
```

Useful for validating radial grid topology (presence of cycles indicates mesh). Self-loops are detected as single-node cycles. Works with GraphView masks — removing a cycle-closing edge eliminates that cycle.

### DAG longest path

Find the longest path in a directed acyclic graph. Supports optional edge weights.

```python
from cgraph import Graph, dag_longest_path

# Unweighted: longest by hop count
g = Graph([1, 2, 3, 4], [(1, 2), (1, 3), (3, 4)], directed=True)
g.dag_longest_path()  # [1, 3, 4]

# Weighted: longest by total weight
g = Graph([1, 2, 3], [(1, 2), (1, 3)], directed=True)
g.dag_longest_path(weights=[1.0, 100.0])  # [1, 3]

# Free function
dag_longest_path([1, 2, 3, 4], [(1, 2), (2, 3), (3, 4)])  # [1, 2, 3, 4]
```

Uses topological sort + dynamic programming. Raises `ValueError` on cyclic graphs. 32-80x faster than networkx.

### Edge-path enumeration (edge-disjoint paths)

Find all paths from source to targets where each edge is used at most once. Returns paths as lists of edge indices. By default, nodes may be revisited (critical for multigraphs). Use `node_simple=True` to restrict to node-simple paths where each node is visited at most once.

```python
g = Graph([0, 1, 2, 3], [(0, 1), (1, 2), (0, 2), (2, 3)])

# All edge-disjoint paths from 0 to 3
paths = g.all_edge_paths(source=0, targets=3)
# [[0, 1, 3], [2, 3]] — two paths using different edges

# With cutoff (max edges per path)
paths = g.all_edge_paths(source=0, targets=3, cutoff=2)
# [[2, 3]] — only paths with ≤2 edges

# Node-simple paths (no node revisits, like networkx all_simple_edge_paths)
g2 = Graph([1, 2, 3, 4], [(1, 2), (2, 3), (3, 1), (1, 4)])
g2.all_edge_paths(1, 4)                     # [[3], [0, 1, 2, 3]] — includes revisit of node 1
g2.all_edge_paths(1, 4, node_simple=True)    # [[3]] — only the direct edge

# Works with masks — respects excluded edges and nodes
view = g.without_edges([2])
paths = view.all_edge_paths(source=0, targets=3)
# [[0, 1, 3]] — only the path through edges 0→1→3
```

## Performance details

### Cost breakdown

Every networkc call has three cost phases. Connected components at 1M nodes, sparse random graph (~3 edges per node):

```python
class Branch:
    def __init__(self, branch_id: int, node_a: int, node_b: int):
        self.branch_id = branch_id
        self.node_a = node_a
        self.node_b = node_b
```

| Phase | Tuples | Split lists | numpy (m,2) |
|-------|-------:|------------:|------------:|
| 1. Gather (Python loop over objects) | 71ms | **35ms** | 91ms |
| 2. Parse (hash map + edge translation) | 23ms | 22ms | **5ms** |
| 3. C algorithm (union-find + results) | 62ms | 62ms | 62ms |
| **Total** | **156ms** | **119ms** | **159ms** |
| vs tuples | baseline | **1.31x** | ~same |

- **Gather** is pure Python — extracting `node_a`/`node_b` from your objects. networkc can't optimize this, but the interface choice affects it (tuples cost 71ms, split lists cost 35ms).
- **Parse** is the C-side input handling — building the node-ID hash map and translating edges to internal indices. Numpy skips per-element Python unpacking via buffer reads.
- **C algorithm** is the actual computation (union-find + building Python `set` results). Fixed cost, identical across all interfaces. The `set` construction via `PySet_Add` accounts for ~50ms of the 62ms — this is the CPython floor for creating hash-based sets of 1M elements.

### Performance across graph topologies

End-to-end from `Branch` objects using split lists. Connected components at 1M nodes:

| Scenario | Components | Gather | networkc | Total |
|----------|-----------:|-------:|-------:|------:|
| 1 component (all connected) | 1 | 25ms | 30ms | 55ms |
| 10 components (100K each) | 10 | 22ms | 27ms | 48ms |
| 1K components (1K each) | 1,000 | 21ms | 23ms | 44ms |
| 1 dominant + 100K isolated | 100,001 | 19ms | 54ms | 73ms |
| Random sparse (avg degree 3) | 54,266 | 35ms | 74ms | 109ms |
| 1M isolated (0 edges) | 1,000,000 | 0ms | 212ms | 212ms |

The networkc call splits into union-find algorithm and Python set construction:

| Scenario | Components | Union-find | Set construction | Set % of networkc |
|----------|-----------:|-----------:|-----------------:|----------------:|
| 1 component (all connected) | 1 | 4ms | 24ms | 86% |
| 10 components (100K each) | 10 | 4ms | 26ms | 87% |
| 1K components (1K each) | 1,000 | 4ms | 20ms | 84% |
| 1 dominant + 100K isolated | 100,001 | 4ms | 41ms | 92% |
| Random sparse (avg degree 3) | 54,266 | 11ms | 50ms | 82% |
| 1M isolated (0 edges) | 1,000,000 | 2ms | 160ms | 99% |

The union-find algorithm is 2-11ms — already near-optimal. **82-99% of the networkc time is Python set construction** (`PySet_New` + `PySet_Add`), which is the CPython floor for building hash-based sets. Many small components are expensive because each `PySet_New()` allocates a Python set object. Gather cost scales with edge count, not component count.

### Calling conventions

Two ways to pass edges — both accept Python lists or numpy arrays:

**Tuples** — simplest:
```python
edges = [(b.node_a, b.node_b) for b in branches]
connected_components(node_ids, edges)
```

**Split lists** — **1.3x faster** end-to-end:
```python
src = [b.node_a for b in branches]
dst = [b.node_b for b in branches]
connected_components(node_ids, src, dst)
```

Split lists is faster because building two flat lists avoids creating 1.5M tuple objects. The C parsing cost is similar — `PyLong_AsLong` per element dominates regardless of container shape.

### Run benchmarks

```bash
pip install -e ".[benchmark]"
pip install networkx pgmpy
pytest tests/performance_tests/ -v -s -k speedup
python benchmarks/bench_all.py       # structured cost breakdown + topology scenarios
python benchmarks/bench_dag_learn.py  # hill-climb K2: networkc vs pgmpy
```

## Tests

```bash
pip install -e ".[dev]"
pytest tests/unit_tests/ -v
```
