Package edu.cmu.tetrad.search.utils

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".
static class	GraphSearchUtils.LegalMagRet	Stores a result for checking whether a graph is a legal MAG--(a) whether it is (a boolean), and (b) the reason why it is not, if it is not (a String).
static class	GraphSearchUtils.LegalPagRet	Stores a result for checking whether a graph is a legal PAG--(a) whether it is (a boolean), and (b) the reason why it is not, if it is not (a String).

Method Summary

Modifier and Type	Method	Description
static void	arrangeByKnowledgeTiers(Graph graph)	arrangeByKnowledgeTiers.
static void	arrangeByKnowledgeTiers(Graph graph, Knowledge knowledge)	arrangeByKnowledgeTiers.
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 GraphSearchUtils.LegalMagRet	isLegalMag(Graph mag, Set<Node> selection)	Determines whether the given graph is a legal Mixed Ancestral Graph (MAG).
static GraphSearchUtils.LegalPagRet	isLegalPag(Graph pag, Set<Node> selection)	Checks if the provided Directed Acyclic Graph (PAG) is a legal PAG.
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 <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)	Tsamardinos, I., Brown, L.
static Node	translate(String a, List<Node> nodes)	translate.

Methods inherited from class java.lang.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

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

isLegalPag

public static GraphSearchUtils.LegalPagRet isLegalPag(Graph pag,
 Set<Node> selection)

Checks if the provided Directed Acyclic Graph (PAG) is a legal PAG.

Parameters:

pag - The Directed Acyclic Graph (PAG) to be checked

selection - The set of nodes to be conditioned on

Returns:

A LegalPagRet object indicating whether the PAG is legal or not, along with a reason if it is not legal.

isLegalMag

public static GraphSearchUtils.LegalMagRet isLegalMag(Graph mag,
 Set<Node> selection)

Determines whether the given graph is a legal Mixed Ancestral Graph (MAG).

Parameters:

mag - the graph to be checked

selection - the set of nodes to be conditioned on

Returns:

a LegalMagRet object indicating whether the graph is legal and providing an error message if it is not

arrangeByKnowledgeTiers

public static void arrangeByKnowledgeTiers(Graph graph,
 Knowledge knowledge)

arrangeByKnowledgeTiers.

Parameters:

graph - a Graph object

knowledge - a Knowledge object

arrangeByKnowledgeTiers

public static void arrangeByKnowledgeTiers(Graph graph)

arrangeByKnowledgeTiers.

Parameters:

graph - a Graph 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

structuralHammingDistance

public static int structuralHammingDistance(Graph trueGraph,
 Graph estGraph)

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.

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

Parameters:

trueGraph - a Graph object

estGraph - a Graph object

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.