Class PagLegalityCheck

java.lang.Object

edu.cmu.tetrad.search.utils.PagLegalityCheck

public class PagLegalityCheck
extends Object

The PagLegalityCheck class provides utility methods for validating the legality of Partial Ancestral Graphs (PAGs) and Maximal Ancestral Graphs (MAGs). It includes methods to assess legality both verbosely, with detailed reasons, and quietly, returning only a boolean outcome.

The quiet methods are staged for speed: cheap necessary conditions are checked first (endpoint syntax, ancestrality of the definite directed part, closure under the sepset-free FCI orientation rules), and the expensive arbiter (Zhang MAG construction, MAG legality, MAG-to-PAG round trip) runs only if all prefilters pass. In a search loop where most candidates are illegal, most candidates are rejected before the round trip.

The verbose methods retain the original (slower) logic so that diagnostic messages are unchanged.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	PagLegalityCheck.LegalMagRet	Stores a result for checking whether a graph is a legal MAG--(a) whether it is (a boolean), and (b) the reason why it is not, if it is not (a String).
static class	PagLegalityCheck.LegalPagRet	Stores a result for checking whether a graph is a legal PAG--(a) whether it is (a boolean), and (b) the reason why it is not, if it is not (a String).

Method Summary

Modifier and Type	Method	Description
static PagLegalityCheck.LegalMagRet	isLegalMag(Graph mag, Set<Node> selection)	Determines whether the given graph is a legal Maximal Ancestral Graph (MAG).
static PagLegalityCheck.LegalMagRet	isLegalMag(Graph mag, Set<Node> selection, int timeoutSeconds)	Runs isLegalMag(Graph, Set) with a timeout.
static boolean	isLegalMagQuiet(Graph mag, Set<Node> selection)	Determines whether the given graph is a legal Maximal Ancestral Graph (MAG) without providing detailed error messages.
static PagLegalityCheck.LegalPagRet	isLegalPag(Graph pag, Graph mag, Set<Node> selection)	The same certificate with the Zhang MAG of pag supplied by the caller, for searches that have already computed that MAG for another purpose (to score it, say) and would otherwise pay for the conversion twice per candidate.
static PagLegalityCheck.LegalPagRet	isLegalPag(Graph pag, Set<Node> selection)	Checks if the provided Partial Ancestral Graph (PAG) is a legal PAG.
static PagLegalityCheck.LegalPagRet	isLegalPag(Graph pag, Set<Node> selection, int timeoutSeconds)	Runs isLegalPag(Graph, Set) with a timeout.
static PagLegalityCheck.LegalPagRet	isLegalPagModuloKnowledge(Graph pag, Set<Node> selection, Knowledge knowledge, FciOrient orient, boolean excludeSelectionBias)	Legality certificate for a PAG that carries background-knowledge endpoint marks: legal PAG *modulo background knowledge*.
static boolean	isLegalPagQuiet(Graph pag, Set<Node> selection)	Determines whether the provided Partial Ancestral Graph (PAG) is a legal PAG without providing detailed error messages.
static boolean	isLegalPagQuiet(Graph pag, Set<Node> selection, int timeoutSeconds)	Runs isLegalPagQuiet(Graph, Set) with a timeout.

Methods inherited from class Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Details

isLegalPag

public static PagLegalityCheck.LegalPagRet isLegalPag(Graph pag,
 Set<Node> selection,
 int timeoutSeconds)

Runs isLegalPag(Graph, Set) with a timeout.

Parameters:

pag - the PAG to check

selection - the selection set

timeoutSeconds - maximum seconds to wait

Returns:

A LegalPagRet object indicating whether the PAG is legal or not, along with a reason if it is not legal, if the check completed within the timeout

Throws:

RuntimeException - if the check fails, is interrupted, or times out (a timeout should be treated by the caller as a failed legality check, i.e. the surgery is reverted)

isLegalMag

public static PagLegalityCheck.LegalMagRet isLegalMag(Graph mag,
 Set<Node> selection,
 int timeoutSeconds)

Runs isLegalMag(Graph, Set) with a timeout.

Parameters:

mag - the MAG to check

selection - the selection set

timeoutSeconds - maximum seconds to wait

Returns:

A LegalMagRet object indicating whether the MAG is legal or not, along with a reason if it is not legal, if the check completed within the timeout

Throws:

RuntimeException - if the check fails, is interrupted, or times out

isLegalPagQuiet

public static boolean isLegalPagQuiet(Graph pag,
 Set<Node> selection,
 int timeoutSeconds)

Runs isLegalPagQuiet(Graph, Set) with a timeout.

Parameters:

pag - the PAG to check

selection - the selection set

timeoutSeconds - maximum seconds to wait

Returns:

true if legal and completed within the timeout

Throws:

RuntimeException - if the check fails, is interrupted, or times out

isLegalPag

public static PagLegalityCheck.LegalPagRet isLegalPag(Graph pag,
 Set<Node> selection)

Checks if the provided Partial Ancestral Graph (PAG) is a legal PAG.

This is the verbose (diagnostic) path. It intentionally uses the exact, unbounded MAG-to-PAG round trip so that a "legal" verdict is a certificate; there is no bounded variant, since bounding the discriminating path search makes the check approximate.

Parameters:

pag - The Partial Ancestral Graph (PAG) to be checked

selection - The set of nodes to be conditioned on

Returns:

A LegalPagRet object indicating whether the PAG is legal or not, along with a reason if it is not legal.

isLegalPag

