Dag Cycle Analysis

---
license: Apache-2.0
name: dag-cycle-analysis
description: Analyze undirected cycle structure within a valid DAG using the source paper's orientation and contraction method. Use for cycle-basis analysis with explicit graph and reduction choices. NOT for directed feedback loops, workflow deadlocks, or runtime resilience claims.
metadata:
  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"

## Method boundary and source correction

This method starts from an undirected cycle basis and restores direction from
explicit ordering metadata for a valid simple DAG. A directed feedback witness
invalidates that premise and belongs to SCC/directed-cycle diagnosis first.
Record whether analysis uses the original DAG or its transitive reduction: the
reduction preserves reachability but changes the underlying cycle space, and an
MCB need not be unique. The four paper images follow its orientation and
wedge-contraction procedure; they do not prove resilience, payload fusion, or
runtime safety. Keep this Apache-2.0 bundle's license unchanged.

## 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.

```mermaid
flowchart TD
  A[Directed graph and ordering metadata] --> B{Simple acyclic DAG?}
  B -->|no| X[Report directed witness or SCC; repair premise]
  B -->|yes| C{Choose original graph or transitive reduction}
  C --> D[Extract underlying undirected graph]
  D --> E[Compute a recorded cycle basis]
  E --> F[Restore orientation and contract eligible neutral wedges]
  F --> G[Report paper class as structural descriptor]
  G --> H[Validate domain interpretation separately]
```

### 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 review** when interpretation would attach functional or policy meaning to a structural descriptor.

## 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](references/INDEX.md)

## Bundled Assets

| Directory | Index | Contents |
|-----------|-------|----------|
| `diagrams/` | [diagrams/INDEX.md](diagrams/INDEX.md) | Decision tree flowchart, cycle taxonomy mindmap, four-class cycle ER diagram |
| `references/` | [references/INDEX.md](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`)