Operations

skeleton(cg::Union{DAG,AbstractPDAG}) -> UG

Return the skeleton of cg: the undirected graph obtained by replacing every directed or partially-directed edge with an undirected edge.

Examples

julia> dag = DAG("A --> B --> C");

julia> skeleton(dag)
UG with 3 nodes and 2 edges:
  nodes: A, B, C
  edges:
    A --- B, B --- C

subgraph(cg::CausalGraph, nodes) -> CausalGraph

Return the subgraph of cg induced by nodes: restricted to the given node set, keeping only edges whose both endpoints are in nodes.

nodes may be a single Symbol or an AbstractVector{Symbol}.

The return type matches cg for most classes, but two classes are downgraded, because the induced subgraph need not satisfy the stronger class invariant:

• CPDAG subgraphs are returned as MPDAG: removing a node can orphan a directed edge that was only strongly protected by that node, but the result is still Meek-closed and therefore a valid MPDAG.
• PAG subgraphs are returned as UNKNOWN: the invariant marks of a Markov equivalence class are not preserved by node restriction, so the result need not be a valid PAG.

Examples

julia> dag = DAG("A --> B --> C, A --> C");

julia> sg = subgraph(dag, [:A, :B])
DAG with 2 nodes and 1 edge:
  nodes: A, B
  edges:
    A --> B

moralize(cg::Union{DAG,AbstractPDAG}) -> UG

Return the moral graph of cg. Connects every pair of directed parents that share a common child (adding a "marriage" edge), then replaces every edge with an undirected edge.

For AbstractPDAG, only directed parents participate in marriage edges; undirected neighbors are included in the skeleton but do not form a clique.

Examples

julia> dag = DAG("A --> C <-- B");

julia> moralize(dag)   # A and B are now married (share child C)
UG with 3 nodes and 3 edges:
  nodes: A, B, C
  edges:
    A --- C, B --- C, A --- B

julia> pdag = PDAG("A --> C <-- B, D --- C");

julia> moralize(pdag)   # A married to B (co-directed-parents of C); D not married
UG with 4 nodes and 4 edges:
  nodes: A, B, C, D
  edges:
    A --- C, B --- C, C --- D, A --- B

dag_from_pdag(cg::AbstractPDAG) -> DAG

Extend cg to a consistent DAG by orienting all undirected edges, using the Dor-Tarsi algorithm.

The algorithm repeatedly finds a potential-sink node x (no directed children, whose undirected neighbors form a clique, and whose undirected neighbors are each adjacent to every existing parent of x), orients all undirected edges toward x, and removes it. Raises an error if no valid DAG extension exists. The last condition on x's existing parents ensures the extension has exactly the same v-structures as cg.

Examples

julia> pdag = PDAG("A --- B --- C");

julia> dag = dag_from_pdag(pdag)
DAG with 3 nodes and 2 edges:
  nodes: A, B, C
  edges:
    A --> B, B --> C

References

• Dor and Tarsi (1992)
• Wienöbst et al. (27–30 Jul 2021)

dag_to_cpdag(cg::DAG) -> CPDAG

Return the CPDAG representing the Markov equivalence class (MEC) of cg.

The algorithm detects v-structures (unshielded colliders) to determine compelled edge orientations, builds an initial PDAG from the skeleton, then applies meek_closure to propagate all implied orientations.

Examples

julia> dag = DAG("A --> B");

julia> dag_to_cpdag(dag)
CPDAG with 2 nodes and 1 edge:
  nodes: A, B
  edges:
    A --- B

julia> dag = DAG("C --> X, A --> X + Y, Y --> Z");

julia> dag_to_cpdag(dag)
CPDAG with 5 nodes and 4 edges:
  nodes: A, C, X, Y, Z
  edges:
    A --- Y, C --> X, A --> X, Y --- Z

dag_to_mpdag(cg::DAG, bk = BackgroundKnowledge()) -> MPDAG

Return the MPDAG representing the DAGs that are Markov equivalent to cg and consistent with the background knowledge bk. This is the CPDAG of cg with the bk orientations applied and closed under Meek's rules R1-R4.

bk may be a BackgroundKnowledge or a string accepted by its constructor. Raises an error if cg itself violates bk; this guarantees the restricted equivalence class is non-empty, since it contains cg.

Examples

julia> dag = DAG("A --> B --> C");

julia> dag_to_cpdag(dag)
CPDAG with 3 nodes and 2 edges:
  nodes: A, B, C
  edges:
    A --- B, B --- C