public static PagLegalityCheck.LegalPagRet isLegalPag(Graph pag,
 Graph mag,
 Set<Node> selection)

The same certificate with the Zhang MAG of pag supplied by the caller, for searches that have already computed that MAG for another purpose (to score it, say) and would otherwise pay for the conversion twice per candidate. The verdict is identical to isLegalPag(Graph, Set) provided mag is in fact GraphTransforms.zhangMagFromPag(pag); supplying any other graph voids the certificate.

Parameters:

pag - The Partial Ancestral Graph (PAG) to be checked

mag - The Zhang MAG of pag, precomputed by the caller

selection - The set of nodes to be conditioned on

Returns:

A LegalPagRet object indicating whether the PAG is legal or not, along with a reason if it is not legal.

isLegalPagModuloKnowledge

public static PagLegalityCheck.LegalPagRet isLegalPagModuloKnowledge(Graph pag,
 Set<Node> selection,
 Knowledge knowledge,
 FciOrient orient,
 boolean excludeSelectionBias)
                                                              throws InterruptedException

Legality certificate for a PAG that carries background-knowledge endpoint marks: legal PAG *modulo background knowledge*. When knowledge is empty this delegates to isLegalPag(Graph, Set) and is therefore exactly the strict certificate. Otherwise the strict certificate's final round-trip equality is replaced by equality modulo knowledge:

1. all nodes must be measured;
2. the graph's implied Zhang MAG must exist and be a legal MAG (this is where structural pathologies -- cycles, almost-cycles, non-maximality -- are caught, so none of that protection is given up);
3. the canonical PAG of that MAG is computed (MagToPag), then re-refined with background knowledge (fciOrientbk) and re-closed under the complete FCI final rules using the supplied orientation engine (pass the engine that oriented the candidate so data-driven R4 resolutions are reproduced and any sepset bookkeeping stays local to that engine);
4. the candidate must equal the knowledge-refined canonical PAG exactly.

Every mark in an accepted graph is therefore either invariant in the Markov equivalence class of the implied MAG or forced by knowledge (directly or via rule propagation). A graph that is "between a MAG and a PAG" for any OTHER reason -- e.g., a non-invariant collider stamped from a noisy sepset -- still fails, exactly as under the strict certificate. This mirrors the modulo-knowledge certificate of StarFci (legalPagModuloKnowledge); it is needed by any search that pins knowledge marks and then gates candidate graphs on legality, since knowledge-refined marks (e.g., a tier arrowhead sharpening a class circle) always fail the strict round-trip equality.

Parameters:

pag - the candidate graph (already carrying knowledge marks)

selection - the selection nodes for the MAG legality check

knowledge - the background knowledge whose refinements are to be tolerated

orient - the orientation engine used to knowledge-refine the reconstituted canonical PAG

excludeSelectionBias - the selection-bias policy passed through to the final-rule closure

Returns:

a LegalPagRet whose isLegalPag() is true iff the candidate is a legal PAG refined by knowledge

Throws:

InterruptedException - if interrupted during the final-rule closure

isLegalMag

public static PagLegalityCheck.LegalMagRet isLegalMag(Graph mag,
 Set<Node> selection)

Determines whether the given graph is a legal Maximal Ancestral Graph (MAG). This is the verbose (diagnostic) path; use isLegalMagQuiet(Graph, Set) in inner loops.

Parameters:

mag - the graph to be checked

selection - the set of nodes to be conditioned on

Returns:

a LegalMagRet object indicating whether the graph is legal and providing an error message if it is not

isLegalPagQuiet

public static boolean isLegalPagQuiet(Graph pag,
 Set<Node> selection)

Determines whether the provided Partial Ancestral Graph (PAG) is a legal PAG without providing detailed error messages. Staged for speed:

1. Stage 0: endpoint syntax on the PAG itself (measured nodes; single edge per pair; all endpoints in {tail, arrow, circle}).
2. Stage 1: ancestrality of the definite directed part (acyclic --> subgraph; no arrowhead into a definite ancestor, which covers directed and almost-directed cycles; no arrowhead at an endpoint of an undirected edge).
3. Stage 2: closure under the sepset-free FCI orientation rules R1, R2, R3, R8. If any rule would change a mark, the graph is under-oriented ("between a MAG and a PAG") and is rejected without building the MAG.
4. Stage 3 (arbiter): Zhang MAG construction, fast MAG legality, exact MAG-to-PAG round trip, equality.

Stages 0-2 are necessary conditions only; Stage 3 is the exact arbiter and its verdict is final. Note that both zhangMagFromPag and MagToPag preserve adjacencies, so skeletons of pag and the reconstituted PAG always agree and a plain equality test suffices in Stage 3.

Parameters:

pag - The Partial Ancestral Graph (PAG) to be checked.

selection - The set of nodes to be conditioned on.

Returns:

true if the PAG is legal, false otherwise.

isLegalMagQuiet

public static boolean isLegalMagQuiet(Graph mag,
 Set<Node> selection)

Determines whether the given graph is a legal Maximal Ancestral Graph (MAG) without providing detailed error messages. Single-pass structural check: one topological sort for acyclicity, one ancestor-bitset closure reused by the bidirected-semantics check and the maximality check, and maximality via per-pair arrow-state reachability (walk-to-path splicing makes walk reachability equivalent to inducing-path existence).

Parameters:

mag - the graph to be checked

selection - the set of nodes to be conditioned on

Returns:

true if the graph is a legal MAG, false otherwise