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:

  • 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 maxLength)
      Finds all paths from node1 to node2 within a specified maximum length.
      Parameters:
      node1 - The starting node.
      node2 - The target node.
      maxLength - 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

    • getAncestorMap

      public Map<Node,Set<Node>> getAncestorMap()
      Return a map from each node to its 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

    • existsInducingPath

      public boolean existsInducingPath(Node x, Node y)
      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.
      Returns:
      true if an inducing path exists, false if not.

    • existsInducingPathVisit

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

      existsInducingPathVisit.

      Parameters:
      a - a Node object
      b - a Node object
      x - a Node object
      y - a Node object
      path - a LinkedList object
      Returns:
      a boolean

    • getInducingPath

      public List<Node> getInducingPath(Node x, Node y)
      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
      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

    • possibleMsep

      public List<Node> possibleMsep(Node x, Node y, int maxPathLength)

      possibleMsep.

      Parameters:
      x - a Node object
      y - a Node object
      maxPathLength - a int
      Returns:
      a List object

    • removeByPossibleMsep

      public void removeByPossibleMsep(IndependenceTest test, SepsetMap sepsets)
      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.

    • 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, IndependenceTest test)
      Retrieves the sepset (a set of nodes) between two given nodes. The sepset is the minimal set of nodes that need to be conditioned on in order to render two nodes conditionally independent.
      Parameters:
      x - the first node
      y - the second node
      containing - the set of nodes that the sepset must contain
      test - the independence test to use
      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 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.
      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.

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

    • 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

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