# Library

## (Partially) directed acyclic graphs (PDAGs and DAGs)

CausalInference.has_a_pathFunction
has_a_path(g::AbstractGraph, U::Vector, V::VectorOrVertex, exclude_vertices::AbstractVector = T[], nbs=Graphs.outneighbors)

Find if there is a (semi-directed) path connecting U with V not passing exclude_vertices, where nbs=Graphs.outneighbors determines the direction of traversal.

CausalInference.iscliqueFunction
isclique(g, nodes)

Return true if all vertices in nodes are adjacent to each other in the graph g. Chickering, "Learning equivalence classes" (2002). Note that a 3-clique with already two undirected edges is also a clique in the neighbor sense.

CausalInference.parentsFunction
parents(g, x)

Parents are vertices y such that there is a directed edge y –> x. Returns sorted array.

CausalInference.childrenFunction
children(g, x)

Children of x in g are vertices y such that there is a directed edge y <– x. Returns sorted array.

CausalInference.isundirectedFunction
isundirected(g, edge::Edge)
isundirected(g, x, y)

Test if x and y are connected by a undirected edge in the graph g.

CausalInference.isorientedFunction
isoriented(g, edge::Edge)
isoriented(g, x, y)

Test if x and y are connected by a directed edge in the graph g, either x←y OR x→y. Can also perform the same test given an edge.

Test if x and y are connected by a any edge in the graph g (i.e. x –- y, x –> y, or x <– y .)

## Causal graphs

CausalInference.dsepFunction
dsep(g::AbstractGraph, u, v, s; verbose = false)

Check whether u and v are d-separated given set s. Algorithm: unrolled https://arxiv.org/abs/1304.1505

CausalInference.cpdagFunction
cpdag(skel::DiGraph)

Computes CPDAG from a DAG using Chickering's conversion algorithm (equivalent to the PC algorithm with d-seperation as independence test, see pc_oracle.)

Reference: M. Chickering: Learning equivalence classes of Bayesian network structures. Journal of Machine Learning Research 2 (2002). M. Chickering: A Transformational Characterization of Equivalent Bayesian Network Structures. (1995).

Note that the edge order defined there is already partly encoded into the representation of a DiGraph.

CausalInference.alt_cpdagFunction
alt_cpdag(g::DiGraph)

Computes CPDAG from a DAG using a simpler adaption of Chickering's conversion algorithm without ordering all edges (equivalent to the PC algorithm with d-separation as independence test, see pc_oracle.)

Reference: M. Chickering: Learning equivalence classes of Bayesian network structures. Journal of Machine Learning Research 2 (2002). M. Chickering: A Transformational Characterization of Equivalent Bayesian Network Structures. (1995).

CausalInference.has_recanting_witnessFunction
has_recanting_witness(g::AbstractGraph, u, v,  blocked_edges::AbstractGraph) -> Bool

In a causal DAG with edges g, determine whether path-specific causal effect from vertex u to v with edges in blocked_edges blocked can be can be computed uniquely from the data available to the investigator (assuming complete observations), which is the case if there is no "recanting witness". Essentially this means that blocked_edges could equivalently be replaced by a blocking only outgoing edges of u.

See Alvin, Shpitser, Pearl (2005): "Identifiability of Path-Specific Effects", https://ftp.cs.ucla.edu/pub/stat_ser/r321-L.pdf.

CausalInference.backdoor_criterionFunction
backdoor_criterion(g::AbstractGraph, u::Integer, v::Integer, Z; verbose = false)

Test that given directed graph g, no node in Z is descendant of u and Z d-separates u from v in the subgraph that only has the backdoors of u left (outgoing edges of u removed).

If so, the causal effect of u on v is identifiable and is given by the formula:

∑{z∈Z} p(v | u, z)p(z)

In the linear Gaussian model, find E[Y | X = x, Z = z] = α + βx + γ'z and obtain E[Y | do(x)] = α + βx + γ'E[Z].

CausalInference.meek_rules!Function
meek_rules!(g; rule4=false)

Apply Meek's rules 1-3 or 1-4 with rule4=true to orient edges in a partially directed graph without creating cycles or new v-structures. Rule 4 is needed if edges are compelled/preoriented using external knowledge.

CausalInference.meek_rule1Function
meek_rule1(g, v, w)

Rule 1: Orient v-w into v->w whenever there is u->v such that u and w are not adjacent (otherwise a new v-structure is created.)

