| 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
Source: Vasiliauskaite, Evans & Expert — "Cycle Analysis of Directed Acyclic Graphs"
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, and provides frameworks for distinguishing functional differences that topology alone cannot capture.
Activation Triggers
Load this skill when:
- Analyzing hierarchical systems (org charts, citation networks, task dependencies, software architectures)
- Someone claims a system is "acyclic" or "has no loops"
- Trying to understand why two similarly-structured hierarchies behave differently
- Diagnosing bottlenecks or failure modes in information flow
- Evaluating whether structural metrics actually capture functional differences
Core Mental Models
1. DAG = Undirected Graph + Directional Metadata
Every DAG decomposes into two separable elements:
- An undirected substrate containing the actual topology (cycles, connectivity)
- Directional metadata derived from an ordering constraint (time, causality, hierarchy, dependency)
"Acyclic" only means directions respect the ordering — it does NOT mean the underlying structure lacks cycles. The same undirected structure + different metadata = different information processing.
2. The Four-Class Cycle Taxonomy
After path-wedge contraction, all cycles belong to exactly four classes:
| Class | Structure | Information Role | Present in TR-DAG? |
|---|
| Feedback Loop | All neutral nodes | Recirculation, refinement | No |
| Shortcut | Transitively reducible | Redundant path, acceleration | No |
| Diamond | Unitary antichains | Resilient alternatives, robustness | Yes |
| Mixer | Non-unitary antichain | Multi-source integration | Yes |
In transitively-reduced DAGs, only diamonds and mixers exist — the fundamental organizing structures of hierarchies. See diagrams/03_erDiagram_four-class_cycle_taxonomy_with.md for a detailed ER view with functional attributes.
3. Transitive Reduction as Truth-Seeking
TR removes shortcuts (informationally redundant), preserves diamonds (genuinely different paths), and reveals mixers (true integration points). Apply when distinguishing essential from accidental complexity. Warning: shortcuts may optimize latency — informational redundancy ≠ functional uselessness.
4. Antichains as Hierarchical Coordinates
An antichain is a set of nodes with no ordering relationship — incomparable, parallel, at the "same level." Cycle antichain structure determines class: unitary → Diamond; non-unitary → Mixer.
5. The Topology-Metadata Gap
Purely topological metrics (node count, edge count, clustering) cannot distinguish DAGs with different functional behaviors. Always combine topological metrics (cycle count, size) with metadata metrics (height, stretch, balance, antichain structure).
Decision Points
Algorithm Selection Tree
See diagrams/01_flowchart_hierarchical_cycle_analysis_de.md for a visual rendering of this decision 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: 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: 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: 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: 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: 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 → analyze metadata.
Step 2 — Classification:
Company A after TR: 8 diamonds, 2 mixers
Company B after TR: 4 diamonds, 4 mixers
Step 3 — Metadata Analysis:
Company A: diamonds at height 2-4 (mid-hierarchy resilience), mixers at height 6-7
Company B: diamonds at height 1-2 (low-level redundancy), mixers at height 3-8
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: Counts total cycles (12 each) and concludes 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; System Y: 47 cycles.
Step 2 — TR + Classification:
System X: 15 diamonds (data layer, height 1-3), 8 mixers (API gateway, height 5-6)
System Y: 8 diamonds (scattered all layers), 12 mixers (business logic, height 3-4)
Step 3 — Antichain Analysis: System X: 6 antichains (well-layered). System Y: 3 antichains (more cross-cutting concerns).
Diagnosis: System X better for read-heavy workloads; System Y better for complex transactional workflows.
Quality Gates
Analysis Complete When:
Ready for Implementation When:
Reference Documentation
| File | Load When... |
|---|
dag-decomposition-for-hierarchical-reasoning.md | Formally separating topological structure from ordering constraints |
four-cycle-classes-information-processing.md | Classifying specific cycles by information-processing role |
transitive-reduction-information-minimization.md | Simplifying hierarchy to essential structure |
antichains-and-hierarchical-coordinates.md | Understanding hierarchical positioning, identifying parallel nodes |
metadata-localizes-topology.md | Two systems have similar topology but different behavior |
minimal-cycle-basis-as-mesoscopic-descriptor.md | Characterizing overall system organization |
failure-modes-hierarchical-analysis.md | Diagnosing why standard graph metrics aren't working |
when-does-dag-analysis-apply.md | Determining if this framework fits your problem |
Full trigger-indexed list: references/INDEX.md
Bundled Assets
| Directory | Index | Contents |
|---|
diagrams/ | diagrams/INDEX.md | Decision tree flowchart, cycle taxonomy mindmap, four-class cycle ER diagram |
references/ | references/INDEX.md | Eight deep-reference files on decomposition, cycle classification, TR, antichains, metadata, MCB, failure modes, and applicability |
NOT-FOR Boundaries
Do NOT use this skill for:
- Real-time dynamic graphs: Use
temporal-graph-analysis instead
- Undirected networks: Use
community-detection instead
- Weighted optimization: Use
network-flow-algorithms instead
- Stochastic processes: Use
markov-chain-analysis instead
Delegate when:
- Graph size >10K nodes: Use
distributed-graph-algorithms
- Real-time constraints: Use
streaming-dag-validation
- Complex temporal dynamics: Use
temporal-motif-analysis
Framework applies only when:
- Clear ordering constraint exists (time, causality, hierarchy, dependency)
- System can be meaningfully represented as DAG
- Cycles represent structural relationships, not algorithmic artifacts
- Static analysis sufficient (system not rapidly evolving)
Shibboleths
Has NOT internalized this framework:
- Uses "acyclic" and "has no cycles" interchangeably without qualification
- Compares hierarchies using only node/edge counts and clustering coefficients
- Treats all cycles in a network as the same kind of structure
- Cannot explain the difference between a diamond and a mixer
- Assumes transitive reduction is always desirable or always preserves function
Has internalized this framework:
- Immediately asks "what's the ordering constraint?" when shown a DAG
- Distinguishes substrate topology from directional metadata
- Recognizes that cycle classification requires path-wedge contraction
- Can point to specific diamonds/mixers and explain their information-processing role
- Combines topological and metadata metrics when comparing systems
- Knows when this framework's assumptions break down (
when-does-dag-analysis-apply.md)
