Graph Validation

Added in: 0.5.0

Graph Validation ensures your workflows are structurally sound before execution, catching errors early and providing clear feedback.

Overview

The validation system checks for:

• Empty graphs - At least one node required
• Invalid entry points - Entry point must exist
• Invalid edge references - All edges must reference existing nodes
• Cycles - Graphs must be DAGs (Directed Acyclic Graphs)
• Unreachable nodes - All nodes must be reachable from entry point

Automatic Validation

Validation happens automatically before execution:

val graph = graph("my-graph") {
    // ... define nodes and edges
}

// Validation runs before execution
val result = runner.run(graph, input)

// If validation fails, returns SpiceResult.Failure
when (result) {
    is SpiceResult.Success -> println("Success!")
    is SpiceResult.Failure -> {
        // ValidationError with details
        println("Error: ${result.error.message}")
    }
}

Manual Validation

You can validate graphs explicitly:

val validation = GraphValidator.validate(graph)

when (validation) {
    is SpiceResult.Success -> println("Graph is valid!")
    is SpiceResult.Failure -> {
        val error = validation.error as SpiceError.ValidationError
        println("Validation failed: ${error.message}")

        // Access detailed errors
        val errors = error.context["errors"] as List<String>
        errors.forEach { println("  - $it") }
    }
}

Validation Rules

Rule 1: Non-Empty Graph

Graphs must have at least one node.

// ❌ Invalid: Empty graph
val invalid = Graph(
    id = "empty",
    nodes = emptyMap(),  // No nodes!
    edges = emptyList(),
    entryPoint = "start"
)

// Error: "Graph must have at least one node"

Rule 2: Valid Entry Point

Entry point must reference an existing node.

// ❌ Invalid: Non-existent entry point
val invalid = Graph(
    id = "bad-entry",
    nodes = mapOf("node1" to someNode),
    edges = emptyList(),
    entryPoint = "nonexistent"  // Doesn't exist!
)

// Error: "Entry point 'nonexistent' does not exist in graph"

Rule 3: Valid Edge References

All edges must reference existing nodes.

// ❌ Invalid: Edge to non-existent node
val invalid = Graph(
    id = "bad-edge",
    nodes = mapOf("node1" to someNode),
    edges = listOf(
        Edge("node1", "node2")  // node2 doesn't exist!
    ),
    entryPoint = "node1"
)

// Error: "Edge references non-existent 'to' node: node2"

Rule 4: No Cycles (DAG)

Added in: 0.6.3 - Optional cycle validation

By default, graphs must be Directed Acyclic Graphs - no cycles allowed.

// ❌ Invalid by default: Cycle in graph
val invalid = Graph(
    id = "cyclic",
    nodes = mapOf(
        "node1" to someNode,
        "node2" to someNode,
        "node3" to someNode
    ),
    edges = listOf(
        Edge("node1", "node2"),
        Edge("node2", "node3"),
        Edge("node3", "node1")  // Cycle!
    ),
    entryPoint = "node1"
)

// Error: "Graph contains cycles involving nodes: node1, node2, node3"

Why DAG by default?

• Predictable execution order
• No infinite loops
• Clear data flow
• Easier to reason about

Allowing Cycles (0.6.3+)

For use cases requiring loops (e.g., iterative workflows, retry loops), you can explicitly allow cycles:

// ✅ Valid with allowCycles: Conditional loop
val workflowWithLoop = Graph(
    id = "workflow-loop",
    nodes = mapOf(
        "workflow" to workflowNode,
        "response" to responseNode
    ),
    edges = listOf(
        Edge("workflow", "workflow") { result ->
            // Loop condition: continue if not done
            (result.data as? Map<*, *>)?.get("continue") == true
        },
        Edge("workflow", "response") { result ->
            // Exit condition: stop when done
            (result.data as? Map<*, *>)?.get("continue") != true
        }
    ),
    entryPoint = "workflow",
    allowCycles = true  // ⭐ Explicitly allow cycles
)

Important: When using allowCycles = true:

• Always include exit conditions in edge predicates
• Implement loop guards in your nodes to prevent infinite loops
• Monitor execution - add middleware for timeout protection
• Consider checkpointing for long-running loops

Rule 5: No Unreachable Nodes

All nodes must be reachable from the entry point.

// ❌ Invalid: Orphan node
val invalid = Graph(
    id = "orphan",
    nodes = mapOf(
        "node1" to someNode,
        "node2" to someNode,
        "orphan" to someNode  // Not connected!
    ),
    edges = listOf(
        Edge("node1", "node2")
    ),
    entryPoint = "node1"
)

// Error: "Graph contains unreachable nodes: orphan"

GraphValidator API

validate()

Validates entire graph structure:

fun validate(graph: Graph): SpiceResult<Unit>

Returns:

• SpiceResult.Success if valid
• SpiceResult.Failure with ValidationError if invalid

isDAG()

Checks if graph is a valid DAG:

fun isDAG(graph: Graph): Boolean