julia> dag_to_mpdag(dag, "A --> B")
MPDAG with 3 nodes and 2 edges:
  nodes: A, B, C
  edges:
    A --> B, B --> C

References

• Meek (1995)

apply_background_knowledge(cg::AbstractPDAG, bk) -> MPDAG

Orient the edges of cg according to the background knowledge bk, then close under Meek's rules R1-R4 (see meek_closure), returning the MPDAG that represents the DAGs consistent with both cg and bk.

bk may be a BackgroundKnowledge or a string accepted by its constructor.

Per constraint, against the current state of the edge in cg:

Errors are raised because background knowledge cannot add or remove adjacencies, only orient existing edges. The orientations are applied one at a time, each followed by Meek's rules; an error is also raised if a later one contradicts an orientation this implies, i.e. if bk is inconsistent with cg (e.g. A --> B, C --> B on A --- B --- C).

Examples

julia> cpdag = CPDAG("A --- B --- C");

julia> apply_background_knowledge(cpdag, "C --> B")
MPDAG with 3 nodes and 2 edges:
  nodes: A, B, C
  edges:
    B --> A, C --> B

julia> apply_background_knowledge(cpdag, "C !--> B")
MPDAG with 3 nodes and 2 edges:
  nodes: A, B, C
  edges:
    A --- B, B --> C

References

• Meek (1995)
• Perković et al. (2017)

meek_closure(cg::AbstractPDAG; check_cycles::Bool = true, r4::Bool = true) -> MPDAG

Apply Meek's orientation rules (R1-R4) to cg until no further orientations are implied, returning the resulting MPDAG.

The four rules are:

• R1: a --> b --- c, a not adjacent to c –> orient b --> c
• R2: a --- b, directed path a --> w --> b exists –> orient a --> b
• R3: a --- b, two parents c, d of b with c not adjacent to d, and a --- c, a --- d –> orient a --> b
• R4: a --- b, a --- c, c not adjacent to b, a adjacent to d, and a directed path c --> d --> b exists –> orient a --> b

Keyword arguments

• check_cycles: when true (default), every candidate orientation is verified not to create a directed cycle before being applied. This check is redundant if cg is a genuine Meek pattern – every directed edge already justified by an unshielded collider – since Meek's Theorem 3 then guarantees no cycle can arise. Potentially unsafe downstream, since it always returns an MPDAG without verifying acyclicity.
• r4: whether to apply R4 (default true). R4 is only needed when cg carries directed edges beyond what its own v-structures imply (background knowledge).

Examples

julia> pdag = PDAG("A --> B --- C");

julia> result = meek_closure(pdag)
MPDAG with 3 nodes and 2 edges:
  nodes: A, B, C
  edges:
    A --> B, B --> C

References

• Meek (1995)

latent_project(cg::DAG, latents) -> ADMG

Project out latent (unobserved) variables from cg to produce an ADMG over the observed variables only.

latents may be a single Symbol or an AbstractVector{Symbol}.

Each latent node v is eliminated by node substitution: directed edges p --> c are added for every parent p and child c of v, and bidirected edges s <-> c are added for every sibling s (bidirected neighbor) and child c of v. All pairs of children of v also become bidirected-connected.

Examples

julia> dag = DAG("U --> X + Y, X --> Y");

julia> latent_project(dag, :U)
ADMG with 2 nodes and 2 edges:
  nodes: X, Y
  edges:
    X --> Y, X <-> Y

exogenize(cg::DAG, nodes) -> DAG

Return a copy of cg with each node in nodes made exogenous: all incoming edges to that node are removed, and its parents are connected directly to its children to preserve reachability.

nodes may be a single Symbol or an AbstractVector{Symbol}.

Examples

julia> dag = DAG("A --> B --> C");

julia> dag2 = exogenize(dag, :B)
DAG with 3 nodes and 2 edges:
  nodes: A, B, C
  edges:
    A --> C, B --> C

normalize_latent_structure(cg::DAG, latents) -> DAG

Normalize the latent structure of cg while preserving the induced marginal model over the observed variables. Applies the following steps (Evans (2016), Lemmas 1-3):

1. Exogenize all latent nodes (remove their incoming edges, rerouting through their parents).
2. Remove latent nodes with at most one active child (they induce no confounding).
3. Remove latent nodes whose child set is a strict subset of another latent node's child set.

latents may be a single Symbol or an AbstractVector{Symbol}.

Examples

julia> dag = DAG("A --> U --> X + Y");