CausalInference.meek_rule2Function
meek_rule2(g, v, w)

Rule 2: Orient v-w into v->w whenever there is a chain v->k->w (otherwise a directed cycle is created.)

CausalInference.meek_rule3Function
meek_rule3(g, v, w)

Rule 3 (Diagonal): Orient v-w into v->w whenever there are two chains v-k->w and v-l->w such that k and l are nonadjacent (otherwise a new v-structure or a directed cycle is created.)

CausalInference.meek_rule4Function
meek_rule4(g, v, w)

Rule 4: Orient v-w into v→w if v-k→l→w where adj(v,l) and not adj(k,w) [check].

## PC algorithm

CausalInference.pcalgFunction
pcalg(n::V, I, par...; stable=true)
pcalg(g, I, par...; stable=true)

Perform the PC algorithm for a set of 1:n variables using the tests

I(u, v, [s1, ..., sn], par...)

Returns the CPDAG as DiGraph. By default uses a stable and threaded versions of the skeleton algorithm.

pcalg(t, p::Float64, test::typeof(gausscitest); kwargs...)

Run PC algorithm for tabular input data t using a p-value p to test for conditional independeces using Fisher's z-transformation.

pcalg(t::T, p::Float64; cmitest::typeof(cmitest); kwargs...) where{T}

Run PC algorithm for tabular input data t using a p-value p to detect conditional independeces using a conditional mutual information permutation test.

CausalInference.orient_unshieldedFunction
orient_unshielded(g, dg, S)

Orient unshielded triples using the separating sets. g is an undirected graph containing edges of unknown direction, dg is an directed graph containing edges of known direction and both v=>w and w=>vif the direction of Edge(v,w)is unknown.S are the separating sets of edges.

Returns g, dg.

CausalInference.apply_pc_rulesFunction
apply_pc_rules(g, dg)

g is an undirected graph containing edges of unknown direction, dg is an directed graph containing edges of known direction and both v=>w and w=>vif the direction of Edge(v,w) is unknown.

Returns the CPDAG as DiGraph.

CausalInference.skeletonFunction
skeleton(n::Integer, I) -> g, S
skeleton(g, I) -> g, S

Perform the undirected PC skeleton algorithm for a set of 1:n variables using the test I. Start with a subgraph g or the complete undirected graph on n vertices. Returns skeleton graph and separating set.

CausalInference.skeleton_stableFunction
skeleton_stable(n::Integer, I) -> g, S
skeleton_stable(g, I) -> g, S

Perform the undirected stable PC skeleton algorithm for a set of 1:n variables using the test I. Start with a subgraph g or the complete undirected graph on n vertices. Returns skeleton graph and separating set.

CausalInference.unshieldedFunction
unshielded(g)

Find the unshielded triples in the cyclefree skeleton. Triples are connected vertices v-w-z where z is not a neighbour of v. Uses that edges iterates in lexicographical order.

CausalInference.orientable_unshieldedFunction
orientable_unshielded(g, S)

Find the orientable unshielded triples in the skeleton. Triples are connected vertices v-w-z where z is not a neighbour of v. Uses that edges iterates in lexicographical order.

CausalInference.plot_pc_graph_tikzFunction
CausalInference.plot_pc_graph_tikz(g, node_labels::AbstractVector{<:AbstractString}=String[])

Plot the output of the PC algorithm (TikzGraphs backend).

Requires TikzGraphs to be imported

CausalInference.plot_pc_graph_recipesFunction
plot_pc_graph_recipes(g, node_labels::AbstractVector{<:AbstractString}=String[])

Plot the output of the PC algorithm (GraphRecipes backend).

Requires GraphRecipes and Plots to be imported

CausalInference.plot_pc_graph_textFunction
plot_pc_graph_text(g::AbstractGraph, node_labels::AbstractVector{<:AbstractString}=String[])

Plot the output of the PC algorithm (text-based output).

See also: plot_pc_graph and plot_pc_graph_tikz (for TikzGraphs.jl-based plotting), plot_pc_graph_recipes (for GraphRecipes.jl-based plotting)

CausalInference.prepare_pc_graphFunction
prepare_pc_graph(g::AbstractGraph, node_labels::AbstractVector{<:AbstractString}=String[])

Prepare resulting graph for plotting with various backends.

## Statistics

CausalInference.gausscitestFunction
gausscitest(i, j, s, (C,n), c)

