Package edu.cmu.tetrad.graph

Class Paths

java.lang.Object

edu.cmu.tetrad.graph.Paths

All Implemented Interfaces:

TetradSerializable, Serializable

public class Paths
extends Object
implements TetradSerializable

Paths class.

Version:

$Id: $Id

Author:

josephramsey

See Also:

• Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	Paths.AllCliquesAlgorithm	An algorithm to find all cliques in a graph.

Constructor Summary

Constructors

Constructor	Description
Paths(Graph graph)	Constructor for Paths.

Method Summary

Modifier and Type	Method	Description
List<Set<Node>>	adjustmentSets(Node source, Node target, int maxNumSets, int maxDistanceFromEndpoint, int nearWhichEndpoint, int maxPathLength)	An adjustment set for a pair of nodes <source, target> for a CPDAG is a set of nodes that blocks all paths from the source to the target that cannot contribute to a calculation for the total effect of the source on the target in any DAG in a CPDAG while not blocking any path from the source to the target that could be causal.
List<List<Node>>	allDirectedPaths(Node node1, Node node2, int maxLength)	Finds all directed paths from node1 to node2 with a maximum length.
Set<List<Node>>	allPaths(Node node1, Node node2, int maxPathLength)	Finds all paths from node1 to node2 within a specified maximum length.
Set<List<Node>>	allPaths(Node node1, Node node2, int minLength, int maxLength, Set<Node> conditionSet, Map<Node,Set<Node>> ancestors, boolean allowSelectionBias)	Finds all paths between two nodes satisfying certain conditions.
Set<List<Node>>	allPaths(Node node1, Node node2, int maxLength, Set<Node> conditionSet, boolean allowSelectionBias)	Finds all paths between two nodes within a given maximum length, considering optional condition set and selection bias.
Set<List<Node>>	allPathsOutOf(Node node1, int maxLength, Set<Node> conditionSet, boolean allowSelectionBias)	Generates all paths out of a given node within a specified maximum length and conditional set.
List<List<Node>>	amenablePathsMpdagMag(Node node1, Node node2, int maxLength)	Finds amenable paths from the given source node to the given destination node with a maximum length.
List<List<Node>>	amenablePathsPag(Node node1, Node node2, int maxLength)	Finds amenable paths from the given source node to the given destination node with a maximum length, for a PAG.
Set<Node>	anteriority(Node... X)	Returns the set of nodes that are in the anteriority of the given nodes in the graph.
List<List<Node>>	connectedComponents()	Returns a list of connected components in the graph.
boolean	definiteNonDescendent(Node node1, Node node2)	added by ekorber, 2004/06/12
boolean	defVisible(Edge edge)	Returns true just in case the given edge is definitely visible.
List<List<Node>>	directedPaths(Node node1, Node node2, int maxLength)	Finds all directed paths from node1 to node2 with a maximum length.
Set<Node>	district(Node node)	Retrieves the set of nodes that belong to the same district as the given node.
Set<Node>	dsep(Node x, Node y)	Returns D-SEP(x, y) for a maximal ancestral graph G (or inducing path graph G, as in Causation, Prediction and Search).
boolean	existsDirectedCycle()	existsDirectedCycle.
boolean	existsDirectedPath(Node node1, Node node2)	Checks if a directed path exists between two nodes in a graph.
boolean	existsDirectedPath(Node node1, Node node2, int depth)	Checks if a directed path exists between two nodes within a certain depth.
boolean	existsDirectedPath(Node node1, Node node2, org.apache.commons.lang3.tuple.Pair<Node,Node> without)	Checks if a directed path exists between two nodes in a graph, ignoring a specified edge.
boolean	existsInducingPath(Node x, Node y, Set<Node> selectionVariables)	Determines whether an inducing path exists between two nodes in a graph.
boolean	existsInducingPathDFS(Node x, Node y, Set<Node> selectionVariables)	Determines whether an inducing path exists between node1 and node2, given a set O of observed nodes and a set sem of conditioned nodes.
boolean	existsInducingPathVisit(Node a, Node b, Node x, Node y, Set<Node> selectionVariables, LinkedList<Node> path)	Determines whether an inducing path exists between two nodes in a graph.
boolean	existsSemiDirectedPath(Node from, Node to)	existsSemiDirectedPath.
boolean	existsSemiDirectedPath(Node node1, Set<Node> nodes)	existsSemiDirectedPath.
boolean	existsTrek(Node node1, Node node2)	Determines whether a trek exists between two nodes in the graph.
List<Node>	getAncestors(Node node)	Retrieves the ancestors of a specified `Node` in the graph.
List<Node>	getAncestors(List<Node> nodes)	Returns a list of all ancestors of the given nodes.
Map<Node,Set<Node>>	getAncestorsMap()	Return a map from each node to its collection of ancestors.
static Graph	getDag(List<Node> pi, Graph g, boolean verbose)	Generates a directed acyclic graph (DAG) based on the given list of nodes using Raskutti and Uhler's method.
Set<Node>	getDescendants(Node node)	Returns a list of all descendants of the given node.
List<Node>	getDescendants(List<Node> nodes)	Retrieves the descendants of the given list of nodes.
Map<Node,Set<Node>>	getDescendantsMap()	Return a map from each node to its collection of descendants.
List<Node>	getInducingPath(Node x, Node y, Set<Node> selectionVariables)	This method calculates the inducing path between two measured nodes in a graph.
Set<Node>	getMConnectedVars(Node y, Set<Node> z)	Retrieves the set of nodes that are connected to the given node y and are also present in the set of nodes z.
Set<Node>	getMConnectedVars(Node y, Set<Node> z, Map<Node,Set<Node>> ancestors)	getMConnectedVars.
static Set<Node>	getParents(List<Node> pi, int p, Graph g, boolean verbose, boolean allowSelectionBias)	Returns the parents of the node at index p, calculated using Pearl's method.
Set<Node>	getSepset(Node x, Node y, boolean allowSelectionBias, IndependenceTest test, int depth)	Finds a sepset for x and y, if there is one; otherwise, returns null.
Set<Node>	getSepsetContaining(Node x, Node y, Set<Node> containing, int maxPathLength)	Retrieves a sepset (a set of nodes) between two given nodes.
List<Node>	getValidOrder(List<Node> initialOrder, boolean forward)	Returns a valid causal order for either a DAG or a CPDAG.
boolean	isAncestor(Node b, Set<Node> z)	Return true if b is an ancestor of any node in z
boolean	isAncestorOf(Node node1, Node node2)	Determines whether one node is an ancestor of another.
boolean	isDescendentOf(Node node1, Node node2)	Determines whether one node is a descendent of another.
boolean	isDirected(Node node1, Node node2)	Checks if there is a directed edge from node1 to node2 in the graph.
boolean	isLegalCpdag()	Checks if the current graph is a legal CPDAG (completed partially directed acyclic graph).
boolean	isLegalDag()	Checks if the graph passed as parameter is a legal directed acyclic graph (DAG).
boolean	isLegalMag()	Checks if the given graph is a legal mag.
boolean	isLegalMpag()	Checks if the given Maximal Ancestral Graph (MPAG) is legal.
boolean	isLegalMpdag()	Checks if the given graph is a legal Maximal Partial Directed Acyclic Graph (MPDAG).
boolean	isLegalPag()	Checks if the given Directed Acyclic Graph (DAG) is a Legal Partial Ancestral Graph (PAG).
boolean	isMConnectedTo(Node x, Node y, Set<Node> z, boolean allowSelectionBias)	Determmines whether x and y are d-connected given z.
boolean	isMConnectedTo(Node x, Node y, Set<Node> z, Map<Node,Set<Node>> ancestors, boolean isPag)	Detemrmines whether x and y are d-connected given z.
boolean	isMConnectingPath(List<Node> path, Set<Node> conditioningSet, boolean isPag)	Checks if the given path is an m-connecting path.
boolean	isMConnectingPath(List<Node> path, Set<Node> conditioningSet, Map<Node,Set<Node>> ancestors, boolean allowSelectionBias)	Checks if the given path is an m-connecting path.
boolean	isMSeparatedFrom(Node node1, Node node2, Set<Node> z, boolean isPag)	Determines whether one n ode is d-separated from another.
boolean	isMSeparatedFrom(Node node1, Node node2, Set<Node> z, Map<Node,Set<Node>> ancestors, boolean allowSelectionBias)	Checks if two nodes are M-separated.
boolean	isSatisfyBackDoorCriterion(Graph graph, Node x, Node y, Set<Node> z)	Check to see if a set of variables Z satisfies the back-door criterion relative to node x and node y.
boolean	isUndirected(Node node1, Node node2)	Checks if the edge between two nodes in the graph is undirected.
void	makeValidOrder(List<Node> order)	Reorders the given order into a valid causal order for either a DAG or a CPDAG.
Set<Node>	markovBlanket(Node node)	Returns the Markov Blanket of a given node in the graph.
Set<Set<Node>>	maxCliques()	Returns a set of all maximum cliques in the graph.
boolean	possibleAncestor(Node node1, Node node2)	possibleAncestor.
List<Node>	possibleDsep(Node x, Node y, int maxPossibleDsepPathLength)	Calculates the possible d-separation nodes between two given Nodes within a graph, using a maximum path length constraint.
void	removeByPossibleMsep(IndependenceTest test, SepsetMap sepsets)	Remove edges by the possible m-separation rule.
List<List<Node>>	semidirectedPaths(Node node1, Node node2, int maxLength)	Finds all semi-directed paths between two nodes up to a maximum length.
List<List<Node>>	treks(Node node1, Node node2, int maxLength)	Finds all treks from node1 to node2 with a maximum length.
List<List<Node>>	treksIncludingBidirected(Node node1, Node node2)	Finds all possible treks between two nodes, including bidirectional treks.

