Queries

nodes(cg::CausalGraph) -> Vector{Symbol}

Return the nodes of cg in alphabetical order.

Examples

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

julia> nodes(dag)
3-element Vector{Symbol}:
 :A
 :B
 :C

edges(cg::CausalGraph) -> Vector{CausalEdge}

Return the edges of cg.

Examples

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

julia> edges(dag)
2-element Vector{CausalEdge}:
 A --> B
 B --> C

has_edge(cg::CausalGraph, src::Symbol, dst::Symbol) -> Bool

Return true if there is any edge between src and dst in cg.

Examples

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

julia> has_edge(dag, :A, :B)
true

topological_sort(cg::DAG) -> Vector{Symbol}

Return the nodes of cg in topological order.

For every directed edge u --> v in cg, u appears before v in the returned vector.

Examples

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

julia> topological_sort(dag)
3-element Vector{Symbol}:
 :B
 :A
 :C

References

• Kahn (1962)

ancestors(cg::Union{DAG,AbstractPDAG,ADMG,AbstractAG}, node::Symbol; open::Bool = true) -> Vector{Symbol}

Return the ancestors of node in cg: all nodes from which node is reachable by following directed edges forward.

When open = true (open definition, default), node itself is excluded from the result. When open = false (closed definition), node is included. The default can be changed project-wide via Preferences.jl: set_preferences!(CausalStructures, "open" => false) (restart Julia after).

Examples

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

julia> ancestors(dag, :A)
Symbol[]

julia> ancestors(dag, :A, open = false)
1-element Vector{Symbol}:
 :A

julia> ancestors(dag, :C)
2-element Vector{Symbol}:
 :A
 :B

descendants(cg::Union{DAG,AbstractPDAG,ADMG,AbstractAG}, node::Symbol; open::Bool = true) -> Vector{Symbol}

Return the descendants of node in cg: all nodes reachable from node by following directed edges forward.

When open = true (open definition, default), node itself is excluded from the result. When open = false (closed definition), node is included. The default can be changed project-wide via Preferences.jl: set_preferences!(CausalStructures, "open" => false) (restart Julia after).

Examples

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

julia> descendants(dag, :A)
2-element Vector{Symbol}:
 :B
 :C

julia> descendants(dag, :C)
Symbol[]

julia> descendants(dag, :A, open = false)
3-element Vector{Symbol}:
 :A
 :B
 :C

anteriors(cg::Union{DAG,ADMG,AbstractPDAG,AbstractAG}, node::Symbol; open::Bool = true) -> Vector{Symbol}

Return the anteriors of node in cg: all nodes from which node is reachable by following directed edges backward or traversing undirected edges.

For a DAG or ADMG, anteriors are equivalent to ancestors (no undirected edges exist). For AbstractPDAG and AbstractAG, undirected edges extend the reachable set beyond strict ancestors.

When open = true (open definition, default), node itself is excluded from the result. When open = false (closed definition), node is included. The default can be changed project-wide via Preferences.jl: set_preferences!(CausalStructures, "open" => false) (restart Julia after).

Examples

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

julia> anteriors(dag, :C)  # same as ancestors for a DAG
2-element Vector{Symbol}:
 :A
 :B

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

julia> anteriors(pdag, :A)
Symbol[]

julia> anteriors(pdag, :C)  # C reaches B via undirected edge, then A via directed
2-element Vector{Symbol}:
 :A
 :B

posteriors(cg::Union{DAG,ADMG,AbstractPDAG,AbstractAG}, node::Symbol; open::Bool = true) -> Vector{Symbol}

Return the posteriors of node in cg: all nodes reachable from node by following directed edges forward or traversing undirected edges.

For a DAG or ADMG, posteriors are equivalent to descendants (no undirected edges exist). For AbstractPDAG and AbstractAG, undirected edges extend the reachable set beyond strict descendants.

When open = true (open definition, default), node itself is excluded from the result. When open = false (closed definition), node is included. The default can be changed project-wide via Preferences.jl: set_preferences!(CausalStructures, "open" => false) (restart Julia after).

Examples

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

julia> posteriors(dag, :A)  # same as descendants for a DAG
2-element Vector{Symbol}:
 :B
 :C

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

julia> posteriors(pdag, :A)  # B via directed edge, C via undirected edge from B
2-element Vector{Symbol}:
 :B
 :C

