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

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

   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:

   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 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:

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:

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 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 truncates detail lists while preserving exact counts in the summary section, ensuring users see the magnitude of changes without processing thousands of individual entries.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}