Methods inherited from class java.lang.Object

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

Constructor Details

Paths

public Paths(Graph graph)

Constructor for Paths.

Parameters:

graph - a Graph object

Method Details

getDag

public static Graph getDag(List<Node> pi,
 Graph g,
 boolean verbose)

Generates a directed acyclic graph (DAG) based on the given list of nodes using Raskutti and Uhler's method.

Parameters:

pi - a list of nodes representing the set of vertices in the graph

g - the graph

verbose - whether to print verbose output

Returns:

a Graph object representing the generated DAG.

getParents

public static Set<Node> getParents(List<Node> pi,
 int p,
 Graph g,
 boolean verbose,
 boolean allowSelectionBias)

Returns the parents of the node at index p, calculated using Pearl's method.

Parameters:

pi - The list of nodes.

p - The index.

g - The graph.

verbose - Whether to print verbose output.

allowSelectionBias - whether to allow selection bias; if true, then undirected edges X--Y are uniformly treated as X->L<-Y.

Returns:

The parents, as a Pair object (parents + score).

getValidOrder

public List<Node> getValidOrder(List<Node> initialOrder,
 boolean forward)

Returns a valid causal order for either a DAG or a CPDAG. (bryanandrews)

Parameters:

initialOrder - Variables in the order will be kept as close to this initial order as possible, either the forward order or the reverse order, depending on the next parameter.

