Library

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.

graph(E)

Create Graph from edge-list.

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.

parents(g, x)

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

children(g, x)

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

isundirected(g, edge::Edge)
isundirected(g, x, y)

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

isparent(g, x, y)

Test if x is a parent of y in the graph g, meaning x→y.

neighbors_undirected(g, x)

All vertices in g connected to x by an undirected edge. Returns sorted array.

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.

orientedge!(g, x, y)

Update the edge x-y to x→y in the graph g. Throws error if not x - y

neighbors_adjacent(g, x)

All vertices in g connected to x by an any edge. Returns sorted array.

isadjacent(g, x, y)

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

ischild(g, x, y)

Test if x is a child of y in the graph g, meaning x←y.

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

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.

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

vskel(g)

Reduce a (P)DAG to skeleton and v-structures.

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.

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

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.

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

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

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

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

Deprecated alias for pdag_to_dag_meek!.

pdag_to_dag_dortarsi!(g)

Complete PDAG to DAG using Dor & Tarsi (1992).

pdag_to_dag_meek!(g, rule4=false)

Complete PDAG to DAG using meek_rules.

" do!(g, v)

Graphical do operator, removes all incoming edges to vertex v in a DiGraph g. Returns the modified graph.

pcalg(g, I; stable=true)

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

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

Use IClosure(I, args) to wrap a function f with signature

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

Returns the CPDAG as DiGraph. By default uses a stable and threaded versions of the skeleton algorithm. (This is the most recent interface)

pcalg(n::V, 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.

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.

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.

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.

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.

dseporacle(i, j, s, g)

Oracle for the skeleton and pcalg functions using dsep on the true graph g

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.

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_tikz(g, node_labels::AbstractVector{<:AbstractString}=String[])

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

Requires TikzGraphs to be imported

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

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)

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

Prepare resulting graph for plotting with various backends.

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.

partialcor(i, j, s, C)

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

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

n_ball(n::Number)

Computes the volume of a n-dimensional unit sphere.

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

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

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

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

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

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

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

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

Set edge marks between node v1 and v2.

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

is_collider(dg, v1, v2, v3)

Check if egde v1, v2 and v3 form a collider.

is_parent(dg, v1, v2)

Check if v1 is a parent of v2.

is_triangle(dg, v1, v2, v3)

Check if v1, v2 and v3 form a triangle.

is_discriminating_path(dg, path)

Check if path is a discriminating path.

is_uncovered_circle_path(dg, path)

Check if path is an uncovered circle path.

is_uncovered_PD_path(dg, path)

Check if path is an uncovered potentially directed path.

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

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

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

Requires TikzGraphs to be imported

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

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)

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

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

digraph(E)

Create DiGraph from edge-list.

arrows(g)

Return the edge-list as Pairs.

pc_oracle(g; stable=true)

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

skel_oracle(g; stable=true)

Compute the skeleton using the dseporacle for the DAG g.

randdag(n, alpha = 0.1)

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

disjoint_sorted(u, v)

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

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

removesorted(collection, item) -> contains(collection, item)

Remove item from sorted collection.

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)]
    add_edge!(g, i, j)
end
graph_to_text(g)

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

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.

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.

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

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.

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.

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.

test_covariate_adjustment(g, X, Y, S)

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.

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

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.

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.

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

local_score(os::GaussianScore, p, v)

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

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.

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.

nup(g, total)

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

ndown(g, total)

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

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.

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.

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

ne_total(g)

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

arrows(g)

Return the edge-list as Pairs.

remove!(dg::DiGraph, x => y)

Removes directed edge.

count_moves(g, κ, balance, prior, score, coldness, dir=:both)

Return

ne_undirected(g)

Number of undirected edges in a PDAG represented as DiGraph.

operator_mcs(G, K)

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

InsertIterator{T<:Integer}

Lists all insert operators for pair x,y (needs semidirected from prev point)

DeleteIterator{T<:Integer}

Lists all delete operators for pair x,y.

count_mcs(G)

Perform a Maximum Cardinality Search on graph G.

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.

next_CPDAG(g, op, x, y, S)

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

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.

count_dag_moves(g, κ, balance, prior, score, coldness, dir=:both)

Return

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