User Story: Automated Graph Integrity & Traceability Validation

Estado de fase (MASTER-00): POC — documentación involucrada en la validación cuantitativa de contexto. Gobernanza: MASTER-00.

User Story: Automated Graph Integrity & Traceability Validation

---

User Story Statement

As a software architect, tech lead, or CI/CD automation pipeline,
I want DocuGraph (and its MCP tool validate_traceability) to automatically audit the documentation graph for circular dependencies, broken atomic references, orphan nodes, and unreferenced API operations,
So that 100% of technical specifications remain structurally sound, fully traceable, and free of circular logic.

---

Business Rationale & User Impact

In growing software projects, manual documentation review fails to catch broken links, missing frontmatters, or accidental circular dependencies. As outlined in VISION-00 and AGENTS.md, circular dependencies disrupt topological sorting, while broken references lead AI coding agents to make false assumptions. Automated traceability validation provides instant feedback to developers and CI/CD pipelines, guaranteeing that the project DAG remains clean and fully connected.

---

User Flow & Interaction Overview

1. Developer triggers validation via UI button on Graph Canvas (FE-03), OR an automated CI/CD pipeline / AI agent invokes MCP tool validate_traceability().
2. Core validation engine in :docugraph-core reads all project Markdown files and parses their YAML frontmatter headers.
3. Validation engine executes Tarjan’s Strongly Connected Components Algorithm to detect any circular dependency loops.
4. Engine scans document body links and YAML links: metadata to detect broken file paths or unresolvable atomic IDs (US-XX, BE-XX, FE-XX).
5. Engine checks openapi.yaml to ensure every declared operationId is referenced by at least one backend task (BE-XX).
6. Engine compiles an Audit Report detailing errors (critical), warnings (medium), and info items, specifying exact file paths and line numbers.

---

Acceptance Criteria (Gherkin Format)

Scenario 1: Circular Dependency Cycle Detection via Tarjan’s Algorithm

Given a documentation repository containing a circular dependency loop (US-01 -> US-02 -> US-01)
When the user clicks "Run Audit" in the app or an AI agent invokes MCP tool "validate_traceability"
Then the core validation engine executes Tarjan's algorithm on the graph model
And reports a CRITICAL validation error identifying the exact cycle path: ["US-01", "US-02", "US-01"]
And flags the specific files and line numbers where the circular references occur

Scenario 2: Broken Link & Unresolved Atomic ID Identification

Given a document "BE-01_auth-login.md" referencing a non-existent atomic ID "US-99" or missing file path "docs/user_stories/US-99.md"
When the traceability validation audit runs
Then the audit report flags an ERROR "UNRESOLVED_ATOMIC_REFERENCE"
And pinpoints the target file "BE-01_auth-login.md", line number, and character position of the broken reference

Scenario 3: Orphan Node & Unreferenced API Operation Audit

Given a backend specification file "BE-06_paywall-check-entitlement.md" that lacks an upstream "depends_on" user story reference
And given an operationId "deleteUser" in openapi.yaml that is not referenced by any backend task spec
When the validation audit runs
Then the audit report includes a WARNING "ORPHAN_SPECIFICATION" for BE-06
And includes a WARNING "UNREFERENCED_OPENAPI_OPERATION" for operationId "deleteUser"

Scenario 4: Structured Audit Report Generation

Given a complete project audit execution
When the validation process finishes
Then the system generates a structured JSON and Markdown audit summary report
And calculates total node count, edge count, overall health score (0-100%), and pass/fail status
And outputs actionable remediation recommendations for each detected violation

---

Functional Requirements & Constraints

1. Performance Requirement: The audit engine in :docugraph-core must complete full graph validation (cycle detection, link verification, frontmatter checking) for 1,000 document nodes in under 2 seconds.
2. Algorithm Requirement: Cycle detection must use Tarjan’s algorithm with O(V + E) time complexity.
3. MCP Tool Signature:

   fun validateTraceability(workspacePath: String): ValidationReport

---

Downstream Atomic Mapping

This User Story serves as the direct upstream source of truth for the following downstream specifications:

• Backend Specification: BE-05_mcp-validate-traceability.md (BE-05) — Ktor route handler for POST /api/v1/mcp/validate-traceability.
• API Contract: openapi.yaml — Single source of truth for REST endpoint with operationId: validateTraceability.
• MCP Specification: docs/mcp/MCP_SPEC.md (tool: validate_traceability) — MCP tool definition for automated audits.
• Core Library Module: :docugraph-core — Parser, Tarjan algorithm, and link verifier implementation.

---

Traceability Index

• Upstream Dependencies:
  • docs/00_BUSINESS_VISION.md (VISION-00) — Quality & Traceability Vision.
  • AGENTS.md (AGENTS) — AI Agent Integrity Rules.
  • US-02_create_project.md (US-02) — Workspace Configuration & Schema Setup.
  • US-03_view_graph.md (US-03) — Graph Engine & Canvas.
• Downstream Direct Linkages (Planned M2/M3):
  • BE-05_mcp-validate-traceability.md (BE-05)
  • tool: validate_traceability in docs/mcp/MCP_SPEC.md
• Related Stories:
  • US-04_get_task_context.md (US-04) — Context extraction requiring valid graph structure.