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
See Also:

  • Constructor Details

    • Paths

      public Paths(Graph graph)

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

    • maxCliques

      public Set<Set<Node>> maxCliques()

    • connectedComponents

      public List<List<Node>> connectedComponents()
      Returns:
      the connected components of the given graph, as a list of lists of nodes.

    • directedPathsFromTo

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

    • semidirectedPathsFromTo

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

    • allPathsFromTo

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

    • allDirectedPathsFromTo

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

    • treks

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

    • treksIncludingBidirected

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

    • existsDirectedPathFromTo

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

    • existsSemiDirectedPath

      public boolean existsSemiDirectedPath(Node from, Node to)

    • isMConnectedTo

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

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

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

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

    • getInducingPath

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

    • possibleMsep

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

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

    • getSepset

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

    • isMConnectedTo

      public boolean isMConnectedTo(Node x, Node y, Set<Node> z)
      Detemrmines whether x and y are d-connected given z.
      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.
      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
      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()

    • existsDirectedPathFromTo

      public boolean existsDirectedPathFromTo(Node node1, Node node2)
      Returns:
      true iff there is a (nonempty) directed path from node1 to node2. a

    • existsSemiDirectedPath

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

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

    • getDescendants

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

    • isAncestorOf

      public boolean isAncestorOf(Node node1, Node node2)
      Determines whether one node is an ancestor of another.

    • getAncestors

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

    • isDescendentOf

      public boolean isDescendentOf(Node node1, Node node2)
      Determines whether one node is a descendent of another.

    • definiteNonDescendent

      public boolean definiteNonDescendent(Node node1, Node node2)
      added by ekorber, 2004/06/12
      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)

    • isDirectedFromTo

      public boolean isDirectedFromTo(Node node1, Node node2)

    • isUndirectedFromTo

      public boolean isUndirectedFromTo(Node node1, Node node2)

    • possibleAncestor

      public boolean possibleAncestor(Node node1, Node node2)