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.

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.

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.

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.

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

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.

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

Compute the CPDAG of cg, apply the bk orientations, and close under Meek's rules R1-R4.

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

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

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

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

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

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

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

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.

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

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

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

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.

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

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.

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

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.

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.

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

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.

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

mag_to_pag(cg::MAG) -> PAG

Compute the Partial Ancestral Graph (PAG) representing cg's Markov equivalence class.

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.

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

mag_from_pag(cg::PAG) -> MAG

Pick one MAG representative of cg's Markov equivalence class. 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.

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

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.

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