julia> posteriors(pdag, :C)  # C reaches B via undirected edge only
1-element Vector{Symbol}:
 :B

exogenous_nodes(cg::Union{DAG,ADMG,AG}) -> Vector{Symbol}
exogenous_nodes(cg::AbstractPDAG; undirected_as_parents = false) -> Vector{Symbol}
exogenous_nodes(cg::UG) -> Vector{Symbol}

Return all exogenous nodes in cg: nodes with no incoming directed edges.

For UG, where no directed edges exist, a node is considered exogenous if and only if it is isolated (no neighbors at all).

For AbstractPDAG, the undirected_as_parents keyword controls how undirected edges are treated. When true, a node incident to any undirected edge is not considered exogenous.

Examples

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

julia> exogenous_nodes(dag)
1-element Vector{Symbol}:
 :A

julia> ug = UG("A --- B, C");

julia> exogenous_nodes(ug)  # only the isolated node C
1-element Vector{Symbol}:
 :C

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

julia> exogenous_nodes(pdag)
2-element Vector{Symbol}:
 :A
 :C

julia> exogenous_nodes(pdag, undirected_as_parents = true)
1-element Vector{Symbol}:
 :A

parents(cg, node::Symbol) -> Vector{Symbol}

Return the parents of node in cg: nodes p such that p --> node is an edge in cg.

Equivalent to neighbors(cg, node; mode = :in). Applicable to DAG, AbstractPDAG, ADMG, AbstractAG, PAG, and UNKNOWN. For a PAG only definite parents (p --> node) are returned; a circle endpoint at node is not a parent.

Examples

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

julia> parents(dag, :B)
2-element Vector{Symbol}:
 :A
 :C

julia> parents(dag, :A)
Symbol[]

children(cg, node::Symbol) -> Vector{Symbol}

Return the children of node in cg: nodes c such that node --> c is an edge in cg.

Equivalent to neighbors(cg, node; mode = :out). Applicable to DAG, AbstractPDAG, ADMG, AbstractAG, PAG, and UNKNOWN. For a PAG only definite children (node --> c) are returned; a circle endpoint at the child is not a definite child.

Examples

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

julia> children(dag, :A)
2-element Vector{Symbol}:
 :B
 :C

julia> children(dag, :B)
Symbol[]

spouses(cg::Union{ADMG,AbstractAG,PAG}, node::Symbol) -> Vector{Symbol}

Return the spouses of node in cg: nodes connected to node via a bidirected edge (node <-> spouse).

Examples

julia> admg = ADMG("A --> B, A <-> C");

julia> spouses(admg, :A)
1-element Vector{Symbol}:
 :C

julia> spouses(admg, :B)
Symbol[]

neighbors(cg::CausalGraph, node::Symbol; mode::Symbol = :all) -> Vector{Symbol}

Return neighbors of node in cg, filtered by edge type via mode.

mode values:

• :all: all adjacent nodes
• :in: parents: nodes p with p --> node
• :out: children: nodes c with node --> c
• :undirected: undirected neighbors node --- c
• :bidirected: bidirected neighbors node <-> c

For a PAG the :in, :out, :undirected, and :bidirected modes return only neighbors joined by the corresponding definite (circle-free) edge. Neighbors joined by circle-mark edges (o->, o--, o-o) are reported by :all only.

Examples

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

julia> neighbors(dag, :B)
2-element Vector{Symbol}:
 :A
 :C

julia> neighbors(dag, :B, mode = :in)
2-element Vector{Symbol}:
 :A
 :C

julia> neighbors(dag, :A, mode = :out)
1-element Vector{Symbol}:
 :B

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

julia> neighbors(pdag, :B, mode = :undirected)
1-element Vector{Symbol}:
 :C

markov_blanket(cg::Union{DAG,AbstractPDAG,ADMG,AbstractAG,PAG}, node::Symbol) -> Vector{Symbol}

Return the Markov blanket of node in cg. The Markov blanket is the minimal set of nodes that renders node conditionally independent of all other nodes in the graph.