if (!GraphValidator.isDAG(graph)) {
    println("Graph contains cycles!")
}

findTerminalNodes()

Find nodes with no outgoing edges:

fun findTerminalNodes(graph: Graph): List<String>

val terminals = GraphValidator.findTerminalNodes(graph)
println("Terminal nodes: $terminals")
// Useful for finding end points

Cyclic Graph Use Cases

Use Case 1: Iterative Refinement Loop

Process data until quality threshold is met:

val refinementWorkflow = graph("data-refinement") {
    agent("refine", refineAgent)
    agent("check-quality", qualityCheckAgent)
    output("final-result") { it.state["refine"] }

    edges {
        edge("refine", "check-quality")
        edge("check-quality", "refine") { result ->
            // Loop back if quality insufficient
            val quality = (result.data as? Map<*, *>)?.get("quality") as? Double ?: 0.0
            quality < 0.9 && ctx.state["iterations"] as? Int ?: 0 < 10
        }
        edge("check-quality", "final-result") { result ->
            // Exit when quality sufficient
            val quality = (result.data as? Map<*, *>)?.get("quality") as? Double ?: 0.0
            quality >= 0.9
        }
    }

    allowCycles = true
}

Use Case 2: User Interaction Loop

Collect user input until confirmation:

val userDialogWorkflow = graph("user-dialog") {
    human("ask-question", prompt = "Enter your choice:")
    agent("validate", validationAgent)
    agent("confirm", confirmAgent)
    output("confirmed") { it.state["confirm"] }

    edges {
        edge("ask-question", "validate")
        edge("validate", "confirm") { it.data == true }
        edge("validate", "ask-question") { it.data == false } // Loop back
        edge("confirm", "ask-question") { result ->
            // Loop if not confirmed
            (result.data as? Boolean) != true
        }
        edge("confirm", "confirmed") { result ->
            // Exit when confirmed
            (result.data as? Boolean) == true
        }
    }

    allowCycles = true
}

Use Case 3: Retry with Backoff

Retry failing operations with exponential backoff:

val retryWorkflow = graph("api-retry") {
    agent("call-api", apiAgent)
    agent("check-result", resultCheckAgent)
    agent("backoff", backoffAgent)
    output("success") { it.state["call-api"] }

    edges {
        edge("call-api", "check-result")
        edge("check-result", "success") { result ->
            // Exit on success
            (result.data as? Map<*, *>)?.get("success") == true
        }
        edge("check-result", "backoff") { result ->
            // Retry on failure
            val retries = ctx.state["retries"] as? Int ?: 0
            (result.data as? Map<*, *>)?.get("success") != true && retries < 5
        }
        edge("backoff", "call-api") // Loop back after waiting
    }

    allowCycles = true
}

Validation Examples

Example 1: Validate Before Deployment

fun deployGraph(graph: Graph): Result<Unit> {
    // Validate before deploying to production
    val validation = GraphValidator.validate(graph)

    return when (validation) {
        is SpiceResult.Success -> {
            // Graph is valid, proceed with deployment
            deployToProduction(graph)
            Result.success(Unit)
        }
        is SpiceResult.Failure -> {
            // Log validation errors
            logger.error("Graph validation failed: ${validation.error.message}")
            Result.failure(Exception(validation.error.message))
        }
    }
}

Example 2: CI/CD Validation

@Test
fun `test all production graphs are valid`() {
    val graphs = listOf(
        createUserWorkflow(),
        createDataProcessingWorkflow(),
        createAnalyticsWorkflow()
    )

    graphs.forEach { graph ->
        val result = GraphValidator.validate(graph)
        assertTrue(result.isSuccess, "Graph ${graph.id} should be valid")
    }
}

Example 3: Development-Time Checks

fun createWorkflow(): Graph {
    val graph = graph("my-workflow") {
        agent("step1", agent1)
        agent("step2", agent2)
        agent("step3", agent3)
        output("result") { it.state["step3"] }
    }

    // Validate immediately during development
    require(GraphValidator.validate(graph).isSuccess) {
        "Graph validation failed"
    }

    return graph
}

Example 4: Interactive Validation

fun validateAndReport(graph: Graph) {
    println("🔍 Validating graph: ${graph.id}")

    val result = GraphValidator.validate(graph)

    when (result) {
        is SpiceResult.Success -> {
            println("✅ Graph is valid!")
            println("   Nodes: ${graph.nodes.size}")
            println("   Edges: ${graph.edges.size}")
            println("   Entry: ${graph.entryPoint}")

            val terminals = GraphValidator.findTerminalNodes(graph)
            println("   Terminals: $terminals")

            val isDAG = GraphValidator.isDAG(graph)
            println("   Is DAG: $isDAG")
        }
        is SpiceResult.Failure -> {
            println("❌ Graph is invalid!")
            val error = result.error as SpiceError.ValidationError
            println("   Message: ${error.message}")

            val errors = error.context["errors"] as? List<String>
            errors?.forEach { err ->
                println("   - $err")
            }
        }
    }
}

