Workflow Pipeline Validator

Build a workflow pipeline validator that constructs computational job graphs and validates their structure before execution.

Background

Scientific computing workflows often consist of multiple processing steps with complex dependencies. Before executing these workflows, it's critical to validate that the job graph is well-formed and free of structural issues that would prevent successful execution.

Requirements

Implement a workflow validator with the following functionality:

1. Job Graph Construction

Create a system that builds a computational workflow with the following structure:

• A root job that initiates the workflow
• Three parallel data processing jobs (process_a, process_b, process_c) that run after the root job
• Two aggregation jobs (aggregate_ab, aggregate_c) where:
  • aggregate_ab depends on process_a and process_b completing
  • aggregate_c depends on process_c completing
• A final merge job that runs after both aggregation jobs complete

Each job should perform a simple operation (e.g., returning a value or appending to a list) to demonstrate the workflow structure.

2. Graph Validation

Implement validation that checks for:

• Cycle detection: Ensure the job graph is acyclic (no circular dependencies)
• Connectivity verification: Confirm all jobs are reachable from the root job

The validator should be able to detect and report:

• If a cycle exists in the dependency graph
• If there are unreachable jobs (orphaned nodes)

3. Test Cases @test

Implement tests in test_validator.py that verify:

Test 1: Valid workflow structure @test

• Build the workflow described above
• Verify it passes validation (no cycles, all jobs connected)
• Confirm the workflow can identify its job count correctly

Test 2: Cycle detection @test

• Create a workflow that intentionally contains a cycle
• Verify the validator detects the cycle
• Ensure appropriate error information is provided

Test 3: Unreachable job detection @test

• Create a workflow with an orphaned job (not connected to the root)
• Verify the validator identifies the connectivity issue

Implementation Notes

• Focus on correctly modeling the dependency relationships between jobs
• The validation logic should run before workflow execution
• Keep the actual job operations simple - the focus is on graph structure and validation

Dependencies { .dependencies }

toil { .dependency }

Provides pipeline management and workflow orchestration capabilities.

Deliverables

• validator.py: Core implementation of the workflow validator
• test_validator.py: Test cases verifying the validation functionality