Test for conditional independence of variable no i and j given variables in s with Gaussian test at the critical value c. C is covariance of n observations.

CausalInference.partialcorFunction
partialcor(i, j, s, C)

Compute the partial correlation of nodes i and j given list of nodes s using the correlation matrix C.

CausalInference.cmitestFunction
cmitest(i,j,s,data,crit; kwargs...)

Test for conditional independence of variables i and j given variables in s with permutation test using nearest neighbor conditional mutual information estimates at p-value crit.

keyword arguments: kwargs...: keyword arguments passed to independence tests

## KL Entropy Estimators

CausalInference.kl_entropyFunction
kl_entropy(data::Array{Float64, 2}; k=5)

Compute the nearest-neighbor estimate of the differential entropy of data.

data is a 2d array, with every column representing one data point. For further information, see

"A class of Rényi information estimators for multidimensional densities" Nikolai Leonenko, Luc Pronzato, and Vippal Savani The Annals of Statistics, 2008 https://projecteuclid.org/euclid.aos/1223908088

keyword arguments: k=5: number of nearest neighbors

CausalInference.kl_renyiFunction
kl_renyi(data::Array{Float64, 2}, q; k=5)

Compute the nearest-neighbor estimate of the Renyi-alpha entropy of data.

data is a 2d array, with every column representing one data point. For further information, see

"A class of Rényi information estimators for multidimensional densities" Nikolai Leonenko, Luc Pronzato, and Vippal Savani The Annals of Statistics, 2008 https://projecteuclid.org/euclid.aos/1223908088

keyword arguments: k=5: number of nearest neighbors

CausalInference.kl_mutual_informationFunction
kl_mutual_information(x, y; k=5, bias_correction=true)

compute the nearest-neighbor 'KGS' estimate of the mutual information between x and y.

x and y are 2d arrays, with every column representing one data point. For further information, see

"Estimating Mutual Information" Alexander Kraskov, Harald Stoegbauer, and Peter Grassberger Physical Review E https://arxiv.org/pdf/cond-mat/0305641.pdf

"Demystifying Fixed k-Nearest Neighbor Information Estimators" Weihao Gao, Sewoong Oh, Pramod Viswanath EEE International Symposium on Information Theory - Proceedings https://arxiv.org/pdf/1604.03006.pdf

keyword arguments: k=5: number of nearest neighbors bias_correction=true: flag to apply Gao's bias correction

CausalInference.kl_cond_miFunction
kl_cond_mi(x, y, z; k=5, bias_correction=true)

compute the nearest-neighbor 'KGS' estimate of the conditional mutual information between x and y given z.

x, y, and z are 2d arrays, with every column representing one data point. keyword arguments: k=5: number of nearest neighbors bias_correction=true: flag to apply Gao's bias correction

CausalInference.kl_perm_mi_testFunction
kl_perm_mi_test(x, y; k=5, B=100, bias_correction=true)

compute permutation test of independence of x and y.

keyword arguments: k=5: number of nearest neighbors to use for mutual information estimate B=100: number of permutations bias_correction=true: flag to apply Gao's bias correction

CausalInference.kl_perm_cond_mi_testFunction
kl_perm_cond_mi_test(x, y, z; k=5, B=100, kp=5, bias_correction=true)

compute permutation test of conditional independence of x and y given z.

For further information, see: "Conditional independence testing based on a nearest-neighbor estimator of conditional mutual information" Jakob Runge Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS) 2018, Lanzarote, Spain. http://proceedings.mlr.press/v84/runge18a/runge18a.pdf

keyword arguments: k=5: number of nearest neighbors to use for mutual information estimate B=100: number of permutations bias_correction=true: flag to apply Gao's bias correction

## FCI algorithm