Error Messages

Validation errors are detailed and actionable:

Graph validation failed: Graph must have at least one node

Graph validation failed: Entry point 'start' does not exist in graph

Graph validation failed: Edge references non-existent 'from' node: node1

Graph validation failed: Edge references non-existent 'to' node: node2

Graph validation failed: Graph contains cycles involving nodes: node1, node2, node3

Graph validation failed: Graph contains unreachable nodes: orphan1, orphan2

Multiple errors are combined:

Graph validation failed: Entry point 'start' does not exist in graph;
Edge references non-existent 'to' node: node2;
Graph contains unreachable nodes: orphan

Cycle Detection Algorithm

The validator uses Depth-First Search (DFS) with a recursion stack:

1. Mark node as visiting (recursion stack)
2. For each neighbor:
   - If neighbor is in recursion stack → Cycle found!
   - If neighbor not visited → Recursively visit
3. Mark node as visited
4. Remove from recursion stack

Time Complexity: O(V + E) where V = nodes, E = edges

Self-Loop Detection

Self-loops (node pointing to itself) are automatically detected as cycles:

// ❌ Invalid: Self-loop
val invalid = Graph(
    id = "self-loop",
    nodes = mapOf("node1" to someNode),
    edges = listOf(
        Edge("node1", "node1")  // Self-loop!
    ),
    entryPoint = "node1"
)

// Error: "Graph contains cycles involving nodes: node1"

Complex Cycle Example

// ❌ Invalid: Complex cycle
val invalid = graph("complex-cycle") {
    agent("a", agent1)
    agent("b", agent2)
    agent("c", agent3)
    agent("d", agent4)

    edges {
        edge("a", "b")
        edge("b", "c")
        edge("c", "d")
        edge("d", "b")  // Creates cycle: b → c → d → b
    }
}

// Error: "Graph contains cycles involving nodes: b, c, d"

Best Practices

✅ Do's

1. Validate early - In development, not just production
2. Add validation tests - Test graphs in CI/CD
3. Use meaningful IDs - Easier to debug validation errors
4. Check terminal nodes - Ensure workflows have clear end points
5. Document graph structure - Especially for complex workflows

❌ Don'ts

1. Don't skip validation - Runtime errors are harder to debug
2. Don't ignore warnings - They indicate potential issues
3. Don't create complex graphs without testing - Start small
4. Don't modify graphs after validation - Re-validate if changed
5. Don't suppress validation errors - Fix the root cause

Validation in Production

Strategy 1: Validate on Load

class GraphRepository {
    fun loadGraph(id: String): Graph {
        val graph = loadFromDatabase(id)

        // Validate before returning
        val validation = GraphValidator.validate(graph)
        if (validation.isFailure) {
            throw IllegalStateException("Loaded invalid graph: $id")
        }

        return graph
    }
}

Strategy 2: Validate on Create

class GraphBuilder {
    fun build(): Graph {
        val graph = Graph(
            id = id,
            nodes = nodes,
            edges = edges,
            entryPoint = entryPoint
        )

        // Validate immediately
        val validation = GraphValidator.validate(graph)
        require(validation.isSuccess) {
            "Failed to build graph: ${validation.exceptionOrNull()?.message}"
        }

        return graph
    }
}

Strategy 3: Pre-Deployment Gate

fun deployWorkflow(graph: Graph) {
    // Gate 1: Validation
    val validation = GraphValidator.validate(graph)
    if (validation.isFailure) {
        throw DeploymentException("Validation failed")
    }

    // Gate 2: Additional checks
    if (graph.nodes.size > 100) {
        throw DeploymentException("Graph too large")
    }

    // Deploy
    deploy(graph)
}

Troubleshooting

Issue: "Entry point does not exist"

Problem: Entry point ID doesn't match any node ID

Solution:

// Check node IDs match entry point
println("Entry point: ${graph.entryPoint}")
println("Node IDs: ${graph.nodes.keys}")

Issue: "Graph contains cycles"

Problem: Circular dependencies in graph

Solution:

// Use isDAG to confirm
if (!GraphValidator.isDAG(graph)) {
    // Manually check edges for cycles
    graph.edges.forEach { edge ->
        println("${edge.from} → ${edge.to}")
    }
}

Issue: "Unreachable nodes"

Problem: Nodes not connected to entry point

Solution:

// Check connectivity
fun printReachability(graph: Graph) {
    val reachable = mutableSetOf<String>()

    fun dfs(nodeId: String) {
        if (nodeId in reachable) return
        reachable.add(nodeId)
        graph.edges.filter { it.from == nodeId }
            .forEach { dfs(it.to) }
    }

    dfs(graph.entryPoint)

    val unreachable = graph.nodes.keys - reachable
    println("Unreachable: $unreachable")
}

Next Steps

• Learn Error Handling Strategies
• Review Graph Middleware
• Explore Performance Optimization

Related

• Graph System Overview
• Graph Nodes
• Graph Checkpoint
• Testing Best Practices