forward - Whether the variables will be iterated over in forward or reverse direction.

Returns:

The valid causal order found.

makeValidOrder

public void makeValidOrder(List<Node> order)

Reorders the given order into a valid causal order for either a DAG or a CPDAG. (bryanandrews)

Parameters:

order - Variables in the order will be kept as close to this initial order as possible, either the forward order or the reverse order, depending on the next parameter.

isLegalDag

public boolean isLegalDag()

Checks if the graph passed as parameter is a legal directed acyclic graph (DAG).

Returns:

true if the graph is a legal DAG, false otherwise.

isLegalCpdag

public boolean isLegalCpdag()

Checks if the current graph is a legal CPDAG (completed partially directed acyclic graph).

Returns:

true if the graph is a legal CPDAG, false otherwise.

isLegalMpdag

public boolean isLegalMpdag()

Checks if the given graph is a legal Maximal Partial Directed Acyclic Graph (MPDAG). A MPDAG is considered legal if it is equal to a CPDAG where additional edges have been oriented by Knowledge, with Meek rules applied for maximum orientation. The test is performed by attemping to convert the graph to a CPDAG using the DAG to CPDAG transformation and testing whether that graph is a legal CPDAG. Finally, we test to see whether the obtained graph is equal to the original graph.

Returns:

true if the MPDAG is legal, false otherwise.

isLegalMpag

public boolean isLegalMpag()

Checks if the given Maximal Ancestral Graph (MPAG) is legal. A MPAG is considered legal if it is equal to a PAG where additional edges have been oriented by Knowledge, with final FCI rules applied for maximum orientation. The test is performed by attemping to convert the graph to a PAG using the DAG to CPDAG transformation and testing whether that graph is a legal PAG. Finally, we test to see whether the obtained graph is equal to the original graph.