CausalInference.has_marksFunction
has_marks(dg, v1, v2, t::Tuple{Symbol, Symbol}

Test if the edge between node v1 and v2 has the edge markers given by the tuple t (use the arrow macro to simplify use)

Example: has_marks(dg, 1, 2, arrow"o->")

CausalInference.set_marks!Function
set_marks!(dg, v1, v2, t::Tuple{Symbol, Symbol})

Set edge marks between node v1 and v2.

Example: set_marks!(dg, 1, 2, arrow"*->")

CausalInference.fcialgFunction
fcialg(n::V, I, par...; augmented=true, verbose=false, kwargs...)

Perform the FCI algorithm for a set of n variables using the test

I(u, v, [s1, ..., sn], par...)

Returns the PAG as a MetaDiGraph

CausalInference.plot_fci_graph_tikzFunction
plot_fci_graph_tikz(g, node_labels::AbstractVector{<:AbstractString}=String[])

Plot the output of the FCI algorithm (TikzGraphs backend).

Requires TikzGraphs to be imported

CausalInference.plot_fci_graph_recipesFunction
plot_fci_graph_recipes(g, node_labels::AbstractVector{<:AbstractString}=String[])

Plot the output of the FCI algorithm (GraphRecipes backend).

Requires GraphRecipes and Plots to be imported

CausalInference.plot_fci_graph_textFunction
plot_fci_graph_text(g::AbstractGraph, node_labels::AbstractVector{<:AbstractString}=String[])

Plot the output of the FCI algorithm (text-based output).

See also: plot_fci_graph and plot_fci_graph_tikz (for TikzGraphs.jl-based plotting), plot_fci_graph_recipes (for GraphRecipes.jl-based plotting)

CausalInference.prepare_fci_graphFunction
prepare_fci_graph(g::AbstractGraph, node_labels::AbstractVector{<:AbstractString}=String[])

Prepare the output of the FCI algorithm for plotting with various backends.

## Miscellaneous

CausalInference.pc_oracleFunction
pc_oracle(g; stable=true)

Compute CPDAG using the PC algorithm using the dseporacle on the DAG g.

CausalInference.randdagFunction
randdag(n, alpha = 0.1)

Create Erdős–Rényi random DAG from randomly permuted random triangular matrix with edge probability alpha.

CausalInference.disjoint_sortedFunction
disjoint_sorted(u, v)

Check if the intersection of sorted collections is empty. The intersection of empty collectios is empty.

CausalInference.ordered_edgesFunction
ordered_edges(dag)

Iterator of edges of a dag, ordered in Chickering order:

Perform a topological sort on the NODES
while there are unordered EDGES in g
Let y be the lowest ordered NODE that has an unordered EDGE incident into it
Let x be the highest ordered NODE for which x => y is not ordered
return x => y
end
CausalInference.graph_to_textFunction
graph_to_text(g::AbstractGraph, node_labels::AbstractVector{<:AbstractString}=[]; edge_styles::AbstractDict=Dict())

Print out a graph g as a table of edges labeled by node_labels.

Arguments

• g::AbstractGraph: a graph to print
• node_labels::AbstractVector{<:AbstractString}=[]: labels for nodes (same order as indices of nodes in g)
• edge_styles::AbstractDict=Dict(): dictionary of edge styles (e.g. Dict((1, 2) => "->", (2, 3) => "<->"))

Example

g = DiGraph(4)
for (i, j) in [(1, 2), (2, 3), (2, 4)]
end
graph_to_text(g)
CausalInference.kwargs_pdag_graphmakieFunction
kwargs_pdag_graphmakie(g; ilabels=1:nv(g), arrowsize=25, ilabels_fontsize=25)

Generates the keywords for GraphMakie.graphplot to plot causal graphs and (C)PDAGs represented as SimpleDiGraph as partially directed graphs.

Usage:

graphplot(g; kwargs_pdag_graphmakie(g)...)
CausalInference.combinations_withoutFunction
combinations_without(a, n::Integer, w)

Generate all combinations of n elements from an indexable object except those with index w. Note that the combinations are modified inplace.

## Bayes ball

CausalInference.bayesballFunction
bayesball(g, X, S = Set{eltype(g)}())

Return the set of vertices d-connected to the set of vertices X given set of vertices S in dag g.

CausalInference.bayesball_graphFunction
bayesball_graph(g, X, S = Set{eltype(g)}(); back=false)

Return an mixed graph b containing edges for possible moves of the Bayes ball. Vertex x of g is vertex "x forward" at 2x-1 of b if entered forward and "x backward" at 2x if entered backward. y is d-connected to x given S if and only if there is a semi-directed path in b from "x backward" to "y forward" or "y backward"). back=true allows path through X

CausalInference.ancestorsFunction
ancestors(g, X, veto = no_veto)

Return the set of ancestors of the set of vertices X in graph g.

Every vertex is an ancestor of itself.

CausalInference.descendantsFunction
descendants(g, X, veto = no_veto)

Return the set of descendants of the set of vertices X in graph g.