For a DAG, the Markov blanket is the set of parents, children, and co-parents (other parents of node's children). For a AbstractPDAG, undirected neighbors are also included. For an ADMG or AbstractAG, it is parents, children, co-parents, spouses, and (for an AbstractAG) undirected neighbors, plus every node reachable by a collider path (Pellet and Elisseeff, 2008): a path of length >= 2 whose interior nodes are all colliders. For a PAG, the blanket is computed on a underlying MAG.

Examples

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

julia> markov_blanket(dag, :B)
3-element Vector{Symbol}:
 :A
 :C
 :D

julia> markov_blanket(dag, :C)
2-element Vector{Symbol}:
 :B
 :D

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

julia> markov_blanket(mag, :A)
2-element Vector{Symbol}:
 :B
 :C

References

• Pellet and Elisseeff (2008)

districts(cg::Union{ADMG,AbstractAG}) -> Vector{Vector{Symbol}}

Return all districts (c-components) of cg.

A district is a maximal set of nodes connected via bidirected edges. Singleton nodes with no bidirected edges each form their own district.

Examples

julia> admg = ADMG("A --> B, A <-> C, D <-> E");

julia> districts(admg)
3-element Vector{Vector{Symbol}}:
 [:A, :C]
 [:B]
 [:D, :E]

d_separated(cg::Union{DAG,AbstractPDAG}, x, y, z = Symbol[]) -> Bool

Return true iff every node in x is d-separated from every node in y given z in cg. x, y, and z may each be a single Symbol or an AbstractVector{Symbol}.

Two nodes are d-separated given a conditioning set z if every path between them is blocked. A path is blocked if it contains either a non-collider node in z, or a collider node (and all its descendants) not in z.

For DAG: restricts to the ancestor graph of x, y, and z, then runs a Bayes-ball traversal from x (blocked at conditioned non-colliders, passing through conditioned colliders) and checks whether y is reached.

For AbstractPDAG: restricts to the anterior set (nodes reachable via directed parents or undirected edges), then runs the same Bayes-ball traversal treating undirected edges as never forming a collider endpoint.

Examples

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

julia> d_separated(dag, :A, :C)        # chain A --> B --> C is open
false

julia> d_separated(dag, :A, :C, :B) # conditioning on B blocks the chain
true

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

julia> d_separated(coll, :A, :B)         # collider A --> C <-- B: blocked without conditioning
true

julia> d_separated(coll, :A, :B, :C)  # conditioning on collider C opens the path
false

julia> mpdag = MPDAG("A --- B --> C");

julia> d_separated(mpdag, :A, :C, :B) # B blocks whether A --> B or A <-- B
true

julia> d_separated(mpdag, :A, :C)       # B is possibly a non-collider: open path exists
false

julia> chain = DAG("A --> C <-- B, C --> D");

julia> d_separated(chain, [:A, :B], :D)         # C lies on both A-->C-->D and B-->C-->D: paths open
false

julia> d_separated(chain, [:A, :B], :D, :C)  # conditioning on chain node C blocks both paths
true

References

• Lauritzen et al. (1990)
• Hauser and Bühlmann (2012)

m_separated(cg::Union{DAG,ADMG,AbstractAG,PAG}, x, y, z = Symbol[]) -> Bool

Return true iff every node in x is m-separated from every node in y given z in cg. x, y, and z may each be a single Symbol or an AbstractVector{Symbol}.

M-separation generalizes d-separation to graphs with bidirected and undirected edges. For a DAG, m-separation is equivalent to d_separated.

DAG / ADMG: restricts to the ancestor graph of x, y, and z, then runs a Bayes-ball traversal from x treating parents and spouses alike as arrowhead endpoints, and checks whether y is reached.

AbstractAG: same traversal extended with undirected edges, restricted to the anterior set of x, y, and z (Richardson & Spirtes, 2002).

PAG: same traversal as AbstractAG, with circle marks collapsing to tails (as for possible_ancestors/possible_descendants).

Examples

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

julia> m_separated(dag, :A, :C)        # equivalent to d_separated on a DAG
false

julia> m_separated(dag, :A, :C, :B)
true

julia> admg = ADMG("A --> B, A <-> C");

julia> m_separated(admg, :B, :C)        # B and C are connected via the bidirected edge at A
false

julia> m_separated(admg, :B, :C, :A) # conditioning on A blocks the path
true

julia> admg2 = ADMG("A <-> C <-> B");

julia> m_separated(admg2, [:A, :B], :C)  # both A and B are m-connected to C
false

References

• Richardson and Spirtes (2002)

minimal_separator(cg::Union{DAG,ADMG,AbstractAG,PAG,AbstractPDAG}, x, y; include=Symbol[], restrict=nothing)

Find a minimal d-separator (DAG, AbstractPDAG) or m-separator (ADMG, AbstractAG, PAG) between nodes x and y.

A set $Z$ separates $x$ from $y$ if conditioning on $Z$ renders them d/m-independent. The returned set is minimal: no proper subset (excluding forced include nodes) still separates $x$ from $y$.

Returns a Vector{Symbol} of node names, or nothing when no valid separator exists within the allowed candidate set.

Arguments

• cg: A DAG, ADMG, AbstractAG, PAG, or AbstractPDAG.
• x, y: The nodes to separate. Each may be a single Symbol or an AbstractVector{Symbol}, in which case the returned set separates every node in x from every node in y.
• include: Nodes forced into the separator. Must be a subset of restrict (or the default candidate set). May be a single Symbol or an AbstractVector{Symbol}.
• restrict: Candidate pool from which the separator is drawn. Defaults to all nodes except x and y. May be a single Symbol or an AbstractVector{Symbol}.

Algorithm

Implements FINDMINSEP from van der Zander and Liśkiewicz (2020), running in $O(n + m)$ time. FINDNEARESTSEP is called twice; once from x, once from y restricted to the first result, and the outputs are intersected.

• DAG: directional Bayes-ball restricted to ancestors of {x, y} ∪ include.
• ADMG: mark-based Bayes-ball over directed and bidirected edges, restricted to ancestors.
• AbstractAG: same as ADMG but uses anteriors (ancestors reachable via directed or undirected edges) and handles undirected edge marks.
• PAG: same as AbstractAG, with circle marks collapsing to tails (as for possible_ancestors/possible_descendants).
• AbstractPDAG: mark-based Bayes-ball over directed and undirected edges, restricted to anteriors.

Examples

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

julia> minimal_separator(dag, :A, :C)  # chain A --> B --> C: separator is {B}
1-element Vector{Symbol}:
 :B

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

julia> minimal_separator(dag_coll, :A, :B)  # collider A --> C <-- B: already d-separated
Symbol[]

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

julia> minimal_separator(dag_edge, :A, :B) === nothing  # direct edge: no separator exists
true

julia> dag4 = DAG("A --> X --> M --> Y, A --> Y");

julia> minimal_separator(dag4, :X, :Y)  # two paths require both A and M
2-element Vector{Symbol}:
 :A
 :M

julia> minimal_separator(dag4, :X, :Y, include = :M)  # force M in; A still needed
2-element Vector{Symbol}:
 :A
 :M

julia> minimal_separator(dag4, :X, :Y, restrict = :M) === nothing  # M alone cannot block X <-- A --> Y
true

julia> dag5 = DAG("A --> M1 --> Y, B --> M2 --> Y");

julia> minimal_separator(dag5, [:A, :B], :Y)  # both mediators are needed to block both sources
2-element Vector{Symbol}:
 :M1
 :M2

julia> admg = ADMG("A --> B --> C");

julia> minimal_separator(admg, :A, :C)
1-element Vector{Symbol}:
 :B

julia> pag = mag_to_pag(MAG("A --> X --> M --> Y, A --> Y"));

julia> minimal_separator(pag, :A, :M)
1-element Vector{Symbol}:
 :X

julia> mag2 = MAG("A <-> X1, B <-> X2, A --> M1 --> Y, B --> M2 --> Y");

julia> sort(minimal_separator(mag2, [:X1, :X2], :Y))
2-element Vector{Symbol}:
 :A
 :B

References

• van der Zander and Liśkiewicz (2020)

possible_d_sep(cg::AbstractAG, x::Symbol, y::Union{Symbol,AbstractVector{Symbol}}) ->
    Vector{Symbol}

Return D-SEP(x, y, cg): every node V != x for which there is a collider path between x and V in cg on which every node, including V, is an ancestor of x or of some member of y.

D-SEP is the set that backdoor_set (for MAG and PAG) uses as the generalized back-door set (Maathuis & Colombo 2015), computed there on M_X (cg with x's visible edges removed) rather than on cg directly.

Examples

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

julia> possible_d_sep(mag, :X, :Y)
3-element Vector{Symbol}:
 :A
 :M
 :Y

julia> backdoor_set(mag, :X, :Y)  # M_X drops the visible edge X --> Y, excluding M and Y
1-element Vector{Symbol}:
 :A

References

• Maathuis and Colombo (2015)

possible_ancestors(cg::AbstractPDAG, node::Symbol; open::Bool = true) -> Vector{Symbol}

Return the possible ancestors of node in cg: all nodes V for which there exists at least one DAG in the equivalence class represented by cg in which V is an ancestor of node.

V is a possible ancestor of node if there is a b-possibly directed path from V to node (Perković, Kalisch & Maathuis 2017/2018): a path on which no node, however far back, has a directed edge into an earlier node on the path. For CPDAG this reduces to the simpler "no edge compelled away from node" rule (checking only consecutive steps suffices there, Meek 1995, Lemma 1); for MPDAG checking only consecutive steps is unsound, since background knowledge can create partially directed cycles.

When open = true (default), node itself is excluded. When open = false (closed definition), node is included. The default can be changed via Preferences.jl: set_preferences!(CausalStructures, "open" => false).

Examples

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

julia> ancestors(cpdag, :C)
Symbol[]

julia> possible_ancestors(cpdag, :C)
2-element Vector{Symbol}:
 :A
 :B

julia> mpdag = MPDAG("A --- B --- C --- D --- A, D --> B");

julia> :B in possible_ancestors(mpdag, :D)  # B --> ... --> D would create a cycle with D --> B
false

References

• Perković et al. (2018)
• Perković et al. (2017)

possible_ancestors(cg::PAG, node::Symbol; open::Bool = true) -> Vector{Symbol}

Return the possible ancestors of node in cg: all nodes V for which there exists at least one MAG in the equivalence class represented by cg in which V is an ancestor of node.

V is a possible ancestor of node if there is a possibly directed path from V to node: a path where no edge has an arrowhead at the source side of each step. Each step traverses a neighbor whose far-mark (the mark at the neighbor's endpoint) is not an arrowhead: parents (<--), undirected (---), circle-parents (<-o), circle-undirected-out (o--), and circle-circle (o-o) edges all qualify. Spouses (<->), children (-->), and circle-children (o->) are excluded because the far-mark is a fixed arrowhead. Circle-undirected-in (--o) edges are also excluded: the near-mark is an invariant tail, so the neighbor can never be an ancestor of node through that edge in any MAG.

When open = true (default), node itself is excluded. When open = false (closed definition), node is included. The default can be changed via Preferences.jl: set_preferences!(CausalStructures, "open" => false).

Examples

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

julia> sort(possible_ancestors(pag, :B))
2-element Vector{Symbol}:
 :A
 :C

julia> possible_ancestors(pag, :A)
Symbol[]

References

• Perković et al. (2018)

possible_descendants(cg::AbstractPDAG, node::Symbol; open::Bool = true) -> Vector{Symbol}

Return the possible descendants of node in cg: all nodes V for which there exists at least one DAG in the equivalence class represented by cg in which V is a descendant of node.

V is a possible descendant of node if there is a b-possibly directed path from node to V (Perković, Kalisch & Maathuis 2017/2018): a path on which no node, however far along, has a directed edge into an earlier node on the path. For CPDAG this reduces to the simpler "no edge compelled away from node" rule (checking only consecutive steps suffices there, Meek 1995, Lemma 1); for MPDAG checking only consecutive steps is unsound, since background knowledge can create partially directed cycles.

When open = true (default), node itself is excluded. When open = false (closed definition), node is included. The default can be changed via Preferences.jl: set_preferences!(CausalStructures, "open" => false).

Examples

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

julia> descendants(cpdag, :A)
Symbol[]

julia> possible_descendants(cpdag, :A)
2-element Vector{Symbol}:
 :B
 :C

julia> mpdag = MPDAG("A --- B --- C --- D --- A, D --> B");

julia> :D in possible_descendants(mpdag, :B)  # B --> ... --> D would create a cycle with D --> B
false

References

• Perković et al. (2018)
• Perković et al. (2017)

possible_descendants(cg::PAG, node::Symbol; open::Bool = true) -> Vector{Symbol}

Return the possible descendants of node in cg: all nodes V for which there exists at least one MAG in the equivalence class represented by cg in which V is a descendant of node.

V is a possible descendant of node if there is a possibly directed path from node to V: a path where no edge has an arrowhead at the source side of each step. Each step traverses a neighbor where the near-mark at the current node is not an arrowhead: children (-->), undirected (---), circle-children (o->), circle-undirected-in (--o), and circle-circle (o-o) edges all qualify. Parents (<--), spouses (<->), and circle-parents (<-o) are excluded because the near-mark is a fixed arrowhead. Circle-undirected-out (o--) edges are also excluded: the far-mark is an invariant tail, so node can never be an ancestor of the neighbor through that edge in any MAG.

When open = true (default), node itself is excluded. When open = false (closed definition), node is included. The default can be changed via Preferences.jl: set_preferences!(CausalStructures, "open" => false).

Examples

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

julia> possible_descendants(pag, :A)
1-element Vector{Symbol}:
 :B

julia> possible_descendants(pag, :B)
Symbol[]

References

• Perković et al. (2018)

possible_parent_sets(cg::AbstractPDAG, x::Symbol) -> Vector{Vector{Symbol}}

Return the possible parent sets of x implied by cg, using the graph-only half of local IDA (Algorithm 3 of (Maathuis et al., 2009)). For each accepted orientation of the undirected neighbors of x, include pa(x) ∪ S, where S is the subset oriented into x. On MPDAGs, acceptance requires a valid full Meek closure; on CPDAGs, the local v-structure check suffices. This is the xs = [x] special case of possible_joint_parent_sets.

Unlike all_adjustment_sets, returns one entry per accepted subset, not per DAG in the Markov equivalence class.

Examples

julia> cpdag = CPDAG("X1 --- X2 + X3 + X4, X3 + X4 --> Y");

julia> sort(possible_parent_sets(cpdag, :X1); by = length)
4-element Vector{Vector{Symbol}}:
 []
 [:X2]
 [:X3]
 [:X4]

References

• Maathuis et al. (2009)
• Perković et al. (2017)

possible_joint_parent_sets(cg::AbstractPDAG, xs) ->
    Vector{Vector{Vector{Symbol}}}

Return every locally valid joint parental structure of xs implied by cg.

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

This is the graph part of joint-IDA (Nandy et al. (2017)), generalizing possible_parent_sets from a single intervention node to a set of simultaneous interventions.

Every undirected edge incident to at least one node in xs is jointly reoriented, including edges directly between two nodes of xs. A candidate orientation is accepted if it introduces no new v-structure at any node that gains a parent from it (not only at nodes in xs: two non-adjacent members of xs directing an edge into the same outside neighbor is also a new v-structure), and if the result extends to a DAG represented by cg.

Each returned entry is a vector of parent sets in the same order as xs (entry i is a valid pa(xs[i]) for that joint orientation). Since a node xs[j] can appear in the parent set of xs[i], comparing entries pairwise recovers a valid causal ordering among xs for that orientation (the ordering downstream recursive-regression methods like RRC or MCD need); nodes of xs with no directed relation between them in a given entry are left unordered by that orientation, as either relative order is valid.

Examples

julia> cpdag = CPDAG("X1 --- X2, X1 --- A, X2 --- B, A --> Y, B --> Y");

julia> for pa in possible_joint_parent_sets(cpdag, [:X1, :X2])
           println(pa)
       end
[[:X2], [:B]]
[[:A], [:X1]]
[Symbol[], [:X1]]
[[:X2], Symbol[]]

Four of the eight ways to jointly orient the three edges touching {X1, X2} survive: e.g. A --> X1 --> X2 <-- B is rejected because it creates a new v-structure at X2 between the non-adjacent X1 and B, even though neither endpoint of that collision is in xs.

References

• Maathuis et al. (2009)
• Nandy et al. (2017)

possible_local_structures(cg::PAG, x::Symbol) -> Vector{Vector{Symbol}}

Return every valid local structure at x in cg (Proposition 2 of Wang et al. (2023)).

Each entry is a subset C of x's circle-marked neighbors for which a MAG consistent with cg exists with x <-> v for every v in C and x --> v for every other circle-marked neighbor. This is the graph-only ingredient PAGcauses (Wang et al. (2025)) enumerates local structures with; pair an entry with maximal_local_mag to get the corresponding graph.

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

References

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

is_dag(cg::CausalGraph)   -> Bool

Check whether cg satisfies the structural constraints of a DAG (directed acyclic graph), independent of its declared graph class.

Examples

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

julia> is_dag(pdag)
true

is_pdag(cg::CausalGraph) -> Bool

Check whether cg satisfies the structural constraints of a PDAG (partially directed acyclic graph), independent of its declared graph class.

Examples

julia> unk = UNKNOWN("A --> B --- C");

julia> is_pdag(unk)
true

is_cpdag(cg::CausalGraph) -> Bool

Check whether cg satisfies the structural constraints of a CPDAG (completed partially directed acyclic graph), independent of its declared graph class.

Examples

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

julia> is_cpdag(dag)
false

is_mpdag(cg::CausalGraph) -> Bool

Check whether cg satisfies the structural constraints of a MPDAG (maximally oriented partially directed acyclic graph), independent of its declared graph class.

Examples

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

julia> is_mpdag(dag)
true

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

julia> is_mpdag(pdag)
false

is_ug(cg::CausalGraph) -> Bool

Check whether cg satisfies the structural constraints of a UG (undirected graph), independent of its declared graph class.

Examples

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

julia> is_ug(pdag)
true

is_admg(cg::CausalGraph) -> Bool

Check whether cg satisfies the structural constraints of a ADMG (acyclic directed mixed graph), independent of its declared graph class.

Examples

julia> pdag = UNKNOWN("A <-> B");

julia> is_admg(pdag)
true

is_ag(cg::CausalGraph) -> Bool

Check whether cg satisfies the structural constraints of a AG (ancestral graph), independent of its declared graph class.

Examples

julia> pdag = UNKNOWN("A <-> B");

julia> is_ag(pdag)
true

is_mag(cg::CausalGraph) -> Bool

Check whether cg satisfies the structural constraints of a MAG (maximal ancestral graph), independent of its declared graph class.

Examples

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

julia> is_mag(ag)
true

julia> ag = AG("Z <-> X <-> Y, Z <-> W, X --> W, Z --> Y");

julia> is_mag(ag)
false

is_pag(cg::CausalGraph) -> Bool

Check whether cg is a valid PAG (partial ancestral graph): the marks are the invariant marks of the Markov equivalence class of some MAG, independent of cg's declared graph class. Verified by resolving cg to a MAG with mag_from_pag and checking that mag_to_pag recovers cg.

Examples

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

julia> is_pag(pag)
true

julia> is_pag(UNKNOWN("A --> B"))
false

is_simple(cg::CausalGraph) -> Bool

Return true if cg has no self-loops and no parallel edges between the same pair of nodes.

For all graph classes except UNKNOWN, simplicity is guaranteed by construction.

Examples

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

julia> is_simple(dag)
true

julia> unk = UNKNOWN("A --> B, A --> B");

julia> is_simple(unk)
false

is_acyclic(cg::CausalGraph) -> Bool

Return true if cg contains no directed cycle.

For all graph classes except UNKNOWN, acyclicity is guaranteed by construction.

Examples

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

julia> is_acyclic(dag)
true

julia> unk = UNKNOWN("A --> B, B --> A");

julia> is_acyclic(unk)
false

markov_equivalent(cg1::DAG, cg2::DAG) -> Bool

Return true if cg1 and cg2 belong to the same Markov equivalence class (MEC), i.e. they encode exactly the same conditional independences.

Two DAGs are Markov equivalent if and only if they share the same skeleton (undirected adjacency structure) and the same set of v-structures (unshielded colliders a –> b <– c with a,c non-adjacent). This is the Verma-Pearl characterization (Verma & Pearl, 1990).

Examples

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

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

julia> markov_equivalent(cg1, cg2)
true

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

julia> markov_equivalent(cg1, cg3)
false

References

• Verma and Pearl (1990)

markov_equivalent(cg1::MAG, cg2::MAG) -> Bool

Return true if cg1 and cg2 belong to the same Markov equivalence class, i.e. they impose the same m-separation constraints.

Examples

A <-> B <-> C and A --> B <-- C both have an unshielded collider at B, so they share the PAG A o-> B <-o C and are Markov equivalent. Replacing the B <-> C edge with B --> C removes that collider, changing the equivalence class:

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

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

julia> markov_equivalent(m1, m2)
true

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

julia> markov_equivalent(m1, m3)
false

References

• Ali et al. (2009)