The user may choose to use the rules from Zhang (2008) or the rules from Spirtes et al. (2000).

Returns:

true if the MPDAG is legal, false otherwise.

isLegalMag

public boolean isLegalMag()

Checks if the given graph is a legal mag.

Returns:

true if the graph is a legal mag, false otherwise

isLegalPag

public boolean isLegalPag()

Checks if the given Directed Acyclic Graph (DAG) is a Legal Partial Ancestral Graph (PAG).

Returns:

true if the graph is a Legal PAG, false otherwise

maxCliques

public Set<Set<Node>> maxCliques()

Returns a set of all maximum cliques in the graph.

Returns:

a set of sets of nodes representing the maximum cliques in the graph

connectedComponents

public List<List<Node>> connectedComponents()

Returns a list of connected components in the graph.

Returns:

A list of connected components, where each component is represented as a list of nodes.

directedPaths

public List<List<Node>> directedPaths(Node node1,
 Node node2,
 int maxLength)

Finds all directed paths from node1 to node2 with a maximum length.

Parameters:

node1 - the starting node

node2 - the destination node

maxLength - the maximum length of the paths

Returns:

a list of lists containing the directed paths from node1 to node2

semidirectedPaths

public List<List<Node>> semidirectedPaths(Node node1,
 Node node2,
 int maxLength)

Finds all semi-directed paths between two nodes up to a maximum length.

Parameters:

node1 - the starting node

node2 - the ending node

maxLength - the maximum path length

Returns:

a list of all semi-directed paths between the two nodes

amenablePathsMpdagMag

public List<List<Node>> amenablePathsMpdagMag(Node node1,
 Node node2,
 int maxLength)

Finds amenable paths from the given source node to the given destination node with a maximum length.

Parameters:

node1 - the source node

node2 - the destination node

maxLength - the maximum length of the paths

Returns:

a list of amenable paths from the source node to the destination node, each represented as a list of nodes

amenablePathsPag

public List<List<Node>> amenablePathsPag(Node node1,
 Node node2,
 int maxLength)

Finds amenable paths from the given source node to the given destination node with a maximum length, for a PAG. These are semidirected paths that start with a visible edge out of node1.

Parameters:

node1 - the source node

node2 - the destination node

maxLength - the maximum length of the paths

Returns:

a list of amenable paths from the source node to the destination node, each represented as a list of nodes

allPaths

public Set<List<Node>> allPaths(Node node1,
 Node node2,
 int maxPathLength)

Finds all paths from node1 to node2 within a specified maximum length.

Parameters:

node1 - The starting node.

node2 - The target node.

maxPathLength - The maximum length of the paths.

Returns:

A list of paths, where each path is a list of nodes.

allPaths

public Set<List<Node>> allPaths(Node node1,
 Node node2,
 int maxLength,
 Set<Node> conditionSet,
 boolean allowSelectionBias)

Finds all paths between two nodes within a given maximum length, considering optional condition set and selection bias.

Parameters:

node1 - the starting node

node2 - the target node

maxLength - the maximum length of each path

conditionSet - a set of nodes that need to be included in the path (optional)

allowSelectionBias - if true, undirected edges are interpreted as selection bias; otherwise, as directed edges in one direction or the other.

Returns:

a set of paths between node1 and node2 that satisfy the conditions

allPaths

public Set<List<Node>> allPaths(Node node1,
 Node node2,
 int minLength,
 int maxLength,
 Set<Node> conditionSet,
 Map<Node,Set<Node>> ancestors,
 boolean allowSelectionBias)

Finds all paths between two nodes satisfying certain conditions.

Parameters:

node1 - the starting node

node2 - the ending node

minLength - the minimum length of paths to consider

maxLength - the maximum length of paths to consider

conditionSet - a set of nodes that must be present in the paths

ancestors - a map representing the ancestry relationships of nodes

allowSelectionBias - true if selection bias is allowed, false otherwise

Returns:

a set of lists representing all paths between node1 and node2

allPathsOutOf

public Set<List<Node>> allPathsOutOf(Node node1,
 int maxLength,
 Set<Node> conditionSet,
 boolean allowSelectionBias)