julia> result = normalize_latent_structure(dag, :U)
DAG with 4 nodes and 4 edges:
  nodes: A, U, X, Y
  edges:
    A --> X, A --> Y, U --> X, U --> Y

References

• Evans (2016)

condition_marginalize(cg::Union{DAG,ADMG,AbstractAG};
                      given = Symbol[], index = Symbol[]) -> AG

Return the AG over the remaining nodes after conditioning on given and marginalizing out index, following Definition 4.2.1 of Richardson and Spirtes (2002).

given and index may each be a single Symbol or an AbstractVector{Symbol}.

Two remaining nodes are adjacent if and only if they cannot be m-separated by any subset of the other remaining nodes given given. The edge type is determined by the anterior relations: a --> b if a is anterior to b but not vice versa; a <-> b if neither is anterior to the other; a --- b if each is anterior to the other.

At least one of given or index must be non-empty, and they must be disjoint.

Examples

julia> dag = DAG("U --> X + Y");

julia> condition_marginalize(dag; index = :U)
AG with 2 nodes and 1 edge:
  nodes: X, Y
  edges:
    X <-> Y

julia> admg = ADMG("U --> X + Y, X <-> Z, Y --> Z");

julia> condition_marginalize(admg; index = :U)
AG with 3 nodes and 3 edges:
  nodes: X, Y, Z
  edges:
    X <-> Y, X <-> Z, Y --> Z

julia> mag = MAG("A <-> X, X --> C, Y --> C, A <-> Y");

julia> condition_marginalize(mag; index = :A)
AG with 3 nodes and 2 edges:
  nodes: C, X, Y
  edges:
    X --> C, Y --> C

julia> condition_marginalize(mag; given = :A)
AG with 3 nodes and 3 edges:
  nodes: C, X, Y
  edges:
    X --> C, Y --> C, X <-> Y

References

• Richardson and Spirtes (2002)

enumerate_dags(cg::AbstractPDAG) -> Vector{DAG}

Enumerate every DAG in the Markov equivalence class (MEC) of cg.

Uses Chickering's (2002) recursive listing algorithm: applies Meek closure first to normalize cg, then branches on each undirected edge in lexicographic order, rejecting orientations that would introduce new v-structures or directed cycles, and propagating forced orientations via Meek's rules at each step.

Can call count_dags for sizing the problem before calling this function, as the number of DAGs in a MEC can be very large.

Examples

julia> pdag = PDAG("A --- B --- C");

julia> dags = enumerate_dags(pdag)
3-element Vector{DAG}:
 DAG with 3 nodes and 2 edges:
  nodes: A, B, C
  edges:
    A --> B, B --> C

 DAG with 3 nodes and 2 edges:
  nodes: A, B, C
  edges:
    B --> A, B --> C

 DAG with 3 nodes and 2 edges:
  nodes: A, B, C
  edges:
    B --> A, C --> B

References

• Chickering (2002)

count_dags(cg::AbstractPDAG) -> Int

Count the number of DAGs in the Markov equivalence class (MEC) of cg, without materializing them. Useful for sizing the problem before calling enumerate_dags.

Unlike calling length(enumerate_dags(cg)), this shares the same Chickering recursion but skips building a DAG (edge list, backend, validation) at every leaf of the search, only incrementing a counter instead.

Examples

julia> pdag = PDAG("A --- B --- C");

julia> count_dags(pdag)
3

enumerate_mags(cg::PAG; selection_bias::Bool = true) -> Vector{MAG}

Enumerate every MAG in the Markov equivalence class represented by the PAG cg (as produced by mag_to_pag).

By default the result includes MAGs with selection bias, i.e. with undirected (---) edges. Pass selection_bias = false to keep only the MAGs without undirected edges, as assumed by e.g. pagcauses and backdoor_set on a PAG; this also prunes the search. If cg itself has an undirected edge, no such MAG exists and the result is empty.

Every member of the class shares cg's invariant (non-circle) endpoint marks, so each circle endpoint is independently resolved to a tail or an arrowhead. For a single representative instead of the whole class, use mag_from_pag.

Algorithm

This is a brute-force search. With k circle endpoints in the PAG, it iterates all 2^k tail/arrow assignments; for each it builds the candidate graph, validates it as a MAG (which itself runs an m-separation search for maximality), and keeps it only when mag_to_pag maps it back to cg. The cost is therefore $O(2^k)$ candidates times the per-candidate MAG validation, so it is exponential in the number of circle endpoints. The number of MAGs in a class can likewise be very large. Parallelizes over Threads.nthreads() once there are enough of them to be worth splitting across tasks.

