Nothing
# ──────────────────────────────────────────────────────────────────────────────
# ──────────────────────────────── Operations ──────────────────────────────────
# ──────────────────────────────────────────────────────────────────────────────
#' @title Moralize a DAG
#'
#' @description
#' Moralizing a DAG involves connecting all parents of each node and then
#' converting all directed edges into undirected edges.
#'
#' @details
#' This changes the graph from a Directed Acyclic Graph (DAG) to an
#' Undirected Graph (UG), also known as a Markov Graph.
#'
#'
#' @param cg A `caugi` object (DAG).
#'
#' @returns A `caugi` object representing the moralized graph (UG).
#'
#' @examples
#' cg <- caugi(A %-->% C, B %-->% C, class = "DAG")
#' moralize(cg) # A -- B, A -- C, B -- C
#'
#' @family operations
#' @concept operations
#'
#' @export
moralize <- function(cg) {
is_caugi(cg, throw_error = TRUE)
if (cg@graph_class != "DAG") {
stop("moralize() can only be applied to DAGs.", call. = FALSE)
}
moralized_session <- rs_moralize(cg@session)
.session_to_caugi(moralized_session, node_names = cg@nodes$name)
}
#' @title Get the skeleton of a graph
#'
#' @description
#' The skeleton of a graph is obtained by replacing all directed edges with
#' undirected edges.
#'
#' @details
#' This changes the graph from any class to an Undirected Graph (UG), also known
#' as a Markov Graph.
#'
#' @param cg A `caugi` object. Either a DAG or PDAG.
#'
#' @returns A `caugi` object representing the skeleton of the graph (UG).
#'
#' @examples
#' cg <- caugi(A %-->% B, class = "DAG")
#' skeleton(cg) # A --- B
#'
#' @family operations
#' @concept operations
#'
#' @export
skeleton <- function(cg) {
is_caugi(cg, throw_error = TRUE)
skeleton_session <- rs_skeleton(cg@session)
.session_to_caugi(skeleton_session, node_names = cg@nodes$name)
}
#' @title Apply Meek closure to a PDAG
#'
#' @description
#' Applies Meek's orientation rules (R1--R4) repeatedly to a PDAG until no more
#' orientations are implied.
#'
#' @param cg A `caugi` object. Must be PDAG-compatible.
#'
#' @returns A `caugi` object closed under Meek's rules. Class `"MPDAG"` in
#' general, or `"DAG"` if the closure orients every edge.
#'
#' @references
#' C. Meek (1995). Causal inference and causal explanation with background
#' knowledge. In \emph{Proceedings of the Eleventh Conference on Uncertainty in
#' Artificial Intelligence (UAI-95)}, pp. 403--411. Morgan Kaufmann.
#'
#' @examples
#' pdag <- caugi(
#' A %---% B,
#' A %-->% C,
#' C %-->% B,
#' class = "PDAG"
#' )
#' mpdag <- meek_closure(pdag)
#' edges(mpdag)
#'
#' @family operations
#' @concept operations
#'
#' @export
meek_closure <- function(cg) {
is_caugi(cg, throw_error = TRUE)
if (!is_pdag(cg, force_check = TRUE)) {
stop("meek_closure() can only be applied to PDAGs.", call. = FALSE)
}
closed_session <- rs_meek_closure(cg@session)
closed_cg <- .session_to_caugi(closed_session, node_names = cg@nodes$name)
if (is_dag(closed_cg)) {
return(mutate_caugi(closed_cg, "DAG"))
} else {
return(closed_cg)
}
}
#' @title Project latent variables from a DAG to an ADMG
#'
#' @description
#' Projects out latent (unobserved) variables from a DAG to produce an
#' Acyclic Directed Mixed Graph (ADMG) over the observed variables.
#'
#' @param cg A `caugi` object of class `"DAG"`.
#' @param latents Character vector of latent variable names to project out.
#'
#' @returns A `caugi` object of class `"ADMG"` containing only the observed
#' variables.
#'
#' @examples
#' # DAG with latent confounder U
#' dag <- caugi(
#' U %-->% X,
#' U %-->% Y,
#' X %-->% Y,
#' class = "DAG"
#' )
#'
#' # Project out the latent variable
#' admg <- latent_project(dag, latents = "U")
#' # Result: X -> Y, X <-> Y (children of U become bidirected-connected)
#' edges(admg)
#'
#' # DAG with directed path through latent
#' dag2 <- caugi(
#' X %-->% L,
#' L %-->% Y,
#' class = "DAG"
#' )
#'
#' # Project out the latent variable
#' admg2 <- latent_project(dag2, latents = "L")
#' # Result: X -> Y (directed path X -> L -> Y becomes X -> Y)
#' edges(admg2)
#'
#' @family operations
#' @concept operations
#'
#' @export
latent_project <- function(cg, latents) {
is_caugi(cg, throw_error = TRUE)
if (!is_dag(cg)) {
stop("latent_project() can only be applied to DAGs.", call. = FALSE)
}
if (!is.character(latents)) {
stop("`latents` must be a character vector of node names.", call. = FALSE)
}
node_names <- cg@nodes$name
# Validate latent names exist
missing_latents <- setdiff(latents, node_names)
if (length(missing_latents) > 0L) {
stop(
paste0(
"Unknown latent node(s): ",
paste(missing_latents, collapse = ", ")
),
call. = FALSE
)
}
# Get 0-based indices for latent nodes
latent_indices <- rs_indices_of(cg@session, latents)
# Get observed node names (preserving order)
is_latent <- node_names %in% latents
observed_names <- node_names[!is_latent]
# Call Rust function
projected_session <- rs_latent_project(cg@session, latent_indices)
# Convert result back to caugi
.session_to_caugi(projected_session, node_names = observed_names)
}
# ──────────────────────────────────────────────────────────────────────────────
# ──────────────────────────── Mutate caugi class ──────────────────────────────
# ──────────────────────────────────────────────────────────────────────────────
#' @title Mutate `caugi` class
#'
#' @description
#' Mutate the `caugi` class from one graph class to another, if possible.
#' For example, convert a `DAG` to a `PDAG`, or a fully directed `caugi` of
#' class `UNKNOWN` to a `DAG`. Throws an error if not possible.
#'
#' @details
#' This function returns a copy of the object, and the original remains
#' unchanged.
#'
#' @param cg A `caugi` object.
#' @param class A character string specifying the new class.
#'
#' @returns A `caugi` object of the specified class.
#'
#' @examples
#' cg <- caugi(A %-->% B, class = "UNKNOWN")
#' cg_dag <- mutate_caugi(cg, "DAG")
#'
#' @family operations
#' @concept operations
#'
#' @export
mutate_caugi <- function(cg, class) {
is_caugi(cg, throw_error = TRUE)
old_class <- cg@graph_class
if (old_class == class) {
return(cg)
}
if (is_empty_caugi(cg)) {
return(caugi(class = class))
}
is_mutation_possible <- switch(
class,
"DAG" = is_dag(cg),
"PDAG" = is_pdag(cg),
"MPDAG" = is_mpdag(cg),
"CPDAG" = is_cpdag(cg),
"UG" = is_ug(cg),
"ADMG" = is_admg(cg),
"AG" = is_ag(cg),
"UNKNOWN" = TRUE,
stop(paste0("Unknown target class: ", class))
)
if (!is_mutation_possible) {
stop(
paste0(
"Cannot convert caugi of class '",
old_class,
"' to '",
class,
"'."
),
call. = FALSE
)
} else {
# Clone the session so the graph keeps its own edge registry.
session <- rs_clone(cg@session)
# Only UNKNOWN, ADMG, and AG may be non-simple (cf. the caugi validator).
rs_set_simple(
session,
cg@simple || !class %in% c("UNKNOWN", "ADMG", "AG")
)
rs_set_class(session, class)
# Validate eagerly: class checks ignore multiplicity, so parallel edges in
# a non-simple source surface here rather than on first query.
rs_build(session)
return(caugi(.session = session))
}
}
# ──────────────────────────────────────────────────────────────────────────────
# ───────────────────────────────── Exogenize ──────────────────────────────────
# ──────────────────────────────────────────────────────────────────────────────
#' @title Exogenize a graph
#'
#' @description
#' Exogenize a graph by removing all ingoing edges to the set of nodes
#' specified (i.e., make the nodes exogenous), as well as joining the
#' parents of the nodes specified to the children of the nodes specified.
#'
#' @param cg A `caugi` object of class `"DAG"`.
#' @param nodes A character vector of node names to exogenize. Must be a subset
#' of the nodes in the graph.
#'
#' @returns A `caugi` object representing the exogenized graph.
#'
#' @examples
#' cg <- caugi(A %-->% B, class = "DAG")
#' exogenize(cg, nodes = "B") # A, B
#'
#' @family operations
#' @concept operations
#'
#' @export
exogenize <- function(cg, nodes) {
is_caugi(cg, throw_error = TRUE)
if (cg@graph_class != "DAG") {
stop(
"`cg` must be a DAG for `exogenize()`. The input graph is of class ",
cg@graph_class,
".",
call. = FALSE
)
}
if (!is.character(nodes) || length(nodes) == 0) {
stop(
"`nodes` must be a non-empty character vector of node names.",
call. = FALSE
)
}
all_nodes <- nodes(cg)$name
for (u in nodes) {
if (!u %in% all_nodes) {
stop(paste0("Node ", u, " not in graph."), call. = FALSE)
}
}
node_indices <- .nodes_to_indices(cg, nodes)
exogenized_session <- rs_exogenize(cg@session, node_indices)
.session_to_caugi(exogenized_session, node_names = all_nodes)
}
# ──────────────────────────────────────────────────────────────────────────────
# ─────────────────────── Normalize latent structure (DAG) ─────────────────────
# ──────────────────────────────────────────────────────────────────────────────
#' @title Normalize latent structure in a DAG
#'
#' @description
#' Normalizes a DAG with latent variables while preserving the induced marginal
#' model over the observed variables. This is done by:
#'
#' (1) exogenizing all latent nodes (making them parentless),
#' (2) removing exogenous latent nodes with at most one child, and
#' (3) removing exogenous latent nodes whose child sets are strict subsets of
#' another latent node's child set.
#'
#' This corresponds to Lemmas 1--3 in Evans (2016).
#'
#' @param cg A `caugi` object of class "DAG".
#' @param latents Character vector of latent node names.
#'
#' @returns A `caugi` object of class "DAG".
#'
#' @references
#' Evans, R. J. (2016). Graphs for margins of Bayesian networks. Scandinavian
#' Journal of Statistics, 43(3), 625–648. \doi{10.1111/sjos.12194}
#'
#' @examples
#' dag <- caugi(
#' A %-->% U,
#' U %-->% X + Y,
#' class = "DAG"
#' )
#'
#' normalize_latent_structure(dag, latents = "U")
#'
#' # More complex example with two latents and nested child sets
#' dag2 <- caugi(
#' A %-->% U,
#' U %-->% X + Y + Z,
#' U2 %-->% Y + Z,
#' class = "DAG"
#' )
#' normalize_latent_structure(dag2, c("U", "U2"))
#'
#' @family operations
#' @concept operations
#'
#' @export
normalize_latent_structure <- function(cg, latents) {
is_caugi(cg, throw_error = TRUE)
if (!is_dag(cg)) {
stop(
"normalize_latent_structure() can only be applied to DAGs.",
call. = FALSE
)
}
if (!is.character(latents)) {
stop("`latents` must be a character vector of node names.", call. = FALSE)
}
latents <- unique(latents)
if (length(latents) == 0L) {
return(cg)
}
node_names <- nodes(cg)$name
missing_latents <- setdiff(latents, node_names)
if (length(missing_latents) > 0L) {
stop(
paste0(
"Unknown latent node(s): ",
paste(missing_latents, collapse = ", ")
),
call. = FALSE
)
}
latent_indices <- .nodes_to_indices(cg, latents)
normalized_session <- rs_normalize_latent_structure(
cg@session,
latent_indices
)
.session_to_caugi(normalized_session)
}
# ──────────────────────────────────────────────────────────────────────────────
# ────────────────────────── Marginalize and condition ─────────────────────────
# ──────────────────────────────────────────────────────────────────────────────
#' @importFrom utils combn
NULL
#' @title Marginalize and/or condition on variables in an ancestral graph (AG)
#'
#' @description
#' Marginalize variables out of an AG, and/or condition on variables.
#' Depending on the structure, it could produce a graph with directed,
#' bidirected, and undirected edges.
#'
#' @param cg A `caugi` ancestral graph of class `"AG"`.
#' @param cond_vars Character vector of nodes to condition on.
#' @param marg_vars Character vector of nodes to marginalize over.
#'
#' @returns A `caugi` object of class `"AG"`.
#'
#' @family operations
#' @concept operations
#'
#' @references
#' Definition 4.2.1 in Thomas Richardson. Peter Spirtes. "Ancestral graph
#' Markov models." Ann. Statist. 30 (4) 962 - 1030, August 2002.
#' \doi{10.1214/aos/1031689015}
#'
#' @examples
#' mg <- caugi(
#' U %-->% X + Y,
#' A %-->% X,
#' B %-->% Y,
#' class = "DAG"
#' )
#'
#' condition_marginalize(mg, marg_vars = "U") # ADMG
#' condition_marginalize(mg, cond_vars = "U") # DAG
#'
#' @export
condition_marginalize <- function(cg, cond_vars = NULL, marg_vars = NULL) {
is_caugi(cg, throw_error = TRUE)
if (!is_ag(cg)) {
stop(
"`cg` must be an AG for `condition_marginalize()`. ",
"The input graph is of class ",
cg@graph_class,
".",
call. = FALSE
)
}
cond_vars_valid <- is.character(cond_vars) && length(cond_vars) > 0L
marg_vars_valid <- is.character(marg_vars) && length(marg_vars) > 0L
if (!cond_vars_valid && !marg_vars_valid) {
stop(
"Either `cond_vars` or `marg_vars` must be a non-empty character vector ",
"of node names.",
call. = FALSE
)
}
if (length(intersect(cond_vars, marg_vars)) > 0L) {
stop("`cond_vars` and `marg_vars` must be disjoint.", call. = FALSE)
}
# Compute remaining nodes after removing conditioned and marginalized vars
all_node_names <- nodes(cg)$name
removed_vars <- union(cond_vars, marg_vars)
remaining_nodes <- setdiff(all_node_names, removed_vars)
n_remaining <- length(remaining_nodes)
# Early exit for trivial cases
if (n_remaining < 2L) {
return(caugi(nodes = remaining_nodes, class = "AG"))
}
# Pre-compute anteriors for all relevant nodes
nodes_for_anteriors <- union(remaining_nodes, cond_vars)
anteriors_list <- anteriors(cg, nodes_for_anteriors)
if (!is.list(anteriors_list)) {
# Single node case: wrap in named list
anteriors_list <- .set_names(list(anteriors_list), nodes_for_anteriors)
}
# Generate all pairs of remaining nodes
pair_indices <- combn(n_remaining, 2L)
n_pairs <- ncol(pair_indices)
# Pre-allocate edge list
edge_list <- vector("list", n_pairs)
for (j in seq_len(n_pairs)) {
node_a <- remaining_nodes[pair_indices[1L, j]]
node_b <- remaining_nodes[pair_indices[2L, j]]
# Check if nodes are adjacent in the original graph
is_adjacent <- node_a %in% neighbors(cg, nodes = node_b)
if (!is_adjacent) {
# Check m-separation for all subsets of (other remaining nodes ∪ cond_vars)
# Nodes are adjacent if NOT m-separated for ANY conditioning subset
other_nodes <- setdiff(remaining_nodes, c(node_a, node_b))
is_adjacent <- .not_m_separated_for_all_subsets(
cg,
node_a,
node_b,
other_nodes,
cond_vars
)
}
if (is_adjacent) {
edge_list[[j]] <- .edge_type_from_anteriors(
node_a,
node_b,
cond_vars,
anteriors_list
)
}
}
# Combine edges efficiently using data.table
non_null <- !vapply(edge_list, is.null, logical(1L))
edges_df <- data.table::rbindlist(edge_list[non_null])
caugi(edges_df = edges_df, nodes = remaining_nodes, class = "AG")
}
#' @title
#' Check if nodes are NOT m-separated for all conditioning subsets
#'
#' @description
#' Tests whether two nodes fail to be m-separated for every possible
#' conditioning set formed from `other_nodes` combined with `cond_vars`.
#' If they are never separated, they must be adjacent in the resulting graph.
#'
#' @param cg A `caugi` object.
#' @param node_a First node name.
#' @param node_b Second node name.
#' @param other_nodes Other remaining nodes to form conditioning sets from.
#' @param cond_vars Conditioning variables (always included in conditioning).
#'
#' @returns `TRUE` if nodes are not m-separated for any subset (i.e., adjacent).
#'
#' @keywords internal
.not_m_separated_for_all_subsets <- function(
cg,
node_a,
node_b,
other_nodes,
cond_vars
) {
node_idx <- .nodes_to_indices(cg, c(node_a, node_b))
other_idx <- if (length(other_nodes) == 0L) {
integer(0)
} else {
.nodes_to_indices(cg, other_nodes)
}
cond_idx <- if (length(cond_vars) == 0L) {
integer(0)
} else {
.nodes_to_indices(cg, cond_vars)
}
rs_not_m_separated_for_all_subsets(
cg@session,
node_idx[[1]],
node_idx[[2]],
other_idx,
cond_idx
)
}
#' @title
#' Infer edge type from anterior relationships
#'
#' @description
#' Given two adjacent nodes, infers the edge type (directed, bidirected,
#' or undirected) based on whether each node is in the anterior of the other
#' combined with the conditioning set.
#'
#' @param node_a First node name.
#' @param node_b Second node name.
#' @param cond_vars Conditioning variables.
#' @param anteriors_list Pre-computed list of anteriors for all nodes.
#'
#' @returns A single-row `data.table` with `from`, `edge`, `to` columns.
#'
#' @keywords internal
.edge_type_from_anteriors <- function(
node_a,
node_b,
cond_vars,
anteriors_list
) {
# Check if a is in ant(b ∪ S): a is in {b ∪ S} or in anteriors of {b ∪ S}
nodes_with_b <- c(node_b, cond_vars)
anteriors_of_b <- unlist(anteriors_list[nodes_with_b], use.names = FALSE)
a_in_anterior_of_b <- node_a %in% nodes_with_b || node_a %in% anteriors_of_b
# Check if b is in ant(a ∪ S)
nodes_with_a <- c(node_a, cond_vars)
anteriors_of_a <- unlist(anteriors_list[nodes_with_a], use.names = FALSE)
b_in_anterior_of_a <- node_b %in% nodes_with_a || node_b %in% anteriors_of_a
if (!a_in_anterior_of_b && !b_in_anterior_of_a) {
# Neither in anterior of the other: bidirected edge
data.table::data.table(from = node_a, edge = "<->", to = node_b)
} else if (a_in_anterior_of_b && b_in_anterior_of_a) {
# Both in anterior of each other: undirected edge
data.table::data.table(from = node_a, edge = "---", to = node_b)
} else if (a_in_anterior_of_b) {
# a is in anterior of b: a --> b
data.table::data.table(from = node_a, edge = "-->", to = node_b)
} else {
# b is in anterior of a: b --> a
data.table::data.table(from = node_b, edge = "-->", to = node_a)
}
}
# ──────────────────────────────────────────────────────────────────────────────
# ───────────────────────────── Extend a PDAG to a DAG ──────────────────────
# ──────────────────────────────────────────────────────────────────────────────
#' @title Extend a PDAG to a DAG using the Dor-Tarsi Algorithm
#' @description
#' Given a Partially Directed Acyclic Graph (PDAG), this function attempts to
#' extend it to a Directed Acyclic Graph (DAG) by orienting the undirected edges
#' while preserving acyclicity and all existing directed edges.
#' The procedure implements the Dor-Tarsi algorithm.
#'
#' If the PDAG cannot be consistently extended to a DAG, the function will raise an error.
#'
#' @param cg A `caugi` object of class `"PDAG"`, `"MPDAG"`, or `"CPDAG"`.
#' @param PDAG Deprecated alias for `cg`. Use `cg` instead.
#'
#' @returns A `caugi` object of class `"DAG"` representing a DAG extension
#' of the input PDAG.
#'
#' @family operations
#' @concept operations
#'
#' @examples
#' pdag <- caugi(
#' A %---% B,
#' B %---% C,
#' class = "PDAG"
#' )
#' dag <- dag_from_pdag(pdag)
#' edges(dag)
#'
#' @references
#' Dor, D., & Tarsi, M. (1992). "A simple algorithm to construct a consistent
#' extension of a partially directed acyclic graph".
#'
#' @export
dag_from_pdag <- function(cg, PDAG) {
if (!missing(PDAG)) {
warning(
"The `PDAG` argument of `dag_from_pdag()` is deprecated; ",
"use `cg` instead.",
call. = FALSE
)
if (missing(cg)) {
cg <- PDAG
}
}
is_caugi(cg, throw_error = TRUE)
if (!(cg@graph_class %in% c("PDAG", "MPDAG", "CPDAG"))) {
stop("Input must be a caugi PDAG/MPDAG/CPDAG graph")
}
.session_to_caugi(rs_dag_extension(cg@session), node_names = cg@nodes$name)
}
#' @title Enumerate all DAGs in a Markov equivalence class
#'
#' @description
#' 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.
#'
#' @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.
#'
#' @param cg A `caugi` object of class `"PDAG"` or `"MPDAG"`.
#'
#' @returns A list of `caugi` objects of class `"DAG"`, one per DAG in the MEC.
#'
#' @examples
#' pdag <- caugi(
#' A %---% B,
#' B %---% C,
#' class = "PDAG"
#' )
#' dags <- enumerate_dags(pdag)
#' length(dags) # 3
#'
#' @references
#' Chickering, D. M. (2002). "Learning Equivalence Classes of Bayesian-Network
#' Structures". \emph{Journal of Machine Learning Research}, 2:445--498.
#'
#' @family operations
#' @concept operations
#'
#' @export
enumerate_dags <- function(cg) {
is_caugi(cg, throw_error = TRUE)
if (!is_pdag(cg, force_check = TRUE)) {
stop("enumerate_dags() can only be applied to PDAGs.", call. = FALSE)
}
sessions <- rs_enumerate_dags(cg@session)
# Rust returns a Dag view, so the session's graph_class is already "DAG";
# no mutate_caugi roundtrip needed.
lapply(sessions, function(s) {
.session_to_caugi(s, node_names = cg@nodes$name)
})
}
#' @title Count DAGs in a Markov equivalence class
#'
#' @description
#' Returns the number of DAGs in the Markov equivalence class of a PDAG
#' without materializing each one. Useful for sizing an enumeration before
#' calling [enumerate_dags()].
#'
#' @param cg A `caugi` object of class `"PDAG"` or `"MPDAG"`.
#'
#' @returns A single numeric value, the cardinality of the MEC. Counts above
#' `2^53` lose integer precision; in practice no realistic PDAG yields a
#' MEC anywhere near that size.
#'
#' @examples
#' pdag <- caugi(
#' A %---% B,
#' B %---% C,
#' class = "PDAG"
#' )
#' count_dags(pdag) # 3
#'
#' @references
#' Chickering, D. M. (2002). "Learning Equivalence Classes of Bayesian-Network
#' Structures". \emph{Journal of Machine Learning Research}, 2:445--498.
#'
#' @family operations
#' @concept operations
#'
#' @export
count_dags <- function(cg) {
is_caugi(cg, throw_error = TRUE)
if (!is_pdag(cg, force_check = TRUE)) {
stop("count_dags() can only be applied to PDAGs.", call. = FALSE)
}
rs_count_dags(cg@session)
}
Any scripts or data that you put into this service are public.
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.