Generates all paths out of a given node within a specified maximum length and conditional set.

Parameters:

node1 - The starting node.

maxLength - The maximum length of each path.

conditionSet - The set of nodes that must be present in each path.

allowSelectionBias - Determines whether to allow selection bias when choosing the next node to visit.

Returns:

A set containing all generated paths as lists of nodes.

allDirectedPaths

public List<List<Node>> allDirectedPaths(Node node1,
 Node node2,
 int maxLength)

Finds all directed paths from node1 to node2 with a maximum length.

Parameters:

node1 - The starting node.

node2 - The target node.

maxLength - The maximum length of the paths.

Returns:

A list of lists of nodes representing the directed paths from node1 to node2.

treks

public List<List<Node>> treks(Node node1,
 Node node2,
 int maxLength)

Finds all treks from node1 to node2 with a maximum length.

Parameters:

node1 - the starting node

node2 - the destination node

maxLength - the maximum length of the treks

Returns:

a list of lists of nodes representing each trek from node1 to node2

treksIncludingBidirected

public List<List<Node>> treksIncludingBidirected(Node node1,
 Node node2)

Finds all possible treks between two nodes, including bidirectional treks.

Parameters:

node1 - The starting node.

node2 - The ending node.

Returns:

A List of Lists representing all treks between the given nodes.

markovBlanket

public Set<Node> markovBlanket(Node node)

Returns the Markov Blanket of a given node in the graph.

Parameters:

node - the node for which the Markov Blanket needs to be computed

Returns:

a set of nodes that constitute the Markov Blanket of the given node

district

public Set<Node> district(Node node)

Retrieves the set of nodes that belong to the same district as the given node.

Parameters:

node - the node from which to start the district search

Returns:

the set of nodes that belong to the same district as the given node

existsDirectedPath

public boolean existsDirectedPath(Node node1,
 Node node2,
 int depth)

Checks if a directed path exists between two nodes within a certain depth.

Parameters:

node1 - the first node in the path

node2 - the second node in the path

depth - the maximum depth to search for the path

Returns:

true if a directed path exists between the two nodes within the given depth, false otherwise

existsSemiDirectedPath

public boolean existsSemiDirectedPath(Node from,
 Node to)

existsSemiDirectedPath.

Parameters:

from - a Node object

to - a Node object

Returns:

a boolean

getMConnectedVars

public Set<Node> getMConnectedVars(Node y,
 Set<Node> z)

Retrieves the set of nodes that are connected to the given node y and are also present in the set of nodes z.

Parameters:

y - The node for which to find the connected nodes.

z - The set of nodes to be considered for connecting nodes.

Returns:

The set of nodes that are connected to y and present in z.

getMConnectedVars

public Set<Node> getMConnectedVars(Node y,
 Set<Node> z,
 Map<Node,Set<Node>> ancestors)

getMConnectedVars.

Parameters:

y - a Node object

z - a Set object

ancestors - a Map object

Returns:

a Set object

getDescendantsMap

public Map<Node,Set<Node>> getDescendantsMap()

Return a map from each node to its collection of descendants.

Returns:

This map.

getAncestorsMap

public Map<Node,Set<Node>> getAncestorsMap()

Return a map from each node to its collection of ancestors.

Returns:

This map.

isAncestor

public boolean isAncestor(Node b,
 Set<Node> z)

Return true if b is an ancestor of any node in z

Parameters:

b - a Node object

z - a Set object

Returns:

true if b is an ancestor of any node in z

existsInducingPathDFS

public boolean existsInducingPathDFS(Node x,
 Node y,
 Set<Node> selectionVariables)

Determines whether an inducing path exists between node1 and node2, given a set O of observed nodes and a set sem of conditioned nodes.

Parameters:

x - the first node.

y - the second node.

selectionVariables - the set of selection variables.

Returns:

true if an inducing path exists, false if not.

existsInducingPathVisit

public boolean existsInducingPathVisit(Node a,
 Node b,
 Node x,
 Node y,
 Set<Node> selectionVariables,
 LinkedList<Node> path)

Determines whether an inducing path exists between two nodes in a graph.

Parameters:

a - the first node in the graph

b - the second node in the graph

x - the first measured node in the graph

y - the second measured node in the graph

selectionVariables - the set of selection variables