Examples

julia> pag = PAG("A o-o B o-o C");

julia> length(enumerate_mags(pag))
8

julia> length(enumerate_mags(pag; selection_bias = false))
5

References

• Zhang (2008)

ag_to_mag(cg::AG) -> MAG

Convert an AG to a Markov equivalent MAG by adding edges between every pair of non-adjacent nodes that cannot be m-separated by any subset of the remaining nodes.

For each non-separable pair (u, v), the edge type is determined by the ancestor relationship in the current graph:

• u ancestor of v –> add u –> v
• v ancestor of u –> add v –> u
• Neither –> add u <-> v (bidirected)

Edges are added one at a time and the graph is re-evaluated after each addition, since each new edge can change m-separation and ancestor relationships.

Examples

julia> ag = AG("A --> B --> C");

julia> ag_to_mag(ag)
MAG with 3 nodes and 2 edges:
  nodes: A, B, C
  edges:
    A --> B, B --> C

References

• Richardson and Spirtes (2002)

mag_to_pag(cg::MAG) -> PAG

Return the Partial Ancestral Graph (PAG) representing the Markov equivalence class of the MAG cg.

The PAG has the same skeleton (adjacencies) as cg. Each endpoint carries an invariant mark: an arrowhead (>) or tail (-) when that mark is shared by every MAG in the equivalence class, and a circle (o) otherwise. Circle marks are represented with the partial (o-o), partially_directed (o->), and partially_undirected (o--) edge kinds.

The algorithm starts from the skeleton with all marks set to circles, orients unshielded colliders as they appear in cg, and then applies Zhang's complete orientation rules R1-R10 until no further mark is implied.

Examples

julia> mag = MAG("A --> B <-- C");

julia> mag_to_pag(mag)
PAG with 3 nodes and 2 edges:
  nodes: A, B, C
  edges:
    A o-> B, C o-> B

References

• Zhang (2008)
• Ali et al. (2009)

mag_from_pag(cg::PAG) -> MAG

Return one MAG belonging to the Markov equivalence class represented by the PAG cg. This is a left inverse of mag_to_pag: mag_to_pag(mag_from_pag(pag)) recovers pag.

A PAG leaves some endpoints as circle marks (o) that are not invariant across the class. This resolves every circle into a tail or arrowhead, following Zhang's construction (2008, Theorem 2):

• A circle opposite a fixed mark always makes the edge directed. An o-> edge becomes --> (the circle turns into a tail), and an o-- edge becomes a directed edge pointing out of the tail end (the circle turns into an arrowhead).
• An undirected (---) edge carries selection bias and is kept unchanged.
• The remaining o-o edges form a chordal component, oriented into a DAG with no new unshielded colliders by Dor-Tarsi simplicial elimination.

Examples

julia> pag = PAG("A o-> B <-o C");

julia> mag_from_pag(pag)
MAG with 3 nodes and 2 edges:
  nodes: A, B, C
  edges:
    A --> B, C --> B

julia> mag = MAG("A --- B --- C --- D --- A");

julia> mag_from_pag(mag_to_pag(mag))
MAG with 4 nodes and 4 edges:
  nodes: A, B, C, D
  edges:
    A --- B, A --- D, B --- C, C --- D

References

• Zhang (2008)
• Dor and Tarsi (1992)

maximal_local_mag(cg::PAG, x::Symbol, c) -> UNKNOWN

Return the maximal local MAG for the local structure c at x in cg.

c may be a single Symbol or an AbstractVector{Symbol}.

This is cg with x <-> v for v in c and x --> v for x's other circle-marked neighbors (Algorithm 1 of Wang et al. (2023)), treated as local background knowledge about x and closed under the corresponding rule set.

c should be a valid local structure, i.e. an entry of possible_local_structures(cg, x); passing an invalid one gives an unsound result. The returned graph may still contain circles (unlike a MAG, which is why it is returned as UNKNOWN rather than validated as a MAG or PAG): only what the local background knowledge about x implies is resolved, not necessarily everything.

Throws ArgumentError if cg has selection bias (undirected edges), since both source papers assume none throughout.

Examples

julia> mag = MAG("A <-> X, B --> X, A <-> B, X --> Y");

julia> pag = mag_to_pag(mag);

julia> maximal_local_mag(pag, :X, :A)
UNKNOWN with 4 nodes and 4 edges:
  nodes: A, B, X, Y
  edges:
    A --> B, A o-> X, X --> B, X --> Y

References

• Wang et al. (2023)
• Wang et al. (2025)