Class GraphSearchUtils

java.lang.Object

edu.cmu.tetrad.search.utils.GraphSearchUtils

public final class GraphSearchUtils
extends Object

Provides some graph utilities for search algorithm.

Version:

$Id: $Id

Author:

josephramsey

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static enum	GraphSearchUtils.CpcTripleType	Gives the options for triple type for a conservative unshielded collider orientation, which may be "collider" or "noncollider" or "ambiguous".

Method Summary

Modifier and Type	Method	Description
static void	basicCpdag(Graph graph)	Get a graph and direct only the unshielded colliders.
static void	basicCpdagRestricted2(Graph graph, Node node)	basicCpdagRestricted2.
static List<Integer>	getAllRows(int sampleSize)	Returns a list of rows 1...sampleSize.
static GraphSearchUtils.CpcTripleType	getCpcTripleType(Node x, Node y, Node z, IndependenceTest test, int depth, Graph graph)	getCpcTripleType.
static String	getEdgewiseComparisonString(String trueGraphName, Graph trueGraph, String targetGraphName, Graph targetGraph)	getEdgewiseComparisonString.
static GraphUtils.GraphComparison	getGraphComparison(Graph trueGraph, Graph targetGraph)	Just counts arrowhead errors--for cyclic edges counts an arrowhead at each node.
static Set<Node>	getReachableNodes(List<Node> initialNodes, LegalPairs legalPairs, List<Node> c, List<Node> d, Graph graph, int maxPathLength)	getReachableNodes.
static int[][]	graphComparison(Graph trueCpdag, Graph estCpdag, PrintStream out)	graphComparison.
static boolean	isArrowheadAllowed(Object from, Object to, Knowledge knowledge)	Checks if an arrowhead is allowed by background knowledge.
static boolean	isLatentVariableAlgorithmByAnnotation(Algorithm algorithm)	Checks if the provided algorithm is a latent variable algorithm by inspecting the associated annotation.
static void	orientCollidersUsingSepsets(SepsetMap set, Knowledge knowledge, Graph graph, boolean verbose, boolean enforceCpdag)	Step C of PC; orients colliders using specified sepset.
static void	pcdOrientC(IndependenceTest test, Knowledge knowledge, Graph graph)	Performs step C of the algorithm, as indicated on page xxx of CPS, with the modification that X--W--Y is oriented as X-->W<--Y if W is *determined by* the sepset of (X, Y), rather than W just being *in* the sepset of (X, Y).
static void	pcOrientbk(Knowledge bk, Graph graph, List<Node> nodes, boolean verbose)	Orients according to background knowledge.
static List<Set<Node>>	powerSet(List<Node> nodes)	powerSet.
static void	repositionLatents(Graph graph)	Repositions each latent node to the average (x, y) location of its adjacent measured nodes (parents and children combined).
static <T> T	runWithTimeout(Callable<T> task, long timeout, TimeUnit unit)	Runs the given task with the given timeout.
static int	structuralhammingdistance(Graph trueGraph, Graph estGraph, boolean useTrueCpdag)	Originally, Tsamardinos, I., Brown, L.
static Node	translate(String a, List<Node> nodes)	translate.

Methods inherited from class Object

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

Method Details

pcOrientbk

public static void pcOrientbk(Knowledge bk,
 Graph graph,
 List<Node> nodes,
 boolean verbose)

Orients according to background knowledge.

Parameters:

bk - a Knowledge object

graph - a Graph object

nodes - a List object

verbose - Whether to print verbose output.

pcdOrientC

public static void pcdOrientC(IndependenceTest test,
 Knowledge knowledge,
 Graph graph)
                       throws InterruptedException

Performs step C of the algorithm, as indicated on page xxx of CPS, with the modification that X--W--Y is oriented as X-->W<--Y if W is *determined by* the sepset of (X, Y), rather than W just being *in* the sepset of (X, Y).

Parameters:

test - a IndependenceTest object

knowledge - a Knowledge object

graph - a Graph object

Throws:

InterruptedException - if any.

orientCollidersUsingSepsets

public static void orientCollidersUsingSepsets(SepsetMap set,
 Knowledge knowledge,
 Graph graph,
 boolean verbose,
 boolean enforceCpdag)

Step C of PC; orients colliders using specified sepset. That is, orients x *-* y *-* z as x *-> y <-* z just in case y is in Sepset({x, z}).

Parameters:

set - a SepsetMap object

knowledge - a Knowledge object

graph - a Graph object

verbose - a boolean

enforceCpdag - a boolean

isArrowheadAllowed

public static boolean isArrowheadAllowed(Object from,
 Object to,
 Knowledge knowledge)

Checks if an arrowhead is allowed by background knowledge.

Parameters:

from - a Object object

to - a Object object

knowledge - a Knowledge object

Returns:

a boolean

basicCpdag

public static void basicCpdag(Graph graph)

Get a graph and direct only the unshielded colliders.

Parameters:

graph - a Graph object

basicCpdagRestricted2

public static void basicCpdagRestricted2(Graph graph,
 Node node)

basicCpdagRestricted2.

Parameters:

graph - a Graph object

node - a Node object

