Enumerate all DAGs in a Markov equivalence class

Given a PDAG, enumerate every Directed Acyclic Graph (DAG) in its Markov equivalence class – i.e. every acyclic orientation of the undirected edges that introduces no new v-structures.

Usage

enumerate_dags(cg)

Arguments

cg

A caugi object of class "PDAG" or "MPDAG".

Value

A list of caugi objects of class "DAG", one per DAG in the MEC.

Details

Implements the recursive listing algorithm of Chickering (2002). The input is normalized via meek_closure() so any background-knowledge orientations are preserved and propagated before enumeration. The number of returned DAGs can grow super-exponentially in the size of the chain components; use count_dags() first to size the problem.

References

Chickering, D. M. (2002). "Learning Equivalence Classes of Bayesian-Network Structures". Journal of Machine Learning Research, 2:445–498.

See also

Other operations: condition_marginalize(), count_dags(), dag_from_pdag(), exogenize(), latent_project(), meek_closure(), moralize(), mutate_caugi(), normalize_latent_structure(), skeleton()

Examples

pdag <- caugi(
  A %---% B,
  B %---% C,
  class = "PDAG"
)
dags <- enumerate_dags(pdag)
length(dags) # 3
#> [1] 3