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

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

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

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

    • directedPathsFromTo

      public List<List<Node>> directedPathsFromTo(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

    • semidirectedPathsFromTo

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

      semidirectedPathsFromTo.

      Parameters:
      node1 - a Node object
      node2 - a Node object
      maxLength - a int
      Returns:
      a List object

    • allPathsFromTo

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

      allPathsFromTo.

      Parameters:
      node1 - a Node object
      node2 - a Node object
      maxLength - a int
      Returns:
      a List object

    • allDirectedPathsFromTo

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

      allDirectedPathsFromTo.

      Parameters:
      node1 - a Node object
      node2 - a Node object
      maxLength - a int
      Returns:
      a List object

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

    • existsDirectedPathFromTo

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

      existsDirectedPathFromTo.

      Parameters:
      node1 - a Node object
      node2 - a Node object
      depth - a int
      Returns:
      a boolean

    • existsSemiDirectedPath

      public boolean existsSemiDirectedPath(Node from, Node to)

      existsSemiDirectedPath.

      Parameters:
      from - a Node object
      to - a Node object
      Returns:
      a boolean

    • isMConnectedTo

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

      isMConnectedTo.

      Parameters:
      x - a Set object
      y - a Set object
      z - a Set object
      Returns:
      a boolean

    • isMConnectedTo

      public boolean isMConnectedTo(Set<Node> x, Set<Node> y, Set<Node> z, Map<Node,Set<Node>> ancestorMap)
      Checks to see if x and y are d-connected given z.
      Parameters:
      x - a Set object
      y - a Set object
      z - a Set object
      ancestorMap - A map of nodes to their ancestors.
      Returns:
      True if x and y are d-connected given z.

    • getMConnectedVars

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

      getMConnectedVars.

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

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

      getInducingPath.

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

    • 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.
      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)
      Detemrmines whether x and y are d-connected given z.
      Parameters:
      x - a Node object
      y - a Node object
      z - a Set object
      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)
      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
      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

    • existsDirectedPathFromTo

      public boolean existsDirectedPathFromTo(Node node1, Node node2)

      existsDirectedPathFromTo.

      Parameters:
      node1 - a Node object
      node2 - a Node object
      Returns:
      true iff there is a (nonempty) directed path from node1 to node2. a

    • 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 List<Node> getDescendants(List<Node> nodes)

      getDescendants.

      Parameters:
      nodes - a List object
      Returns:
      a List object

    • 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(List<Node> nodes)

      getAncestors.

      Parameters:
      nodes - a List object
      Returns:
      a List object

    • 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)
      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.
      Parameters:
      node1 - the first node.
      node2 - the second node.
      z - the conditioning set.
      Returns:
      true if node1 is d-separated from node2 given set t, false if not.
      See Also:

    • isMSeparatedFrom

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

      isMSeparatedFrom.

      Parameters:
      node1 - a Node object
      node2 - a Node object
      z - a Set object
      ancestors - a Map object
      Returns:
      a boolean

    • isDirectedFromTo

      public boolean isDirectedFromTo(Node node1, Node node2)

      isDirectedFromTo.

      Parameters:
      node1 - a Node object
      node2 - a Node object
      Returns:
      a boolean

    • isUndirectedFromTo

      public boolean isUndirectedFromTo(Node node1, Node node2)

      isUndirectedFromTo.

      Parameters:
      node1 - a Node object
      node2 - a Node object
      Returns:
      a boolean

    • possibleAncestor

      public boolean possibleAncestor(Node node1, Node node2)

      possibleAncestor.

      Parameters:
      node1 - a Node object
      node2 - a Node object
      Returns:
      a boolean