Every vertex is a descendant of itself.

CausalInference.alt_test_dsepFunction
alt_test_dsep(g, X, Y, S, veto = no_veto)

Check if sets of vertices X and Y are d-separated in g given S.

An alternative to the test_dsep function, which uses gensearch under the hood. Might be (a bit) slower.

Check if S is a covariate adjustment set relative to (X, Y) in graph g.

Based on the sound and complete graphical criterion for covariate adjustment given in https://arxiv.org/abs/1203.3515 using the algorithmic approach proposed in https://arxiv.org/abs/1803.00116. Output is a boolean.

CausalInference.alt_test_backdoorFunction
alt_test_backdoor(g, X, Y, S)

Check if S satisfies the backdoor criterion relative to (X, Y) in graph g.

The generalization to sets X and Y differs from, e.g., Pearl (2009). See the Example section (TODO: ref).

CausalInference.find_dsepFunction
find_dsep(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y), veto = no_veto)

Find a d-separator Z with $I ⊆ Z ⊆ R$ for sets of vertices X and Y in g, else return false.

Based on the algorithmic approach proposed in https://arxiv.org/abs/1803.00116.

CausalInference.find_min_dsepFunction
find_min_dsep(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y), veto = no_veto)

Find an inclusion minimal d-separator Z with $I ⊆ Z ⊆ R$ for sets of vertices X and Y in g, i.e., one for which no subset is a d-separator, else return false.

Based on the algorithmic approach proposed in http://auai.org/uai2019/proceedings/papers/222.pdf.

find_covariate_adjustment(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y))

Find a covariate adjustment set Z with $I ⊆ Z ⊆ R$ for sets of vertices X and Y in g, else return false.

Based on the algorithmic approach proposed in https://arxiv.org/abs/1803.00116.

find_backdoor_adjustment(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y))

Find a backdoor adjustment set Z with $I ⊆ Z ⊆ R$ for sets of vertices X and Y in g, else return false.

The generalization to sets X and Y differs from, e.g., Pearl (2009). See the Example section (TODO: ref).

find_frontdoor_adjustment(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y))

Find a frontdoor adjustment set Z with $I ⊆ Z ⊆ R$ for sets of vertices X and Y in g, else return false.

Based on the algorithm given in https://arxiv.org/abs/2211.16468.

find_min_covariate_adjustment(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y))

Find an inclusion minimal covariate adjustment set Z with $I ⊆ Z ⊆ R$ for sets of vertices X and Y in g, else return false.

Based on the algorithmic approach proposed in https://arxiv.org/abs/1803.00116.

find_min_backdoor_adjustment(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y))

Find an inclusion minimal backdoor adjustment set Z with $I ⊆ Z ⊆ R$ for sets of vertices X and Y in g, else return false.

The generalization to sets X and Y differs from, e.g., Pearl (2009). See the Example section (TODO: ref).

find_min_frontdoor_adjustment(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y))

Find an inclusion minimal frontdoor adjustment set Z with $I ⊆ Z ⊆ R$ for sets of vertices X and Y in g, else returns false.

Based on the algorithm given in https://arxiv.org/abs/2211.16468.

CausalInference.list_dsepsFunction
list_dseps(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y))

List all d-separators Z with $I ⊆ Z ⊆ R$ for sets of vertices X and Y in g.

list_covariate_adjustment(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y))

List all covariate adjustment sets Z with $I ⊆ Z ⊆ R$ for sets of vertices X and Y in g.

list_backdoor_adjustment(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y))

List all back-door adjustment sets Z with $I ⊆ Z ⊆ R$ for sets of vertices X and Y in g.

list_frontdoor_adjustment(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y))

List all front-door adjustment sets Z with $I ⊆ Z ⊆ R$ for sets of vertices X and Y in g.

## GES

CausalInference.gesFunction
ges(X; method=:gaussian_bic, penalty=0.5, parallel=false, verbose=false)

Compute a causal graph for the given observed data X (variables in columns) using GES. Returns the CPDAG, the score improvement relative to the empty graph and time measurements of first and second phase.

ges(n, local_score; score=0.0, parallel=false, verbose=false)

Internal method called by ges.

CausalInference.local_scoreFunction
local_score(os::GaussianScore, p, v)

Local Gaussian BIC score. Memoized for GaussianScore{Float64, Symmetric{Float64, Matrix{Float64}}}.