path - the path to check

Returns:

true if an inducing path exists, false if not

existsInducingPath

public boolean existsInducingPath(Node x,
 Node y,
 Set<Node> selectionVariables)

Determines whether an inducing path exists between two nodes in a graph. This is a breadth-first implementation.

Parameters:

x - the first node in the graph

y - the second node in the graph

selectionVariables - the set of selection variables

Returns:

true if an inducing path exists, false if not

getInducingPath

public List<Node> getInducingPath(Node x,
 Node y,
 Set<Node> selectionVariables)

This method calculates the inducing path between two measured nodes in a graph.

Parameters:

x - the first measured node in the graph

y - the second measured node in the graph

selectionVariables - the set of selection variables

Returns:

the inducing path between node x and node y, or null if no inducing path exists

Throws:

IllegalArgumentException - if either x or y is not of NodeType.MEASURED

possibleDsep

public List<Node> possibleDsep(Node x,
 Node y,
 int maxPossibleDsepPathLength)

Calculates the possible d-separation nodes between two given Nodes within a graph, using a maximum path length constraint.

Parameters:

x - the starting Node for the path

y - the ending Node for the path

maxPossibleDsepPathLength - the maximum length of the path, -1 for unlimited

Returns:

a List of Nodes representing the possible d-separation nodes

removeByPossibleMsep

public void removeByPossibleMsep(IndependenceTest test,
 SepsetMap sepsets)
                          throws InterruptedException

Remove edges by the possible m-separation rule.

Parameters:

test - The independence test to use to remove edges.

sepsets - A sepset map to which sepsets should be added. May be null, in which case sepsets will not be recorded.

Throws:

InterruptedException

dsep

public Set<Node> dsep(Node x,
 Node y)

Returns D-SEP(x, y) for a maximal ancestral graph G (or inducing path graph G, as in Causation, Prediction and Search).

We trust the user to make sure the given graph is a MAG or IPG; we don't check this.

Parameters:

x - The one endpoint.

y - The other endpoint.

Returns:

D-SEP(x, y) for MAG/IPG G.

isSatisfyBackDoorCriterion

public boolean isSatisfyBackDoorCriterion(Graph graph,
 Node x,
 Node y,
 Set<Node> z)

