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:

• Serialized Form

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	Description
void	addTriple(Node x, Node b, Node y)	Adds a triple consisting of three given nodes to the data structure.
static @NotNull Map<Node,Set<Edge>>	getBMap(Graph pag)	Returns a map of nodes to bidirected edges for them.
Set<Triple>	getTriple(Node y)	Returns the set of triples for the given node.
void	recallUnshieldedTriples(Graph pag)	Recalls unshielded triples in the given graph.
boolean	removeAlmostCycles(Graph pag)	Removes almost cycles from the Graph.
boolean	removeCycles(Graph pag)	Removes cycles from the Graph.
Set<Node>	tKeys()	Returns the set of nodes that are keys in the map of triples.
boolean	tripleAllowed(Node x, Node b, Node z)	Determines whether a triple consisting of three given nodes is allowed.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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.