CausalInference.Insert!Function
Insert!(g, x, y, T)

Inserts x->y and directs previously undirected edges t->y, t ∈ T. Here x and y are not adjacent and T are undirected-neighbors of y that are not adjacent to x.

CausalInference.Delete!Function
Delete!(g, x, y, H)

Deletes x-y or x->y and directs previously undirected edges x->h and y->h for h in H.

## Causal Zig-Zag

CausalInference.nupFunction
nup(g, total)

Number of directed edges that can be add to a PDAG g with total number of edges.

CausalInference.ndownFunction
ndown(g, total)

Number of edges that can be removed from a pdag counting undirected edges twice.

CausalInference.count_moves_uniformFunction
count_moves_uniform(g, κ=nv(g) - 1) = s1, s2, (x1, y1, T1), (x2, y2, H2)

Counts and samples operator in polynomial-time by avoiding full enumeration (only works for uniform score.) Count the number s1 of Insert and s2 of Delete operators for CPDAG g with degree bound κ and return a uniformly selected Insert(x1, y1, T1)and a uniform selectedDelete(x2, y2, H2) operator.

CausalInference.causalzigzagFunction
causalzigzag(n, G = (DiGraph(n), 0); balance = metropolis_balance, prior = (_,_)->1.0, score=UniformScore(),
coldness = 1.0, σ = 0.0, ρ = 1.0, naive=false,
κ = min(n - 1, 10), iterations=10, verbose=false, save=true)

Run the causal zigzag algorithm starting in a cpdag (G, t) with t oriented or unoriented edges, the balance function balance ∈ {metropolis_balance, barker_balance, sqrt}, score function (see ges algorithm) coldness parameter for iterations. σ = 1.0, ρ = 0.0 gives purely diffusive behaviour, σ = 0.0, ρ = 1.0 gives Zig-Zag behaviour.

Returns a vector of tuples with information, each containing a graph, spent time, current direction, number of edges and the score.

CausalInference.keyedreduceFunction
keyedreduce(op, key::AbstractVector{T}, a, init=0.0) where T

Similar to countmap returning a dictionary mapping unique key in key to the reduction the given collection itr with the given binary operator op.

julia> keyedreduce(+, [:a, :b, :a], [7, 3, 2])
Dict{Symbol, Float64} with 2 entries:
:a => 9.0
:b => 3.0
CausalInference.ne_totalFunction
ne_total(g)

Number of directed or undirected edges in a PDAG represented as DiGraph.

CausalInference.operator_mcsFunction
operator_mcs(G, K)

Perform a Maximum Cardinality Search on graph G. The elements of clique K are of prioritized and chosen first.

CausalInference.precompute_semidirectedFunction
precompute_semidirected(g, y)

Computes for vertex y all vertices reachable via semidirected path from any undirected neighbor and y itself with all vertices in this same set blocked.

CausalInference.next_CPDAGFunction
next_CPDAG(g, op, x, y, S)

next_CDPAG applies an operator and computes the resulting CPDAG in linear-time

## DAG Zig-Zag

CausalInference.dagzigzagFunction
dagzigzag(n, G = DiGraph(n); balance = metropolis_balance, prior = (_,_)->1.0, score=UniformScore(),
coldness = 1.0, σ = 0.0, ρ = 1.0,
κ = min(n - 1, 10), iterations=10, verbose=false, save=true)

Run the causal zigzag algorithm starting in a dag G the balance function balance ∈ {metropolis_balance, barker_balance, sqrt}, score function (see ges algorithm) coldness parameter for iterations. σ = 1.0, ρ = 0.0 gives purely diffusive behaviour, σ = 0.0, ρ = 1.0 gives Zig-Zag behaviour.

Returns a vector of tuples with information, each containing a graph, spent time, current direction, number of edges and the score.

## Exact

CausalInference.exactscorebasedFunction
exactscorebased(X; method=:gaussian_bic, penalty=0.5, parallel=false, verbose=false)

Compute a CPDAG for the given observed data X (variables in columns) using the exact algorithm proposed by Silander and Myllymäki (2006) for optimizing the BIC score (or any decomposable score). The complexity is n*2^n and the algorithm should scale up to ~20-25 variables, afterwards memory becomes a problem.

• Silander, T., & Myllymäki, P. (2006). A simple approach for finding the globally optimal Bayesian network structure. In Uncertainty in Artificial Intelligence (pp. 445-452).