getReachableNodes

public static Set<Node> getReachableNodes(List<Node> initialNodes,
 LegalPairs legalPairs,
 List<Node> c,
 List<Node> d,
 Graph graph,
 int maxPathLength)

getReachableNodes.

Parameters:

initialNodes - The nodes that reachability undirectedPaths start from.

legalPairs - Specifies initial edges (given initial nodes) and legal edge pairs.

c - a set of vertices (intuitively, the set of variables to be conditioned on.

d - a set of vertices (intuitively to be used in tests of legality, for example, the set of ancestors of c).

graph - the graph with respect to which reachability is

maxPathLength - the maximum length of a path to be considered.

Returns:

the set of nodes reachable from the given set of initial nodes in the given graph according to the criteria in the given legal pairs object.

A variable v is reachable from initialNodes iff for some variable X in initialNodes thers is a path U [X, Y1, ..., v] such that legalPairs.isLegalFirstNode(X, Y1) and for each [H1, H2, H3] as subpaths of U, legalPairs.isLegalPairs(H1, H2, H3).

The algorithm used is a variant of Algorithm 1 from Geiger, Verma, and Pearl (1990).

translate

public static Node translate(String a,
 List<Node> nodes)

translate.

Parameters:

a - a String object

nodes - a List object

Returns:

the string in nodelist which matches string in BK.

powerSet

public static List<Set<Node>> powerSet(List<Node> nodes)

powerSet.

Parameters:

nodes - a List object

Returns:

a List object

getCpcTripleType

public static GraphSearchUtils.CpcTripleType getCpcTripleType(Node x,
 Node y,
 Node z,
 IndependenceTest test,
 int depth,
 Graph graph)
                                                       throws InterruptedException

getCpcTripleType.

Parameters:

x - a Node object

y - a Node object

z - a Node object

test - a IndependenceTest object

depth - a int

graph - a Graph object

Returns:

a GraphSearchUtils.CpcTripleType object

Throws:

InterruptedException - if any.

structuralhammingdistance

public static int structuralhammingdistance(Graph trueGraph,
 Graph estGraph,
 boolean useTrueCpdag)

Originally, Tsamardinos, I., Brown, L. E., and Aliferis, C. F. (2006). The max-min hill-climbing Bayesian network structure learning algorithm. Machine learning, 65(1), 31-78.

But using the formulation in Peters, J., & Bühlmann, P. (2015). Structural intervention distance for evaluating causal graphs. Neural computation, 27(3), 771-799.

Converts each graph (DAG or CPDAG) into its CPDAG before scoring.

Parameters:

trueGraph - a Graph object

estGraph - a Graph object

useTrueCpdag - Use the CPDAG of the true graph.

Returns:

a int

getGraphComparison

public static GraphUtils.GraphComparison getGraphComparison(Graph trueGraph,
 Graph targetGraph)

Just counts arrowhead errors--for cyclic edges counts an arrowhead at each node.

Parameters:

trueGraph - a Graph object

targetGraph - a Graph object

Returns:

a GraphUtils.GraphComparison object

getEdgewiseComparisonString

public static String getEdgewiseComparisonString(String trueGraphName,
 Graph trueGraph,
 String targetGraphName,
 Graph targetGraph)

getEdgewiseComparisonString.

Parameters:

trueGraphName - a String object

trueGraph - a Graph object

targetGraphName - a String object

targetGraph - a Graph object

Returns:

a String object

graphComparison

public static int[][] graphComparison(Graph trueCpdag,
 Graph estCpdag,
 PrintStream out)

graphComparison.

Parameters:

trueCpdag - a Graph object

estCpdag - a Graph object

out - a PrintStream object

Returns:

an array of objects

isLatentVariableAlgorithmByAnnotation

public static boolean isLatentVariableAlgorithmByAnnotation(Algorithm algorithm)

Checks if the provided algorithm is a latent variable algorithm by inspecting the associated annotation.

Parameters:

algorithm - The algorithm to check.

Returns:

true if the algorithm is a latent variable algorithm, false otherwise.

Throws:

NullPointerException - if the algorithm is null.

RuntimeException - if there is an error in getting the algorithm type from the annotation.

runWithTimeout

public static <T> T runWithTimeout(Callable<T> task,
 long timeout,
 TimeUnit unit)

Runs the given task with the given timeout.

Type Parameters:

T - The type of the result.

Parameters:

task - The task to run.

timeout - The timeout.

unit - The time unit of the timeout.

Returns:

The result of the task, or null if the task times out.

getAllRows

public static List<Integer> getAllRows(int sampleSize)

Returns a list of rows 1...sampleSize.

Parameters:

sampleSize - the number of rows in the dataset.

Returns:

a list of rows 1...sampleSize.

repositionLatents

public static void repositionLatents(Graph graph)

Repositions each latent node to the average (x, y) location of its adjacent measured nodes (parents and children combined). Latents that have no measured neighbors are left where they are.

A single pass is sufficient for tree-shaped latent structures; for graphs where latents are adjacent to other latents, iterating until convergence gives a better result.

Parameters:

graph - the graph whose latent nodes are to be repositioned; mutated in place