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
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:

• 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 and metadata metrics (height, stretch, balance) calculated
• Transitive reduction applied and convergence verified
• Diamond vs mixer distinction mapped to functional requirements
• Integration points (mixers) and resilience points (diamonds) documented

Ready for Implementation When:

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

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)