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.

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

Constructor Summary

Constructors

Constructor	Description
GraphSearchUtils()

Method Summary

Modifier and Type	Method	Description
static void	arrangeByKnowledgeTiers(Graph graph)
static void	arrangeByKnowledgeTiers(Graph graph, Knowledge knowledge)
static void	basicCpdag(Graph graph)	Get a graph and direct only the unshielded colliders.
static void	basicCpdagRestricted2(Graph graph, Node node)
static GraphSearchUtils.CpcTripleType	getCpcTripleType(Node x, Node y, Node z, IndependenceTest test, int depth, Graph graph)
static String	getEdgewiseComparisonString(String trueGraphName, Graph trueGraph, String targetGraphName, Graph targetGraph)
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)
static int[][]	graphComparison(Graph trueCpdag, Graph estCpdag, PrintStream out)
static boolean	isArrowheadAllowed(Object from, Object to, Knowledge knowledge)	Checks if an arrowhead is allowed by background knowledge.
static GraphSearchUtils.LegalPagRet	isLegalPag(Graph 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)	Orients according to background knowledge.
static List<Set<Node>>	powerSet(List<Node> nodes)
static int	structuralHammingDistance(Graph trueGraph, Graph estGraph)	Tsamardinos, I., Brown, L.
static Node	translate(String a, List<Node> nodes)

Methods inherited from class java.lang.Object

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

Constructor Details

GraphSearchUtils

public GraphSearchUtils()

Method Details

pcOrientbk

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

Orients according to background knowledge.

pcdOrientC

public 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).

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}).

isArrowheadAllowed

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

Checks if an arrowhead is allowed by background knowledge.

basicCpdag

public static void basicCpdag(Graph graph)

Get a graph and direct only the unshielded colliders.

basicCpdagRestricted2

public static void basicCpdagRestricted2(Graph graph,
 Node node)

isLegalPag

public static GraphSearchUtils.LegalPagRet isLegalPag(Graph pag)

arrangeByKnowledgeTiers

public static void arrangeByKnowledgeTiers(Graph graph,
 Knowledge knowledge)

arrangeByKnowledgeTiers

public static void arrangeByKnowledgeTiers(Graph graph)

getReachableNodes

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

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

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)

Returns:

the string in nodelist which matches string in BK.

powerSet

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

getCpcTripleType

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

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.

getGraphComparison

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

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

getEdgewiseComparisonString

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

graphComparison

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