Check to see if a set of variables Z satisfies the back-door criterion relative to node x and node y. (author Kevin V. Bui (March 2020).

Parameters:

graph - a Graph object

x - a Node object

y - a Node object

z - a Set object

Returns:

a boolean

getSepset

public Set<Node> getSepset(Node x,
 Node y,
 boolean allowSelectionBias,
 IndependenceTest test,
 int depth)

Finds a sepset for x and y, if there is one; otherwise, returns null.

Parameters:

x - The first node.

y - The second node.

allowSelectionBias - Whether to allow selection bias.

test - The independence test to use.

depth - The maximum depth to search for a sepset.

Returns:

A sepset for x and y, if there is one; otherwise, null.

getSepsetContaining

public Set<Node> getSepsetContaining(Node x,
 Node y,
 Set<Node> containing,
 int maxPathLength)

Retrieves a sepset (a set of nodes) between two given nodes.

Parameters:

x - the first node

y - the second node

containing - the set of nodes that the sepset must contain

maxPathLength - the maximum length of the path to search for the blocking set

Returns:

the sepset between the two nodes

isMConnectedTo

public boolean isMConnectedTo(Node x,
 Node y,
 Set<Node> z,
 boolean allowSelectionBias)

Determmines whether x and y are d-connected given z.

Parameters:

x - a Node object

y - a Node object

z - a Set object

allowSelectionBias - whether to allow selection bias; if true, then undirected edges X--Y are uniformly treated as X->L<-Y.

Returns:

true if x and y are d-connected given z; false otherwise.

isMConnectingPath

public boolean isMConnectingPath(List<Node> path,
 Set<Node> conditioningSet,
 boolean isPag)

Checks if the given path is an m-connecting path.

Parameters:

path - The path to check.

conditioningSet - The set of nodes to check reachability against.

isPag - Determines if selection bias is allowed in the m-connection procedure.

Returns:

true if the given path is an m-connecting path, false otherwise.

isMConnectingPath

public boolean isMConnectingPath(List<Node> path,
 Set<Node> conditioningSet,
 Map<Node,Set<Node>> ancestors,
 boolean allowSelectionBias)

Checks if the given path is an m-connecting path.

Parameters:

path - The path to check.

conditioningSet - The set of nodes to check reachability against.

ancestors - The ancestors of each node in the graph.

allowSelectionBias - Determines if selection bias is allowed in the m-connection procedure.

Returns:

true if the given path is an m-connecting path, false otherwise.

isMConnectedTo

public boolean isMConnectedTo(Node x,
 Node y,
 Set<Node> z,
 Map<Node,Set<Node>> ancestors,
 boolean isPag)

Detemrmines whether x and y are d-connected given z.

Parameters:

x - a Node object

y - a Node object

z - a Set object

ancestors - a Map object

isPag - whether to allow selection bias; if true, then undirected edges X--Y are uniformly treated as X->L<-Y.

Returns:

true if x and y are d-connected given z; false otherwise.

defVisible

public boolean defVisible(Edge edge)

Returns true just in case the given edge is definitely visible. The reference for this is Zhang, J. (2008). Causal Reasoning with Ancestral Graphs. Journal of Machine Learning Research, 9(7).

This definition will work for MAGs and PAGs. "Definite" here means for PAGs that the edge is visible in all MAGs in the equivalence class.

Parameters:

edge - the edge to check.

Returns:

true if the given edge is definitely visible.

Throws:

IllegalArgumentException - if the given edge is not a directed edge in the graph

existsDirectedCycle

public boolean existsDirectedCycle()

existsDirectedCycle.

Returns:

a boolean

existsDirectedPath

public boolean existsDirectedPath(Node node1,
 Node node2)

Checks if a directed path exists between two nodes in a graph.

Parameters:

node1 - the starting node of the path

node2 - the target node of the path

Returns:

true if a directed path exists from node1 to node2, false otherwise

existsDirectedPath

public boolean existsDirectedPath(Node node1,
 Node node2,
 org.apache.commons.lang3.tuple.Pair<Node,Node> without)

Checks if a directed path exists between two nodes in a graph, ignoring a specified edge.

Parameters:

node1 - the starting node of the path

node2 - the target node of the path

without - the edge to ignore. If null, no edge is ignored.

Returns:

true if a directed path exists from node1 to node2, false otherwise

existsSemiDirectedPath

public boolean existsSemiDirectedPath(Node node1,
 Set<Node> nodes)

existsSemiDirectedPath.

Parameters:

node1 - a Node object

nodes - a Set object

Returns:

a boolean

existsTrek

public boolean existsTrek(Node node1,
 Node node2)

Determines whether a trek exists between two nodes in the graph. A trek exists if there is a directed path between the two nodes or else, for some third node in the graph, there is a path to each of the two nodes in question.

Parameters:

node1 - a Node object

node2 - a Node object

Returns:

a boolean

getDescendants

public Set<Node> getDescendants(Node node)

Returns a list of all descendants of the given node.

Parameters:

node - The node for which to find descendants.

Returns:

A list of all descendant nodes.

getDescendants

public List<Node> getDescendants(List<Node> nodes)

Retrieves the descendants of the given list of nodes.

Parameters:

nodes - The list of nodes to find descendants for.

Returns:

A list of nodes that are descendants of the given nodes.

isAncestorOf

public boolean isAncestorOf(Node node1,
 Node node2)

Determines whether one node is an ancestor of another.

Parameters:

node1 - a Node object

node2 - a Node object

Returns:

a boolean

getAncestors

public List<Node> getAncestors(Node node)

Retrieves the ancestors of a specified `Node` in the graph.

Parameters:

node - The node whose ancestors are to be retrieved.

Returns:

A list of ancestors for the specified `Node`.

getAncestors

public List<Node> getAncestors(List<Node> nodes)

Returns a list of all ancestors of the given nodes.

Parameters:

nodes - the list of nodes for which to find ancestors

Returns:

a list containing all the ancestors of the given nodes

isDescendentOf

public boolean isDescendentOf(Node node1,
 Node node2)

Determines whether one node is a descendent of another.

Parameters:

node1 - a Node object

node2 - a Node object

Returns:

a boolean

definiteNonDescendent

public boolean definiteNonDescendent(Node node1,
 Node node2)

added by ekorber, 2004/06/12

Parameters:

node1 - a Node object

node2 - a Node object

Returns:

true iff node2 is a definite nondecendent of node1

isMSeparatedFrom

public boolean isMSeparatedFrom(Node node1,
 Node node2,
 Set<Node> z,
 boolean isPag)

Determines whether one n ode is d-separated from another. According to Spirtes, Richardson and Meek, two nodes are d- connected given some conditioning set Z if there is an acyclic undirected path U between them, such that every collider on U is an ancestor of some element in Z and every non-collider on U is not in Z. Two elements are d-separated just in case they are not d-connected. A collider is a node which two edges hold in common for which the endpoints leading into the node are both arrow endpoints.

Precondition: This graph is a DAG. Please don't violate this constraint; weird things can happen!

Parameters:

node1 - the first node.

node2 - the second node.

z - the conditioning set.

isPag - whether to allow selection bias; if true, then undirected edges X--Y are uniformly treated as X->L<-Y.

Returns:

true if node1 is d-separated from node2 given set t, false if not.

isMSeparatedFrom

public boolean isMSeparatedFrom(Node node1,
 Node node2,
 Set<Node> z,
 Map<Node,Set<Node>> ancestors,
 boolean allowSelectionBias)

Checks if two nodes are M-separated.

Parameters:

node1 - The first node.

node2 - The second node.

z - The set of nodes to be excluded from the path.

ancestors - A map containing the ancestors of each node.

allowSelectionBias - whether to allow selection bias; if true, then undirected edges X--Y are uniformly treated as X->L<-Y.

Returns:

true if the two nodes are M-separated, false otherwise.

isDirected

public boolean isDirected(Node node1,
 Node node2)

Checks if there is a directed edge from node1 to node2 in the graph.

Parameters:

node1 - the source node

node2 - the destination node

Returns:

true if there is a directed edge from node1 to node2, false otherwise

isUndirected

public boolean isUndirected(Node node1,
 Node node2)

Checks if the edge between two nodes in the graph is undirected.

Parameters:

node1 - the first node

node2 - the second node

Returns:

true if the edge is undirected, false otherwise

possibleAncestor

public boolean possibleAncestor(Node node1,
 Node node2)

possibleAncestor.

Parameters:

node1 - a Node object

node2 - a Node object

Returns:

a boolean

anteriority

public Set<Node> anteriority(Node... X)

Returns the set of nodes that are in the anteriority of the given nodes in the graph.

Parameters:

X - the nodes for which the anteriority needs to be determined

Returns:

the set of nodes in the anteriority of the given nodes

adjustmentSets

public List<Set<Node>> adjustmentSets(Node source,
 Node target,
 int maxNumSets,
 int maxDistanceFromEndpoint,
 int nearWhichEndpoint,
 int maxPathLength)

An adjustment set for a pair of nodes <source, target> for a CPDAG is a set of nodes that blocks all paths from the source to the target that cannot contribute to a calculation for the total effect of the source on the target in any DAG in a CPDAG while not blocking any path from the source to the target that could be causal. In typical causal graphs, multiple adjustment sets may exist for a given pair of nodes. This method returns up to maxNumSets adjustment sets for the pair of nodes <source, target> fitting a certain description.

The description is as follows. We look for adjustment sets of varaibles that are close to either the source or the target (or either) in the graph. We take all possibly causal paths from the source to the target into account but only consider other paths up to a certain specified length. (This maximum length can be unlimited for small graphs.)

Within this description, we list adjustment sets in order or increasing size.

Hopefully, these parameters along with the size ordering can help to give guidance for the user to choose the best adjustment set for their purposes when multiple adjustment sets are possible.

This currently will only work for DAGs and CPDAGs.

Parameters:

source - The source node whose sets will be used for adjustment.

target - The target node whose sets will be adjusted to match the source node.

maxNumSets - The maximum number of sets to be adjusted. If this value is less than or equal to 0, all sets in the target node will be adjusted to match the source node.

maxDistanceFromEndpoint - The maximum distance from the endpoint of the trek to consider for adjustment.

nearWhichEndpoint - The endpoint(s) to consider for adjustment; 1 = near the source, 2 = near the target, 3 = near either.

maxPathLength - The maximum length of the path to consider for backdoor paths. If a value of -1 is given, all paths will be considered.

Returns:

A list of adjustment sets for the pair of nodes <source, target>.