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:

  • 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 excludeSelectionBias)
      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.
      excludeSelectionBias - 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.

    • getValidOrderMag

      public List<Node> getValidOrderMag(List<Node> initialOrder, boolean forward)
      Generates a valid topological ordering of nodes in a directed graph without cycles. If the provided graph is cyclic, an IllegalArgumentException is thrown.
      Parameters:
      initialOrder - the initial list of nodes representing a possible order to process
      forward - a boolean indicating the direction of the list processing; if true, the initial order is reversed
      Returns:
      a valid list of nodes representing the order in which the directed graph can be traversed without breaking dependency constraints

    • 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.

    • checkLegalCpdag

      public Paths.CpdagCheckResult checkLegalCpdag()
      Checks whether the given graph is a CPDAG (Completed Partially Directed Acyclic Graph). This method performs the following validation steps:

      1. Ensures all edges in the graph are either directed or undirected. 2. Validates whether a valid elimination order exists for the graph. 3. Compares the input graph to the CPDAG derived from the DAG of the graph using the valid elimination order and a d-separation algorithm.

      If the graph passes all the checks, it is deemed to be a CPDAG. Otherwise, the method surfaces specific violations with helpful details for debugging.

      Returns:
      A CpdagCheckResult object indicating whether the input graph is a legal CPDAG. If the graph is not a CPDAG, the result will include the corresponding violation and relevant details.

    • isLegalCpdag

      public boolean isLegalCpdag()
      Determines whether the current structure is a legal completed partially directed acyclic graph (CPDAG). This method synchronizes the check to ensure thread-safe operations.
      Returns:
      true if the current structure is a legal CPDAG; false otherwise.

    • isLegalPdag

      public boolean isLegalPdag()
      Checks if the given graph is a legal Maximal Partial Directed Acyclic Graph (PDAG). A PDAG 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 PDAG is legal, false otherwise.

    • isLegalMpag

      public boolean isLegalMpag(boolean excludeSelectionBias)
      Checks if the given Maximal Ancestral Graph (MAG) is legal. A MAG 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).

      Parameters:
      excludeSelectionBias - True to exclude selection bias, false otherwise.
      Returns:
      true if the PDAG 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() throws RuntimeException
      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
      Throws:
      RuntimeException - if the check times out or there is an error in the check

    • 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 Set<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

    • potentiallyDirectedPaths

      public Set<List<Node>> potentiallyDirectedPaths(Node node1, Node node2, int maxLength)
      Finds all potentially 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 set of all potentially directed paths between the two nodes

    • getAmenablePathsPdagMag

      public Set<List<Node>> getAmenablePathsPdagMag(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 set of amenable paths from the source node to the destination node, each represented as a list of nodes

    • getAmenablePathsMag

      public Set<List<Node>> getAmenablePathsMag(Node node1, Node node2, int maxLength, Set<Node> forceVisible)
      Amenable paths for MAGs: potentially directed paths from node1 to node2 whose first edge is directed out of node1 AND visible (Zhang 2008; required for adjustment amenability in MAGs per Perkovic et al. 2018). An invisible directed edge in a MAG is compatible with latent confounding, so it cannot anchor an amenable path.
      Parameters:
      node1 - the source node
      node2 - the target node
      maxLength - maximum path length, or -1 for unbounded
      forceVisible - nodes b for which a directed edge node1 -> b should be treated as visible by fiat (e.g., from background knowledge); may be empty
      Returns:
      the set of amenable paths

    • getAmenablePathsPag

      public Set<List<Node>> getAmenablePathsPag(Node node1, Node node2, int maxLength, Set<Node> forceVisible)
      Finds amenable paths from the given source node to the given destination node with a maximum length, for a PAG. These are potentially directed paths that start with a visible edge out of node1. This is the option used by Refinement-based PAG IDA (rPAG-IDA).
      Parameters:
      node1 - the source node
      node2 - the destination node
      maxLength - the maximum length of the paths
      forceVisible - the set of nodes out of X to force visibility for
      Returns:
      a set 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 excludeSelectionBias)
      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)
      excludeSelectionBias - 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 excludeSelectionBias)
      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
      excludeSelectionBias - 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 excludeSelectionBias)
      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.
      excludeSelectionBias - 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 Set<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

    • existsPotentiallyDirectedPath

      public boolean existsPotentiallyDirectedPath(Node from, Node to)

      existsPotentiallyDirectedPath.

      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.

    • isAncestorOfAnyZ

      public boolean isAncestorOfAnyZ(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

    • existsInducingPathBFS

      public boolean existsInducingPathBFS(Node x, Node y, Set<Node> selectionVariables)
      Breadth-first version of the “inducing-path exists?” test.
      Parameters:
      x - first measured node
      y - second measured node
      selectionVariables - set of selection variables (Z)
      Returns:
      true iff there is an inducing path from x to y

    • 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, int maxPossibleDsepPathLength)
      Identifies and returns a list of possible d-separating nodes relative to a specified node in the graph. The search is constrained by the specified maximum path length.
      Parameters:
      x - the target node for which possible d-separating nodes are to be identified
      maxPossibleDsepPathLength - the maximum allowable path length for determining d-separating nodes; a value of -1 indicates no explicit limit
      Returns:
      a sorted list of nodes that are potential d-separators for the specified node, ordered in descending order

    • removeByPossibleDsep

      public void removeByPossibleDsep(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 - if any

    • 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 excludeSelectionBias, 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.
      excludeSelectionBias - 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) throws InterruptedException, TimeoutException
      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
      Throws:
      InterruptedException - if any.
      TimeoutException - if the operation times out

    • isMConnectedTo

      public boolean isMConnectedTo(Node x, Node y, Set<Node> z, boolean excludeSelectionBias)
      Determmines whether x and y are d-connected given z.
      Parameters:
      x - a Node object
      y - a Node object
      z - a Set object
      excludeSelectionBias - 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 excludeSelectionBias)
      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.
      excludeSelectionBias - If true, selection bias is excluded; undirected edges should NOT be interpreted as potential selection edges. If false, selection bias is allowed and undirected edges may represent selection effects (PAG semantics).
      Returns:
      true if the path is m-connecting; false otherwise.

    • isMConnectingPath

      public boolean isMConnectingPath(List<Node> path, Set<Node> conditioningSet, Map<Node, Set<Node>> ancestors, boolean excludeSelectionBias)
      Checks if the given path is an m-connecting path and doens't contain duplicate nodes.
      Parameters:
      path - The path to check.
      conditioningSet - The set of nodes to check reachability against.
      ancestors - The ancestors of each node in the graph.
      excludeSelectionBias - 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.

    • defVisiblePag

      public boolean defVisiblePag(Node A, Node B)
      Returns true if the edge form A to B is a definitely visible edge in a PAG.
      Parameters:
      A - The one node.
      B - The other node.
      Returns:
      True if so.

    • 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; also false if either node has no same-named node in this graph.

    • 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

    • existsPotentiallyDirectedPath

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

      existsPotentiallyDirectedPath.

      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 excludeSelectionBias)
      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.
      excludeSelectionBias - 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 X, Node Y, String graphType, int maxNumSets, int maxRadius, int nearWhichEndpoint, int maxPathLength, String colliderPolicy)
      Computes the adjustment sets needed to estimate the causal effect of node X on node Y in a given graph structure under specified parameters.
      Parameters:
      X - The node representing the cause in the causal relationship.
      Y - The node representing the effect in the causal relationship.
      graphType - The type of the graph (e.g., DAG, MAG, etc.).
      maxNumSets - The maximum number of adjustment sets to return.
      maxRadius - The maximum distance from an endpoint to look for adjustment-set variables.
      nearWhichEndpoint - TThe which endpoint to find adjustment sets near, 1 = source, 2 = target, 3 = both.
      maxPathLength - The maximum allowable length of causal paths considered.
      colliderPolicy - A string determining the collider policy for adjustment set computation. Values may be "OFF", "PREFER_NONCOLLIDERS", or "NONCOLLIDER_FIRST".
      Returns:
      A list of sets of nodes, each set representing a valid adjustment set for the causal effect estimation.

    • adjustmentSets

      public List<Set<Node>> adjustmentSets(Node X, Node Y, String graphType, int maxNumSets, int maxRadius, int nearWhichEndpoint, int maxPathLength, String colliderPolicy, boolean henckelPruning)
      Computes the adjustment sets needed to estimate the causal effect of node X on node Y in a given graph structure under specified parameters.
      Parameters:
      X - The node representing the cause in the causal relationship.
      Y - The node representing the effect in the causal relationship.
      graphType - The type of the graph (e.g., DAG, MAG, etc.).
      maxNumSets - The maximum number of adjustment sets to return.
      maxRadius - The maximum distance from an endpoint to look for adjustment-set variables.
      nearWhichEndpoint - TThe which endpoint to find adjustment sets near, 1 = source, 2 = target, 3 = both.
      maxPathLength - The maximum allowable length of causal paths considered.
      colliderPolicy - A string determining the collider policy for adjustment set computation. Values may be "OFF", "PREFER_NONCOLLIDERS", or "NONCOLLIDER_FIRST".
      henckelPruning - whether to use Henckel pruning during adjustment set computation.
      Returns:
      A list of sets of nodes, each set representing a valid adjustment set for the causal effect estimation.

    • adjustmentSets

      public List<Set<Node>> adjustmentSets(Node X, Node Y, String graphType, int maxNumSets, int maxRadius, int nearWhichEndpoint, int maxPathLength)
      Computes and returns a list of adjustment sets for given nodes and parameters. Adjustment sets are used in causal inference to determine sets of variables that need to be conditioned on to block backdoor paths. Assumes the collider policy is "OFF".
      Parameters:
      X - the source node in the causal graph
      Y - the target node in the causal graph
      graphType - the type of graph being used (e.g., DAG, MAG, PAG)
      maxNumSets - the maximum number of adjustment sets to return
      maxRadius - the maximum distance from endpoint to look for adjsutment sets
      nearWhichEndpoint - The which endpoint to find adjustment sets near, 1 = source, 2 = target, 3 = both.
      maxPathLength - the maximum length of paths to consider in the graph
      Returns:
      a list of sets of nodes, where each set represents an adjustment set that can be used to block backdoor paths between X and Y

    • adjustmentSets

      public List<Set<Node>> adjustmentSets(Node X, Node Y, String graphType, int maxNumSets, int maxRadius, int nearWhichEndpoint, int maxPathLength, boolean henckelPruning, boolean oSetCompatible)
      Computes and returns a list of adjustment sets for given nodes and parameters. Adjustment sets are used in causal inference to determine sets of variables that need to be conditioned on to block backdoor paths. Assumes the collider policy is "OFF".
      Parameters:
      X - the source node in the causal graph
      Y - the target node in the causal graph
      graphType - the type of graph being used (e.g., DAG, MAG, PAG)
      maxNumSets - the maximum number of adjustment sets to return
      maxRadius - the maximum distance from endpoint to look for adjsutment sets
      nearWhichEndpoint - The which endpoint to find adjustment sets near, 1 = source, 2 = target, 3 = both.
      maxPathLength - the maximum length of paths to consider in the graph
      henckelPruning - whether to use Henckel pruning during adjustment set computation
      oSetCompatible - whether to use O-set compatibility during adjustment set computation
      Returns:
      a list of sets of nodes, where each set represents an adjustment set that can be used to block backdoor paths between X and Y

    • getBackdoorPaths

      public Set<List<Node>> getBackdoorPaths(Node X, Node Y, String graphType, int maxPathLength)
      Finds and returns all valid backdoor paths between two nodes in a graph. A backdoor path is a path that satisfies certain conditions based on the graph type and causal inference principles. The method supports PDAG, MAG, and PAG graph types.
      Parameters:
      X - the starting node of the path
      Y - the target node to which backdoor paths are sought
      graphType - the type of graph, must be one of "PDAG", "MAG", or "PAG"
      maxPathLength - the maximum number of edges allowed in a path, -1 for no limit
      Returns:
      a set of all valid backdoor paths, where each path is represented as a list of nodes; returns an empty set if no valid backdoor paths are found
      Throws:
      IllegalArgumentException - if the provided graphType is invalid

    • isAcyclic

      public boolean isAcyclic()
      Determines whether the graph is acyclic, meaning it does not contain any directed cycles.
      Returns:
      true if the graph is acyclic; false otherwise

    • isMaximal

      public boolean isMaximal()
      Determines if the current graph configuration is maximal. A graph configuration is considered maximal if for every pair of non-adjacent nodes, there does not exist an inducing path between them considering the selected nodes.
      Returns:
      true if the graph configuration is maximal, otherwise false.

    • isGraphAmenable

      public boolean isGraphAmenable(Node node1, Node node2, String graphType, int maxLengthAdjustment, Set<Node> forceVisibility)
      Determines if the graph is amenable based on the provided nodes, graph type, and maximum allowable length adjustment.
      Parameters:
      node1 - the first node to be evaluated within the graph
      node2 - the second node to be evaluated within the graph
      graphType - the type of graph to be considered for the operation
      maxLengthAdjustment - the maximum allowed adjustment to the length in the graph evaluation
      forceVisibility - whether to force visibility during the graph evaluation
      Returns:
      true if the graph meets the amenability criteria based on the nodes, graph type, and length adjustment; false otherwise