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

    • allPaths

      public List<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.

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

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

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

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

      getSepset.

      Parameters:
      x - a Node object
      y - a Node object
      Returns:
      a Set object

    • isMConnectedTo

      public boolean isMConnectedTo(Node x, Node y, Set<Node> z, 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
      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.

    • 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)
      added by ekorber, 2004/06/11
      Parameters:
      edge - a Edge object
      Returns:
      true if the given edge is definitely visible (Jiji, pg 25)
      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