Package edu.cmu.tetrad.search.utils

Class FciOrient

java.lang.Object

edu.cmu.tetrad.search.utils.FciOrient

public class FciOrient
extends Object

Performs the final orientation steps of the FCI algorithms, which is a useful tool to use in a variety of FCI-like algorithms.

There are two versions of these final orientation steps, one due to Peter Spirtes (the original, in Causation, Prediction and Search), which is arrow complete, and the other due to Jiji Zhang, which is arrow and tail complete. The references for these are as follows.

Spirtes, P., Glymour, C. N., Scheines, R., & Heckerman, D. (2000). Causation, prediction, and search. MIT press.

Zhang, J. (2008). On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence, 172(16-17), 1873-1896.

These final rules are used in all algorithms in Tetrad that follow and refine the FCI algorithm--for example, the GFCI and RFCI algorihtms.

We've made the methods for each of the separate rules publicly accessible in case someone wants to use the individual rules in the context of their own algorithms.

Note: This class is a modified version of the original FciOrient class, in that we allow the R0 and R4 rules to be be overridden by subclasses. This is useful for the TeyssierScorer class, which needs to override these rules in order to calculate the score of the graph. It is also useful for DAG to PAG, which needs to override these rules in order to use D-SEP. The R0 and R4 rules are the only ones that cannot be carried out by an examination of the graph but which require additional analysis of the underlying distribution or graph. In addition, several methods have been optimized.

Version:

$Id: $Id

Author:

Erin Korber, June 2004, Alex Smith, December 2008, josephramsey 2024-8-21, Choh-Man Teng

See Also:

• Fci
• GFci
• Rfci

Constructor Summary

Constructors

Constructor	Description
FciOrient(R0R4Strategy strategy)	Initializes a new instance of the FciOrient class with the specified R4Strategy.

Method Summary

