Package edu.cmu.tetrad.search.utils

Class AlmostCycleRemover

java.lang.Object
edu.cmu.tetrad.search.utils.AlmostCycleRemover
All Implemented Interfaces:
TetradSerializable, Serializable
public class AlmostCycleRemover extends Object implements TetradSerializable
A class for heuristically removing almost cycles from a PAG to avoid unfaithfulness in an estimated PAG. An almost cycle is a path x ~~> y where x <-> y. Bidirected edge semantics for PAGs require that there be no almost directed cycles, though LV algorithms may produce them.

This class is meant to be incorporated into a latent variable algorithm and used to remove almost cycles from the graph in the final step.

The method works by identifying almost cyclic paths for x <-> y where there is a semidirected path from x to y in the estimated PAG and then removing all unshielded collider orientations into x for these. This removes the need to orient a collider at x for these edges, and so removes the need to orient a path out of x to y. Almost directed paths are symptomatic of unfaithfulness in the data (implying dependencies that should not exist if the output is a faithful PAG), so this is a reasonable heuristic.

Author:
jdramsey
See Also:

  • Constructor Details

    • AlmostCycleRemover

      public AlmostCycleRemover()
      Constructs a new instance of the AlmostCycleRemover class with the specified Graph.

  • Method Details

    • getBMap

      @NotNull public static @NotNull Map<Node,Set<Edge>> getBMap(Graph pag)
      Returns a map of nodes to bidirected edges for them.
      Parameters:
      pag - The Graph to be reoriented.
      Returns:
      a map of nodes to bidirected edges for them.

    • addTriple

      public void addTriple(Node x, Node b, Node y)
      Adds a triple consisting of three given nodes to the data structure. This should be a triple x, b, y where x and y are adjacent to b and oriented into y, and x and y are non-adjacent.
      Parameters:
      x - the first node
      b - the second node
      y - the third node
      Throws:
      IllegalArgumentException - if the nodes are not distinct

    • removeAlmostCycles

      public boolean removeAlmostCycles(Graph pag)
      Removes almost cycles from the Graph. An almost cycle is a path x ~~> y where x <-> y.
      Parameters:
      pag - The Graph to be reoriented.
      Returns:
      true if almost cycles were removed; false otherwise

    • removeCycles

      public boolean removeCycles(Graph pag)
      Removes cycles from the Graph. A cycle is a path x ~~> x.
      Parameters:
      pag - The Graph to be reoriented.
      Returns:
      true if cycles were removed; false otherwise

    • tripleAllowed

      public boolean tripleAllowed(Node x, Node b, Node z)
      Determines whether a triple consisting of three given nodes is allowed. This should be a triple x, b, z where x and z are adjacent to b and oriented into z, and x and z are non-adjacent.
      Parameters:
      x - the first node
      b - the second node
      z - the third node
      Returns:
      true if the triple is allowed; false otherwise

    • tKeys

      public Set<Node> tKeys()
      Returns the set of nodes that are keys in the map of triples.
      Returns:
      the set of nodes that are keys in the map of triples

    • getTriple

      public Set<Triple> getTriple(Node y)
      Returns the set of triples for the given node.
      Parameters:
      y - the node
      Returns:
      the set of triples for the given node

    • recallUnshieldedTriples

      public void recallUnshieldedTriples(Graph pag)
      Recalls unshielded triples in the given graph.
      Parameters:
      pag - The graph from which unshielded triples should be recalled.