================================================================================
TCK COMPARISON ANALYSIS SUMMARY
================================================================================
Date: 2026-02-14
Task: Compare PropertyGraph vs NetworKitRust TCK failures
================================================================================

TEST RESULTS COMPARISON
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Backend          | Passing  | Failing | Pass Rate | Total Scenarios
─────────────────|----------|---------|-----------|────────────────
PropertyGraph    | 3,728    | 32      | 95.7%     | 3,897
NetworKitRust    | 3,417    | 344     | 87.7%     | 3,897
─────────────────|----------|---------|-----------|────────────────
Shared failures  |          | 23      |           |
NK-specific      |          | 299     |           |

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

KEY FINDINGS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

1. NetworKitRust has 299 backend-specific failures (93% of total failures)
2. Only 23 failures are shared between backends (7%)
3. Primary issue: Bidirectional edge representation in NetworKitRust
4. Most affected area: MATCH operations (107 scenarios, 35.8%)
5. Second most affected: WHERE filtering (35 scenarios, 11.7%)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

FAILURE CATEGORIES (NetworKitRust-specific)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Category                  | Count | % of Failures
─────────────────────────|-------|──────────────
MATCH operations         | 107   | 35.8%
WHERE filtering          | 35    | 11.7%
Pattern operations       | 30    | 10.0%
Triadic selection        | 18    | 6.0%
WITH clause              | 18    | 6.0%
RETURN operations        | 15    | 5.0%
MERGE                    | 15    | 5.0%
DELETE                   | 12    | 4.0%
Graph functions          | 10    | 3.3%
Collections/Paths        | 10    | 3.3%
Subqueries/Quantifiers   | 10    | 3.3%
CREATE                   | 9     | 3.0%
Other                    | 20    | 6.7%

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

TOP 10 FIX PRIORITIES
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

 #  Area                          Scenarios  Impact  Effort
 ──────────────────────────────────────────────────────────────────────
 1  Relationship Matching         107        35%     Medium (2-3 days)
 2  WHERE Filtering               35         12%     Medium (2-3 days)
 3  Pattern Predicates            30         10%     High (4-5 days)
 4  Triadic Selection             18         6%      Low (1-2 days)
 5  Variable-Length Paths         23         8%      Medium (3-4 days)
 6  WITH Variable Forwarding      18         6%      Low (1-2 days)
 7  MERGE Relationships           15         5%      Medium (2-3 days)
 8  RETURN Projection             15         5%      Low (1-2 days)
 9  DELETE Relationships          12         4%      Low (1 day)
10  Relationship Accessors        10         3%      Low (1 day)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

IMPLEMENTATION ROADMAP
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Phase 1: Core Relationship Fixes (Weeks 1-2)
  - Relationship matching deduplication
  - WHERE filtering on relationships
  - Relationship accessor functions
  Impact: 152 scenarios (51% of failures)

Phase 2: Advanced Patterns (Week 3)
  - Pattern predicates and comprehensions
  - Variable-length path expansion
  - Triadic selection adaptation
  Impact: 71 scenarios (24% of failures)

Phase 3: Write Operations (Week 4)
  - MERGE bidirectional handling
  - DELETE both-edge removal
  - SET/REMOVE on relationships
  Impact: 41 scenarios (14% of failures)

Phase 4: Query Pipeline (Week 5)
  - WITH variable forwarding
  - RETURN relationship projection
  - Other pipeline operations
  Impact: 50 scenarios (17% of failures)

Total Estimated Effort: 4-5 weeks to resolve all 299 failures

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

ROOT CAUSE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

NetworKitRust stores each Cypher relationship as TWO DIRECTED EDGES (one in
each direction) for performance. This creates systematic issues:

1. Deduplication: Undirected matches (a)--(b) find both edges
2. Metadata: Properties/type may only be stored on one edge
3. Self-loops: When a == b, two edges create matching ambiguity
4. Path building: Paths may include both directions
5. Delete operations: Must delete both edge directions

Solution: Implement 'canonical edge' concept and deduplication logic in all
pattern matching operations.

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

DELIVERABLES
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Generated Documents:

1. NETWORKIT_VS_PROPERTYGRAPH_COMPARISON.md (723 lines)
   - Comprehensive comparison of all failures
   - Categorized list of 299 NK-specific failures
   - List of 23 shared failures
   - Fix strategy recommendations

2. NETWORKIT_FAILURE_PATTERNS.md (219 lines)
   - Pattern frequency analysis
   - Root cause hypotheses
   - Investigation recommendations
   - Top 15 affected features

3. NETWORKIT_FIX_PRIORITIES.md (247 lines)
   - Action-oriented quick reference
   - Top 10 priorities with specifications
   - 4-phase implementation plan
   - Quick diagnostic tests

4. ANALYSIS_INDEX.md (131 lines)
   - Document index and navigation guide
   - Quick start instructions
   - Summary of key findings

Supporting Files:
- failure_comparison.txt - Raw comparison data
- networkit_only_failures.txt - Categorized failures

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

NEXT STEPS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

1. Review NETWORKIT_VS_PROPERTYGRAPH_COMPARISON.md for full context
2. Run diagnostic tests from NETWORKIT_FIX_PRIORITIES.md
3. Add debug logging to confirm root cause hypotheses
4. Start with Priority 1: Relationship Matching (107 scenarios)
5. Validate fix against affected TCK scenarios
6. Continue with remaining priorities

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