Modifier and Type	Method	Description
void	fciOrientbk(Knowledge bk, Graph graph, List<Node> variables)	Orient the edges of a graph based on the given knowledge.
void	finalOrientation(Graph graph)	Orients the graph (in place) according to rules in the graph (FCI step D).
Collection<Triple>	getInitialAllowedColliders()	Returns the initial allowed colliders based on the current strategy.
int	getMaxDiscriminatingPathLength()	Returns the maximum path length, or -1 if unlimited.
static boolean	isArrowheadAllowed(Node x, Node y, Graph graph, Knowledge knowledge)	Determines whether an arrowhead is allowed between two nodes in a graph, based on specific conditions.
boolean	isCompleteRuleSetUsed()	Checks if the complete rule set is being used.
static Set<DiscriminatingPath>	listDiscriminatingPaths(Graph graph, int maxDiscriminatingPathLength, boolean checkEcNonadjacency)	Lists all the discriminating paths in the given graph.
static Set<DiscriminatingPath>	listDiscriminatingPaths(Graph graph, Node w, Node y, int maxDiscriminatingPathLength, boolean checkEcNonadjacency)	Lists the discriminating paths for <w, y> in the graph.
void	orient(Graph graph, Set<Triple> unshieldedTriples)	Performs FCI orientation on the given graph, including R0 and either the Spirtes or Zhang final orientation rules.
void	ruleR0(Graph graph, Set<Triple> unshieldedTriples)	Orients unshielded colliders in the graph.
void	ruleR1(Node a, Node b, Node c, Graph graph)	R1 If α ∗→ β o−−∗ γ, and α and γ are not adjacent, then orient the triple as α ∗→ β → γ.
void	ruleR10(Node alpha, Node gamma, Graph graph)	R10 Suppose α o→ γ, β → γ ← θ, p1 is an uncovered potentially directed (semidirected) path from α to β, and p2 is an uncovered p.d.
void	ruleR2(Node a, Node b, Node c, Graph graph)	R2 If α → β ∗→ γ or α ∗→ β → γ, and α ∗−o γ, then orient α ∗−o γ as α ∗→ γ.
void	ruleR3(Graph graph)	R3 If α ∗→ β ←∗ γ, α ∗−o θ o−∗ γ, α and γ are not adjacent, and θ ∗−o β, then orient θ ∗−o β as θ ∗→ β.
void	ruleR4(Graph graph)	R4 If u = <θ ,...,α,β,γ> is a discriminating path between θ and γ for β, and β o−−∗ γ; then if β ∈ Sepset(θ,γ), orient β o−−∗ γ as β → γ; otherwise orient the triple <α,β,γ> as α ↔ β ↔ γ.
void	ruleR5(Graph graph)	R5 For every (remaining) α o−−o β, if there is an uncovered circle path p = <α,γ,...,θ,β> between α and β s.t.
void	ruleR6(Graph graph)	R6 If α —- β o−−∗ γ (α and γ may or may not be adjacent), then orient β o−−∗ γ as β −−∗ γ.
void	ruleR7(Graph graph)	R7 If α −−o β o−−∗ γ, and α, γ are not adjacent, then orient β o−−∗ γ as β −−∗ γ.
boolean	ruleR8(Node a, Node c, Graph graph)	R8 If α → β → γ or α−−◦β → γ, and α o→ γ, orient α o→ γ as α → γ.
boolean	ruleR9(Node a, Node c, Graph graph)	R9 If α o→ γ, and p = <α,β,θ,...,γ> is an uncovered potentialy directed path from α to γ such that γ and β are not adjacent, then orient α o→ γ as α → γ.
void	rulesR1R2cycle(Graph graph)	Apply rules R1 and R2 in cycles for a given graph.
void	rulesR8R9R10(Graph graph)	Implements Zhang's rules R8, R9, R10, applies them over the graph once.
void	setAllowedColliders(Set<Triple> allowedColliders)	Sets the allowed colliders for this object.
void	setCompleteRuleSetUsed(boolean completeRuleSetUsed)	Sets the flag indicating if the complete rule set is being used.
void	setDoR4(boolean doR4)	Sets whether R4 should be run.
void	setEndpointStrategy(SetEndpointStrategy endpointStrategy)	Sets the endpoint strategy for this object.
void	setInitialAllowedColliders(HashSet<Triple> initialAllowedColliders)	Sets the initial allowed colliders for the strategy.
void	setKnowledge(Knowledge knowledge)	Sets the knowledge to use for the final orientation.
void	setMaxDiscriminatingPathLength(int maxDiscriminatingPathLength)	Sets the maximum length of any discriminating path.
void	setParallel(boolean parallel)	Sets whether the discriminating path orientation should be run in parallel.
void	setTestTimeout(long testTimeout)	Sets the timeout for running tests.
void	setVerbose(boolean verbose)	Sets whether verbose output is printed.

Methods inherited from class java.lang.Object

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

Constructor Details

FciOrient

public FciOrient(R0R4Strategy strategy)

Initializes a new instance of the FciOrient class with the specified R4Strategy.

Parameters:

strategy - The FciOrientDataExaminationStrategy to use for the examination.

Throws:

NullPointerException - If the strategy parameter is null.

See Also:

• R0R4Strategy

Method Details

isArrowheadAllowed

public static boolean isArrowheadAllowed(Node x,
 Node y,
 Graph graph,
 Knowledge knowledge)

Determines whether an arrowhead is allowed between two nodes in a graph, based on specific conditions.

Parameters:

x - The first node.

y - The second node.

graph - The graph data structure.

knowledge - The knowledge base containing forbidden connections.

Returns:

true if an arrowhead is allowed between X and Y, false otherwise.

listDiscriminatingPaths

public static Set<DiscriminatingPath> listDiscriminatingPaths(Graph graph,
 int maxDiscriminatingPathLength,
 boolean checkEcNonadjacency)

Lists all the discriminating paths in the given graph.

Parameters:

graph - the graph to analyze

maxDiscriminatingPathLength - the maximum length of a discriminating path

checkEcNonadjacency - whether to check for EC nonadjacency

Returns:

a set of discriminating paths found in the graph

listDiscriminatingPaths

