# CCD — Cyclic Causal Discovery

**Type:** Constraint-based (DCG / cyclic)  
**Output:** Cyclic PAG (partial ancestral graph for directed cyclic graphs)

`Ccd` implements **Richardson’s Cyclic Causal Discovery algorithm** for **directed cyclic graphs (DCGs)**.  
Given a conditional independence test that is valid for data generated by a DCG, CCD returns a **cyclic PAG**: a mixed graph (with circles, arrowheads, and special underline / dotted-underline marks) that represents the **Markov equivalence class** of DCGs compatible with the observed independences.

---

## Key Idea

The original CCD algorithm generalizes PC-style reasoning to **graphs with feedback loops**.

In Tetrad’s implementation:

1. **Skeleton via FAS**
    - Runs the standard Fast Adjacency Search (`Fas`) over the variables using the provided `IndependenceTest`.
    - Produces an undirected skeleton, then reorients all endpoints to circles (o-o).

2. **Step B – Unshielded triples: underline vs collider**
    - For each unshielded triple A–B–C, looks up a separating set S(A, C).
    - If B is in S(A, C): record A–B–C as a **non-collider** (underline triple).
    - If B is not in S(A, C): record A–B–C as a **collider**, attempting to orient A → B ← C (subject to forbidden-edge knowledge).

3. **Step C – Orientation propagation**
    - Iteratively uses modified CCD rules and further independence checks to orient additional edges, respecting underline and collider markings and background knowledge.

4. **Steps D–F – Dotted underlines and sup-sepsets**
    - Introduces **dotted underlines** and constructs sup-sepsets (augmented separating sets) to encode more refined d-connection information.
    - Uses these to further orient edges both **into** and **out of** marked triples, again respecting knowledge.

5. **R1 “push-away” rule**
    - Optionally applies an R1-style **push-away** rule: arrowheads into a node B induce orientations away from B along certain underlined structures, propagating directionality in a way that is sound for DCGs.

The result is a **cyclic PAG** with:
- arrowheads and tails indicating required orientations,
- circles for ambiguous endpoints, and
- underline/dotted-underline annotations encoding non-colliders and special CCD constraints.

---

## When to Use

Use `Ccd` when:

- You believe your system may have **feedback loops** or **instantaneous cycles** (for example, economic models, biological regulation, or control systems).
- You want a **constraint-based** method that is **sound for DCGs**, rather than forcing a DAG approximation.
- You have a **CI test** appropriate for DCGs (often a standard CI test is used as an approximation, but CCD’s guarantees presume an oracle for DCG Markov properties).
- You want an **equivalence-class representation** (cyclic PAG) rather than a single oriented graph.

It is especially useful when:

- You want to distinguish between **purely acyclic** explanations and those that genuinely require cycles.
- You want a principled alternative to running DAG-only algorithms on systems you know are cyclic.

Related algorithms:

- **PC / FCI / RFCI**: acyclic or PAG-based; do not directly target DCGs.
- **Dagma / score-based DAG learners**: assume acyclicity.
- **SingleGraphAlg**: for analyzing a fixed imported cyclic graph, not learning it.

---

## Prior Knowledge Support

**Does it accept background knowledge?**  
Yes, but **only forbidden edges** are honored.

- `Knowledge` may specify **forbidden directed edges** X → Y.
    - CCD will then refuse to orient X → Y and may instead leave the endpoint ambiguous.
- **Required edges are explicitly disallowed** in this implementation:
    - If you supply required edges, CCD will throw an error.
    - This is intentional: forcing orientations not justified by CCD can break correctness for DCGs.

---

## Strengths

- **Designed for cyclic causal structure**
    - One of the few algorithms explicitly targeting **directed cyclic graphs**.
- **Equivalence-class output**
    - Produces a cyclic PAG that encodes all DCGs consistent with the discovered independences.
- **Richer edge semantics**
    - Underlines and dotted underlines provide nuanced information about non-colliders and special separation properties.
- **Respects forbidden edges**
    - Lets you rule out impossible directions while preserving CCD’s theoretical guarantees.

---

## Limitations

- **No required edges**
    - Cannot enforce X → Y; only forbid directions.
- **Assumes a DCG-appropriate independence oracle**
    - Theoretical guarantees rely on an oracle-level CI notion for DCGs; practical tests are approximations.
- **Complex output**
    - Cyclic PAGs with underline/dotted-underline annotations are harder to interpret than standard DAGs/CPDAGs.
- **Same sensitivity to CI-test errors as other constraint-based methods**
    - Finite-sample noise can affect adjacency and orientation decisions.

---

## Key Parameters in Tetrad

`Ccd` is configured via its setters and the underlying `IndependenceTest`.

All important controls:

| Parameter (camelCase) | Description |
|------------------------|-------------|
| `depth` | Maximum conditioning-set size used for CCD-specific separation checks (e.g., Steps D and F). A value of `-1` means no depth limit. |
| `applyR1` | Boolean. If `true`, applies the **R1 push-away rule**, which orients arrowheads away from tails in certain underline structures, matching the CCD-specific adaptation of Zhang’s propagation rules. |
| `fdrQ` | The **false discovery rate threshold q** for FDR-controlled independence testing. If set, CCD uses FDR-adjusted p-values to decide conditional independence. |
| `verbose` | Boolean. If `true`, prints detailed diagnostic output about Steps A–F, collider detection, underline detection, orientation rules, and FDR-adjusted decisions. |

You indirectly control:

- The **significance level** and behavior of CI tests via the chosen `IndependenceTest` (for example, Fisher Z with its alpha).
- Any caching / performance behavior via `CachingIndependenceTest`.

---

## Reference

Richardson, T. S. (2013).  
**A discovery algorithm for directed cyclic graphs.**  
arXiv:1302.3599.

See also:

Glymour, C., & Cooper, G. (Eds.). (1999).  
**Computation, Causation, and Discovery.**  
Chapter 7 discusses cyclic discovery ideas related to CCD.

---

## Summary

`Ccd` is Tetrad’s implementation of **Richardson’s cyclic discovery algorithm**, taking a conditional independence test for DCGs and returning a **cyclic PAG** with underline and dotted-underline annotations, while honoring forbidden directions but refusing required edges—your go-to constraint-based learner when feedback loops are part of the story.