Backend Spec: Automated Graph Integrity & Traceability Validation (mcp.validate_traceability)

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

Backend Spec: Automated Graph Integrity & Traceability Validation (mcp.validate_traceability)

1. Overview & Objectives

This specification details the backend service (validateTraceability) for automated graph integrity audits. It processes POST /api/v1/mcp/validate-traceability, executes Tarjan’s Strongly Connected Components (SCC) algorithm to detect circular dependency loops in $O(V+E)$ time, verifies relative link targets and operationId mappings, calculates a normalized Health Score, and returns a JSON audit report.

2. API Endpoint Signature & Traceability

• HTTP Method & Path: POST /api/v1/mcp/validate-traceability
• operationId: validateTraceability
• Upstream Requirements: US-05, IX-03, SCHEMA-01
• Primary Service Class: TraceabilityValidatorService.kt
• Ktor Route Handler: McpRoutes.kt

3. Data Models & Kotlin Data Classes

package io.docugraph.backend.models.mcp

import kotlinx.serialization.Serializable

@Serializable
data class ValidateTraceabilityRequest(
    val projectId: String? = null,
    val workspacePath: String? = null
)

@Serializable
data class BrokenLinkItemDto(
    val sourceNode: String,
    val targetRef: String,
    val errorMessage: String
)

@Serializable
data class CircularDependencyItemDto(
    val cyclePath: List<String>
)

@Serializable
data class AuditReportResponse(
    val healthScore: Float,
    val totalNodes: Int,
    val totalEdges: Int,
    val brokenLinksCount: Int,
    val circularDependenciesCount: Int,
    val brokenLinks: List<BrokenLinkItemDto>,
    val circularDependencies: List<CircularDependencyItemDto>,
    val missingOperationIds: List<String>
)

4. Tarjan’s SCC & Validation Algorithm

                 Graph Nodes & Edges
                          |
                          v
         +----------------------------------+
         | Tarjan's SCC Cycle Search O(V+E) |
         +----------------+-----------------+
                          |
                          v
         +----------------------------------+
         | Audit Relative File Links & IDs  |
         +----------------+-----------------+
                          |
                          v
         +----------------------------------+
         |  Calculate Health Score Formula  |
         +----------------+-----------------+
                          |
                          v
                 AuditReportResponse

4.1 Health Score Calculation Formula

$$\text{Health Score} = \max\left(0.0,; 100.0 \times \left(1.0 - \frac{\text{Broken Links} + \text{Circular Dependencies}}{\max(1, \text{Total Edges})}\right)\right)$$

4.2 Tarjan’s Algorithm Logic (Kotlin Pseudocode)

class TarjanSccDetector(private val graph: Map<String, List<String>>) {
    private var index = 0
    private val stack = ArrayDeque<String>()
    private val indices = mutableMapOf<String, Int>()
    private val lowLink = mutableMapOf<String, Int>()
    private val onStack = mutableSetOf<String>()
    val sccs = mutableListOf<List<String>>()

    fun findCycles(): List<List<String>> {
        for (node in graph.keys) {
            if (!indices.containsKey(node)) {
                strongConnect(node)
            }
        }
        return sccs.filter { it.size > 1 } // Components with > 1 node form cycles
    }

    private fun strongConnect(node: String) {
        indices[node] = index
        lowLink[node] = index
        index++
        stack.addLast(node)
        onStack.add(node)

        for (neighbor in graph[node] ?: emptyList()) {
            if (!indices.containsKey(neighbor)) {
                strongConnect(neighbor)
                lowLink[node] = minOf(lowLink[node]!!, lowLink[neighbor]!!)
            } else if (onStack.contains(neighbor)) {
                lowLink[node] = minOf(lowLink[node]!!, indices[neighbor]!!)
            }
        }

        if (lowLink[node] == indices[node]) {
            val component = mutableListOf<String>()
            do {
                val w = stack.removeLast()
                onStack.remove(w)
                component.add(w)
            } while (w != node)
            if (component.size > 1) sccs.add(component)
        }
    }
}

5. Database Interaction & SQL Queries

SELECT n.atomic_id AS source_id, e.target_node_id, t.atomic_id AS target_id
FROM node_edges e
JOIN nodes n ON n.id = e.source_node_id
LEFT JOIN nodes t ON t.id = e.target_node_id
WHERE e.project_id = :projectId;

6. Error Handling & HTTP Status Codes

Error Condition	HTTP Code	Internal Code	Response Message
Neither projectId nor workspacePath supplied	400 Bad Request	MISSING_AUDIT_TARGET	“Must provide either projectId or workspacePath.”
Target project workspace not found	404 Not Found	PROJECT_NOT_FOUND	“Project workspace not found in database.”
Engine audit failure	500 Server Error	AUDIT_EXECUTION_ERROR	“Internal error during graph audit execution.”

7. Verification & Test Plan

• Unit Test: Test TarjanSccDetector on a graph with known cycles (A -> B -> C -> A).
• Integration Test: Run audit on test project graph and verify health score calculations.