dag-cycle-analysis

license	Apache-2.0
name	dag-cycle-analysis
description	Graph algorithms for detecting and resolving cycles in directed graphs and workflow definitions
category	Agent & Orchestration
tags	["dag","cycle-detection","graph-theory","validation","algorithms"]

Hierarchical Cycle Analysis

Skill ID: hierarchical-cycle-analysis
Domain: Complex systems, network science, information architecture

Description

This skill applies rigorous cycle-theoretic methods to understand the hidden organizational structure of hierarchical systems. It reveals how systems that appear "acyclic" (DAGs) actually contain rich cyclic structure that determines their information-processing capabilities.

Decision Points

Algorithm Selection Tree

IF analyzing system behavior/comparison
├── THEN decompose DAG = undirected graph + directional metadata
├── IF need functional differences between similar topologies
│   └── THEN use metadata metrics (height, stretch, balance) + topology
└── IF need structural simplification
    └── THEN apply transitive reduction first

IF detecting cycles in DAG
├── IF raw cycle count needed
│   └── THEN use DFS on undirected substrate
├── IF functional classification needed
│   ├── THEN apply path-wedge contraction first
│   └── THEN classify: feedback/shortcut/diamond/mixer
└── IF comparing cycle organization
    └── THEN compute antichain structure + metadata positioning

IF system shows unexpected behavior despite "good" topology
├── THEN check antichain structure (parallel vs sequential)
├── THEN measure cycle height/stretch/balance distribution
└── IF still unclear, THEN load metadata-localizes-topology framework

IF redesigning hierarchical process
├── IF need resilience THEN preserve/add diamonds (parallel alternatives)
├── IF need integration THEN check mixer positioning (multi-level convergence)
└── IF optimizing efficiency THEN identify shortcuts for potential removal

Stopping Criteria

• Stop iterating when TR converges (no more transitive edges to remove)
• Stop analysis when all cycles classified into four classes
• Stop decomposition when undirected substrate + metadata separated
• Escalate to domain expert if >50% of cycles are mixers (unusual integration pattern)

Failure Modes

Topology Blindness

Symptom: Two hierarchies have identical node/edge counts but behave differently
Diagnosis: Analyzing structure without considering ordering metadata
Detection Rule: If degree distributions match but information flow differs
Fix: Decompose into undirected graph + metadata, compute metadata-derived metrics

Acyclic Confusion

Symptom: Claiming "no cycles exist" in hierarchical system
Diagnosis: Confusing directional constraint-compatibility with topological absence
Detection Rule: If someone says "it's a DAG so no loops"
Fix: Extract undirected substrate to reveal hidden cyclic structure

Cycle Conflation

Symptom: Counting all cycles as equivalent structural features
Diagnosis: Missing functional differences between diamonds vs mixers
Detection Rule: If analysis treats 3-node triangle same as 6-node mixer
Fix: Apply path-wedge contraction, classify into four classes

Over-Reduction

Symptom: System performance degrades after applying transitive reduction
Diagnosis: Removing shortcuts that were functionally valuable despite being informationally redundant
Detection Rule: If TR improves "structural metrics" but worsens latency/reliability
Fix: Distinguish informational redundancy from functional optimization

Antichain Ignorance

Symptom: Cannot explain why parallel nodes behave differently
Diagnosis: Missing hierarchical coordinate system, treating all "same level" nodes as equivalent
Detection Rule: If surprised by different behaviors at "same hierarchical level"
Fix: Compute antichain decomposition, analyze cycle organization by level

Worked Examples

Example 1: Organizational Chart Analysis

Scenario: Two companies with identical reporting structures (30 nodes, 35 edges) but different decision-making speeds.

Step 1 - Decomposition:

Company A: Extract undirected substrate → 12 cycles found
Company B: Extract undirected substrate → 12 cycles found

Topology identical, so analyze metadata.

Step 2 - Classification:

Apply transitive reduction:
Company A: 8 diamonds, 2 mixers remain
Company B: 4 diamonds, 4 mixers remain

Step 3 - Metadata Analysis:

Company A diamonds: Height 2-4 (mid-hierarchy resilience)
Company A mixers: Height 6-7 (senior integration points)

Company B diamonds: Height 1-2 (low-level redundancy)  
Company B mixers: Height 3-8 (integration at all levels)

Expert Insight: Company B's distributed mixers create more integration overhead but higher adaptability. Company A's concentrated senior mixers create bottlenecks but faster routine decisions.

Novice Miss: Would only count total cycles (12 each) and conclude structures identical.

Example 2: Software Architecture Comparison

Scenario: Microservice dependency graphs with similar complexity metrics but different deployment reliability.

Step 1 - Cycle Detection:

System X: 45 cycles in undirected substrate
System Y: 47 cycles in undirected substrate  

Step 2 - TR + Classification:

System X after TR: 15 diamonds, 8 mixers
- Diamonds concentrated in data layer (height 1-3)
- Mixers in API gateway layer (height 5-6)

System Y after TR: 8 diamonds, 12 mixers  
- Diamonds scattered across all layers
- Mixers concentrated in business logic (height 3-4)

Step 3 - Antichain Analysis:

System X: 6 major antichains, services well-layered
System Y: 3 major antichains, more cross-cutting concerns

Expert Diagnosis: System X has resilient data access (diamonds) but single points of integration failure. System Y has complex business logic integration creating brittleness.

Decision: System X better for read-heavy workloads, System Y better for complex transactional workflows.

Quality Gates

Analysis Complete When:

• DAG decomposed into undirected substrate + directional metadata
• All cycles classified into exactly four classes (feedback/shortcut/diamond/mixer)
• Antichain structure computed and hierarchical coordinates established
• Both topological metrics (cycle count, size distribution) and metadata metrics (height, stretch, balance) calculated
• Transitive reduction applied and convergence verified
• Diamond vs mixer distinction mapped to functional requirements
• Edge cases identified where framework assumptions may not hold
• Integration points (mixers) and resilience points (diamonds) documented
• Comparison baseline established using both structural and positional metrics

Ready for Implementation When:

• Specific cycle classes linked to system requirements (resilience needs → diamond preservation)
• Optimization targets defined (remove shortcuts vs preserve alternatives)

NOT-FOR Boundaries

Do NOT use this skill for:

• Real-time dynamic graphs: For temporal networks, use temporal-graph-analysis instead
• Undirected networks: For social networks without ordering, use community-detection instead
• Weighted optimization: For cost/flow optimization, use network-flow-algorithms instead
• Stochastic processes: For probabilistic workflows, use markov-chain-analysis instead

Delegate when:

• Graph size >10K nodes: Use distributed-graph-algorithms for scalability
• Real-time constraints: Use streaming-dag-validation for online systems
• Complex temporal dynamics: Use temporal-motif-analysis for time-varying hierarchies
• Domain-specific rules: Load domain frameworks (org-behavior, software-architecture, etc.)

Framework applies only when:

• Clear ordering constraint exists (time, causality, hierarchy, dependency)
• System can be meaningfully represented as DAG
• Cycles represent structural relationships, not just algorithmic artifacts
• Static analysis sufficient (system not rapidly evolving)