public static Set<DiscriminatingPath> listDiscriminatingPaths(Graph graph,
 Node w,
 Node y,
 int maxDiscriminatingPathLength,
 boolean checkEcNonadjacency)

Lists the discriminating paths for <w, y> in the graph.

Parameters:

graph - The graph.

w - The first node.

y - The second node.

maxDiscriminatingPathLength - The maximum length of w discriminating path.

checkEcNonadjacency - Whether to check for EC nonadjacency.

Returns:

The set of discriminating paths for <w, y>.

orient

public void orient(Graph graph,
 Set<Triple> unshieldedTriples)

Performs FCI orientation on the given graph, including R0 and either the Spirtes or Zhang final orientation rules.

Parameters:

graph - The graph to orient.

unshieldedTriples - The set of unshielded triples oriented by R0. This set is updated with new triples.

setKnowledge

public void setKnowledge(Knowledge knowledge)

Sets the knowledge to use for the final orientation.

Parameters:

knowledge - This knowledge.

isCompleteRuleSetUsed

public boolean isCompleteRuleSetUsed()

Checks if the complete rule set is being used.

Returns:

true if the complete rule set is being used, false otherwise.

setCompleteRuleSetUsed

public void setCompleteRuleSetUsed(boolean completeRuleSetUsed)

Sets the flag indicating if the complete rule set is being used.

Parameters:

completeRuleSetUsed - boolean value indicating if the complete rule set is being used

ruleR0

public void ruleR0(Graph graph,
 Set<Triple> unshieldedTriples)

