# Graph Diff Algorithm in code-review-graph: How It Compares Code Snapshots

> Explore the graph diff algorithm in code-review-graph. Learn how it compares code snapshots using deterministic set subtraction for O(N) complexity, identifying changes efficiently.

- Repository: [Tirth Kanani/code-review-graph](https://github.com/tirth8205/code-review-graph)
- Tags: deep-dive
- Published: 2026-07-22

---

**The graph diff algorithm uses deterministic set subtraction on JSON-compatible snapshots to identify added and removed nodes, edges, and community reassignments with O(N) linear complexity.**

The `tirth8205/code-review-graph` repository provides tools for analyzing code structure as knowledge graphs. Its built-in graph diff algorithm enables developers to track how code graphs evolve between analysis runs by comparing portable snapshots stored as plain Python dictionaries.

## How the Graph Diff Algorithm Works

The algorithm operates on snapshots produced by `take_snapshot()` in [`code_review_graph/graph_diff.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/graph_diff.py). These snapshots capture the complete state of the knowledge graph at a point in time, including node counts, edge collections, and community assignments.

### Snapshot Structure

Each snapshot is a JSON-compatible dictionary containing:

- **Node mappings**: A dictionary keyed by **qualified name** (e.g., function or class paths), storing the node's kind, source file, and `community_id`
- **Edge collections**: A set of strings formatted as `source→target:kind` representing relationships between code elements
- **Metadata**: Total counts of nodes and edges for quick reference

The `take_snapshot()` function constructs these representations by querying the underlying `GraphStore` (typically SQLite-backed), then returns the structure without preserving database connections.

### The Four-Step Diff Process

When `diff_snapshots()` compares two snapshots, it executes a deterministic sequence of set operations:

1. **Extract node and edge sets**

   ```python
   before_nodes = set(before.get("nodes", {}).keys())
   after_nodes  = set(after.get("nodes",  {}).keys())
   before_edges = before.get("edges", set())
   after_edges  = after.get("edges",  set())
   ```

2. **Compute additions and deletions** using set subtraction:
   - `new_nodes` = `after_nodes - before_nodes`
   - `removed_nodes` = `before_nodes - after_nodes`
   - `new_edges` = `after_edges - before_edges`
   - `removed_edges` = `before_edges - after_edges`

3. **Detect community moves** by iterating over the intersection of node sets:

   ```python
   for qn in before_nodes & after_nodes:
       if before["nodes"][qn]["community_id"] != after["nodes"][qn]["community_id"]:
           community_changes.append({...})
   ```

4. **Build the result dictionary** containing detailed lists and a summary section with raw counts (`nodes_added`, `edges_removed`, etc.)

All operations execute in **O(N)** time relative to the snapshot size, making the approach suitable for large codebases.

## Implementation Details and Limitations

The `diff_snapshots()` implementation in [`code_review_graph/graph_diff.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/graph_diff.py) deliberately constrains output size to keep payloads manageable for downstream tools like CLI renderers or PR comment generators.

### Result Set Limits

- **100 items maximum** for added and removed node lists
- **100 items maximum** for added and removed edge lists  
- **50 entries maximum** for community change records

These limits ensure that diff reports remain readable while preserving the most significant changes. The `summary` section always contains exact numeric counts regardless of list truncation.

### Storage Engine Independence

Because snapshots are pure dictionaries without database references, the graph diff algorithm operates **independently of the underlying storage engine**. You can diff snapshots taken from different `GraphStore` instances or reload historical snapshots using `load_snapshot()` without maintaining the original database connection.

## Practical Usage Examples

### Diff Two In-Memory Snapshots

Compare graph states before and after a code analysis run:

```python
from code_review_graph.graph import GraphStore
from code_review_graph.graph_diff import take_snapshot, diff_snapshots

store = GraphStore("tmp/graph.db")
snap1 = take_snapshot(store)          # baseline snapshot

# ... run analysis that mutates the store ...

snap2 = take_snapshot(store)          # post-analysis snapshot

diff = diff_snapshots(snap1, snap2)
print("Added nodes:", diff["summary"]["nodes_added"])
print("Removed edges:", diff["summary"]["edges_removed"])

```

### Persist and Compare Snapshots Later

Save snapshots to disk for longitudinal analysis or cross-process comparison:

```python
from pathlib import Path
from code_review_graph.graph_diff import save_snapshot, load_snapshot, diff_snapshots

# Save snapshots

save_snapshot(snap1, Path("snap_a.json"))
save_snapshot(snap2, Path("snap_b.json"))

# Load and compare later

snap_a = load_snapshot(Path("snap_a.json"))
snap_b = load_snapshot(Path("snap_b.json"))

diff = diff_snapshots(snap_a, snap_b)
for change in diff["community_changes"]:
    print(f"{change['node']} moved: {change['before_community']} → {change['after_community']}")

```

## Summary

- The **graph diff algorithm** in [`code_review_graph/graph_diff.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/graph_diff.py) uses **set subtraction** to determine changes between snapshots, achieving O(N) linear complexity.
- Snapshots capture **qualified names**, **edges** as formatted strings, and **community IDs** in JSON-compatible dictionaries.
- The algorithm detects **added nodes**, **removed edges**, and **community reassignments** by comparing set intersections and differences.
- Results are **capped at 100 nodes/edges and 50 community changes** to maintain manageable payload sizes for CLI and web interfaces.
- The approach is **storage-engine agnostic**, working with any snapshots regardless of whether they came from SQLite-backed `GraphStore` instances or JSON files.

## Frequently Asked Questions

### What is the time complexity of the graph diff algorithm?

The algorithm runs in **O(N)** time where N is the size of the snapshots. Because it relies on Python's hash-based set operations for computing unions and differences rather than graph traversals, performance scales linearly with the number of nodes and edges.

### Can the diff algorithm work without the SQLite GraphStore?

**Yes.** The `diff_snapshots()` function operates exclusively on in-memory dictionaries. Once `take_snapshot()` extracts data from a `GraphStore`, the resulting snapshot contains no database references. You can save snapshots to JSON with `save_snapshot()`, transfer them between systems, and diff them later without access to the original SQLite database.

### How does the algorithm detect community changes between snapshots?

For every **qualified name** present in both snapshots (the set intersection), the algorithm compares the stored `community_id` values. If they differ, it records a community change entry containing the node identifier, previous community, and new community. This enables tracking of code ownership shifts or module reorganizations between analysis runs.

### Why are the results limited to 100 nodes/edges and 50 community changes?

These limits prevent excessively large diff outputs from overwhelming CLI displays or PR comment systems. The `diff_snapshots()` function in [`code_review_graph/graph_diff.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/graph_diff.py) truncates detail lists while preserving exact counts in the `summary` section, ensuring users see the magnitude of changes without processing thousands of individual entries.