Orients unshielded colliders in the graph. (FCI Step C, Zhang's step F3, rule R0.)

Parameters:

graph - The graph to orient.

unshieldedTriples - The set of unshielded triples oriented by R0. This set is updated with new triples.

finalOrientation

public void finalOrientation(Graph graph)

Orients the graph (in place) according to rules in the graph (FCI step D).

Zhang's rules R1-R10.

Parameters:

graph - a Graph object

rulesR1R2cycle

public void rulesR1R2cycle(Graph graph)

Apply rules R1 and R2 in cycles for a given graph.

Parameters:

graph - The graph to apply the rules on.

ruleR1

public void ruleR1(Node a,
 Node b,
 Node c,
 Graph graph)

R1 If α ∗→ β o−−∗ γ, and α and γ are not adjacent, then orient the triple as α ∗→ β → γ.

Parameters:

a - α

b - β

c - γ

graph - the graph containing the edges and nodes

ruleR2

public void ruleR2(Node a,
 Node b,
 Node c,
 Graph graph)

R2 If α → β ∗→ γ or α ∗→ β → γ, and α ∗−o γ, then orient α ∗−o γ as α ∗→ γ.

Parameters:

a - α

b - β

c - γ

graph - the graph in which the nodes exist

ruleR3

public void ruleR3(Graph graph)

R3 If α ∗→ β ←∗ γ, α ∗−o θ o−∗ γ, α and γ are not adjacent, and θ ∗−o β, then orient θ ∗−o β as θ ∗→ β.

Parameters:

graph - a Graph object

ruleR4

public void ruleR4(Graph graph)

R4 If u = <θ ,...,α,β,γ> is a discriminating path between θ and γ for β, and β o−−∗ γ; then if β ∈ Sepset(θ,γ), orient β o−−∗ γ as β → γ; otherwise orient the triple <α,β,γ> as α ↔ β ↔ γ.

Parameters:

graph - a Graph object

ruleR5

public void ruleR5(Graph graph)

R5 For every (remaining) α o−−o β, if there is an uncovered circle path p = <α,γ,...,θ,β> between α and β s.t. α,θ are not adjacent and β,γ are not adjacent, then orient α o−−o β and every edge on p as undirected edges (--).

Parameters:

graph - the graph to orient.

ruleR6

public void ruleR6(Graph graph)

R6 If α —- β o−−∗ γ (α and γ may or may not be adjacent), then orient β o−−∗ γ as β −−∗ γ.

Parameters:

graph - a Graph object

ruleR7

public void ruleR7(Graph graph)

R7 If α −−o β o−−∗ γ, and α, γ are not adjacent, then orient β o−−∗ γ as β −−∗ γ.

Parameters:

graph - a Graph object

rulesR8R9R10

public void rulesR8R9R10(Graph graph)

Implements Zhang's rules R8, R9, R10, applies them over the graph once. Orient arrow tails. I.e., tries R8, R9, and R10 in that sequence on each Ao->C in the graph.

Parameters:

graph - a Graph object

ruleR8

public boolean ruleR8(Node a,
 Node c,
 Graph graph)

R8 If α → β → γ or α−−◦β → γ, and α o→ γ, orient α o→ γ as α → γ.

Parameters:

a - α

c - γ

graph - a Graph object

Returns:

Whether R8 was successfully applied.

ruleR9

public boolean ruleR9(Node a,
 Node c,
 Graph graph)

R9 If α o→ γ, and p = <α,β,θ,...,γ> is an uncovered potentialy directed path from α to γ such that γ and β are not adjacent, then orient α o→ γ as α → γ.

Parameters:

a - The node A.

c - The node C.

graph - The graph being oriented.

Returns:

Whether R9 was successfully applied.

ruleR10

public void ruleR10(Node alpha,
 Node gamma,
 Graph graph)

R10 Suppose α o→ γ, β → γ ← θ, p1 is an uncovered potentially directed (semidirected) path from α to β, and p2 is an uncovered p.d. path from α to θ. Let μ be the vertex adjacent to α on p1 (μ could be β), and ω be the vertex adjacent to α on p2 (ω could be θ). If μ and ω are distinct, and are not adjacent, then orient α o→ γ as α → γ.

Parameters:

alpha - α

gamma - γ

graph - alpha Graph object

getMaxDiscriminatingPathLength

public int getMaxDiscriminatingPathLength()

Returns the maximum path length, or -1 if unlimited.

Returns:

the maximum path length

setMaxDiscriminatingPathLength

public void setMaxDiscriminatingPathLength(int maxDiscriminatingPathLength)

Sets the maximum length of any discriminating path.

Parameters:

maxDiscriminatingPathLength - the maximum length of any discriminating path, or -1 if unlimited.

setVerbose

public void setVerbose(boolean verbose)

Sets whether verbose output is printed.

Parameters:

verbose - True, if so.

setTestTimeout

public void setTestTimeout(long testTimeout)

Sets the timeout for running tests.

Parameters:

testTimeout - the timeout value in milliseconds

setAllowedColliders

public void setAllowedColliders(Set<Triple> allowedColliders)

Sets the allowed colliders for this object. These are passed to R4 is the set of unshielded colliders for the model is to be restricted. TODO Think this through again.

Parameters:

allowedColliders - the set of colliders allowed to interact with this object

getInitialAllowedColliders

public Collection<Triple> getInitialAllowedColliders()

Returns the initial allowed colliders based on the current strategy. These are the unshielded colliders from R4's first run.

TODO think this through again.

Returns:

a collection of Triple objects representing the initial allowed colliders.

setInitialAllowedColliders

public void setInitialAllowedColliders(HashSet<Triple> initialAllowedColliders)

Sets the initial allowed colliders for the strategy.

TODO: Think this thorugh again.

Parameters:

initialAllowedColliders - The set of initial allowed colliders.

setParallel

public void setParallel(boolean parallel)

Sets whether the discriminating path orientation should be run in parallel.

Parameters:

parallel - True, if so.

setEndpointStrategy

public void setEndpointStrategy(SetEndpointStrategy endpointStrategy)

Sets the endpoint strategy for this object.

Parameters:

endpointStrategy - the endpoint strategy to set

See Also:

• SetEndpointStrategy

fciOrientbk

public void fciOrientbk(Knowledge bk,
 Graph graph,
 List<Node> variables)

Orient the edges of a graph based on the given knowledge.

Parameters:

bk - The knowledge containing forbidden and required edges.

graph - The graph to be oriented.

variables - The list of nodes in the graph.

setDoR4

public void setDoR4(boolean doR4)

Sets whether R4 should be run.

Parameters:

doR4 - True, if so.