Package edu.cmu.tetrad.graph

Class GraphUtils

java.lang.Object

edu.cmu.tetrad.graph.GraphUtils

public final class GraphUtils
extends Object

Utility class for working with graphs.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	GraphUtils.GraphComparison	Represents a comparison between two graphs.
static enum	GraphUtils.GraphType	The GraphType enum represents the types of graphs that can be used in the application.
static class	GraphUtils.TwoCycleErrors	Two-cycle errors.

Method Summary

Modifier and Type	Method	Description
static void	addEdgeSpecializationMarkup(Graph graph)	Adds markups for edge specializations for the edges in the given graph.
static void	addForbiddenReverseEdgesForDirectedEdges(Graph graph, Knowledge knowledge)	Adds forbidden reverse edges for directed edges in the given graph based on the knowledge.
static Set<Node>	anteriority(Graph G, Node... x)	Computes the anteriority of the given nodes in a graph.
static @NotNull List<Integer>	asList(int[] choice)	Creates a new list containing the elements of the given array.
static List<Node>	asList(int[] indices, List<Node> nodes)	Constructs a list of nodes from the given nodes list at the given indices in that list.
static Set<Node>	asSet(int[] indices, List<Node> nodes)	Converts an array of indices into a set of corresponding nodes from a given list of nodes.
static Set<Node>	asSet(Node... nodes)	Converts the given array of nodes into a Set of nodes.
static Graph	bidirectedToUndirected(Graph graph)	Converts a bidirected graph to an undirected graph.
static boolean	colliderAllowed(Graph pag, Node x, Node b, Node y, Knowledge knowledge)	Determines if the collider is allowed.
static boolean	compatible(Edge edge1, Edge edge2)	Determines if two edges are compatible.
static Graph	completeGraph(Graph graph)	completeGraph.
static boolean	containsBidirectedEdge(Graph graph)	Checks if a given graph contains a bidirected edge.
static Graph	convert(String spec)	Converts a string spec of a graph--for example, "X1-->X2, X1---X3, X2o->X4, X3<->X4" to a Graph.
static int	countAdjErrors(Graph graph1, Graph graph2)	Counts the adjacencies that are in graph1 but not in graph2.
static int	degree(Graph graph)	Calculates the maximum degree of a graph.
static boolean	distinct(Node... n)	Determines whether three Node objects are distinct.
static Set<Node>	district(Node x, Graph G)	Calculates the district of a given node in a graph.
static void	doRequiredOrientations(FciOrient fciOrient, Graph pag, List<Node> best, Knowledge knowledge, boolean verbose)	Orient required edges in PAG.
static Set<Node>	dsep(Node x, Node y, Graph G)	Returns D-SEP(x, y) for a MAG G.
static Set<Node>	dsep0(Node x, Node y, Graph G)	Returns D-SEP(x, y) for a MAG G (or inducing path graph G, as in Causation, Prediction and Search).
static Set<Node>	dsep2(Node x, Node y, Graph G)	Returns D-SEP(x, y) for a MAG G.
static Set<Node>	dsepReachability(Node x, Node y, Graph G)	Returns D-SEP(x, y) for a MAG G.
static int[][]	edgeMisclassificationCounts(Graph leftGraph, Graph topGraph, boolean print)	Computes the misclassification counts for each edge in the given graphs.
static String	edgeMisclassifications(double[][] counts, NumberFormat nf)	Generates a textual representation of the edge misclassifications based on the provided counts and number format.
static String	edgeMisclassifications(int[][] counts)	Calculates the misclassifications of edges based on the given counts.
static Graph	emptyGraph(int numNodes)	Creates an empty graph with the specified number of nodes.
static void	fciOrientbk(Knowledge knowledge, Graph graph, List<Node> variables)	Attempts to orient the edges in the graph based on the given knowledge.
static List<Triple>	getAmbiguousTriplesFromGraph(Node node, Graph graph)	Retrieves the list of ambiguous triples from the given graph for a given node.
static Node	getAssociatedNode(Node errorNode, Graph graph)	Returns the associated node for the given error node in the specified graph.
static Graph	getComparisonGraph(Graph graph, Parameters params)	Returns a comparison graph based on the specified parameters.
static int	getDegree(Graph graph)	Returns the maximum degree of a graph.
static List<Triple>	getDottedUnderlinedTriplesFromGraph(Node node, Graph graph)	Retrieves the list of dotted and underlined triples from the given graph, with the specified node as the middle node.
static Graph	getGraphWithoutXToY(Graph G, Node x, Node y, GraphUtils.GraphType graphType)	Returns a graph that is obtained by removing the edge from node x to node y from the input graph.
static int	getIndegree(Graph graph)	Calculates the maximum indegree in a given graph.
static String	getIntersectionComparisonString(List<Graph> graphs)	Generates a comparison string for the intersection of multiple graphs.
static Graph	getMarkovBlanketSubgraphWithTargetNode(Graph graph, Node target)	Calculates the subgraph over the Markov blanket of a target node for a DAG, CPDAG, MAG, or PAG.
static int	getNumCoveringAdjacenciesInPag(Graph trueGraph, Graph estGraph)	Returns the number of covering edges in the given estimated partial ancestral graph (PAG) with respect to the given true PAG.
static int	getNumInducedAdjacenciesInPag(Graph trueGraph, Graph estGraph)	Calculates the number of induced adjacencies in the given estiamted Partial Ancestral (PAG) with respect to the given true PAG.
static Node	getTrekSource(Graph graph, List<Node> trek)	This method returns the source node of a given trek in a graph.
static GraphUtils.TwoCycleErrors	getTwoCycleErrors(Graph trueGraph, Graph estGraph)	Returns the TwoCycleErrors object that represents errors for direct feedback loops.
static List<Triple>	getUnderlinedTriplesFromGraph(Node node, Graph graph)	Retrieves the underlined triples from the given graph that involve the specified node.
static void	gfciExtraEdgeRemovalStep(Graph graph, Graph cpdag, List<Node> nodes, SepsetProducer sepsets, int depth, boolean verbose)	The extra-edge removal step for GFCI.
static void	gfciR0(Graph pag, Graph cpdag, SepsetProducer sepsets, Knowledge knowledge, boolean verbose, Set<Triple> unshieldedTriples)	Applies the GFCI-R0 algorithm to orient edges in a pag based on a reference CPDAG, sepsets, and knowledge.
static String	graphAttributesToText(Graph graph, String title)	Converts the attributes of a given graph into a text format.
static String	graphEdgesToText(Graph graph, String title)	Converts the edges of a graph to text representation.
static String	graphNodeAttributesToText(Graph graph, String title, char delimiter)	Converts the attributes of nodes in a graph to text format.
static String	graphNodesToText(Graph graph, String title, char delimiter)	Converts the nodes of a graph to a formatted text representation.
static Graph	guaranteePag(Graph pag, FciOrient fciOrient, Knowledge knowledge, Set<Triple> unshieldedColliders, Set<Triple> extraUnshieldedColliders, boolean verbose, Set<Node> selection)	Guarantees a legal PAG by repairing deviations of a graph from a legal PAG (partial ancestral graph).
static boolean	isClique(Collection<Node> set, Graph graph)	Checks if the given set of nodes forms a clique in the specified graph.
static boolean	isConfoundingTrek(Graph trueGraph, List<Node> trek, Node x, Node y)	Checks if the given trek in a graph is a confounding trek.
static boolean	isCorrectBidirectedEdge(Edge edge, Graph trueGraph)	Determines if the given bidirected edge has a latent confounder in the true graph--that is, whether for X <-> Y there is a latent node Z such that X <- (Z) -> Y.
static boolean	isCoveringAdjacency(Graph trueGraph, Graph estGraph, Node x, Node y)	Determines whether an edge between two nodes in the estimated graph is covering a collider or noncollider in the true graph.
static boolean	isDag(Graph graph)	Determines if the given graph is a directed acyclic graph (DAG).
static LinkedList<Triple>	listColliderTriples(Graph graph)	Generates a list of triples where a node acts as a collider in a given graph.
static double	localMarkovInitializePValues(Graph dag, boolean ensureMarkov, IndependenceTest test, Map<org.apache.commons.lang3.tuple.Pair<Node,Node>,Set<Double>> pValues)	Initializes and evaluates p-values for local Markov properties in a given graph.
static Set<Node>	markovBlanket(Node x, Graph G)	Returns a Markov blanket of a node for a DAG, CPDAG, MAG, or PAG.
static Graph	markovBlanketSubgraph(Node target, Graph graph)	Calculates the subgraph over the Markov blanket of a target node in a given DAG, CPDAG, MAG, or PAG.
static Set<Set<Node>>	maximalCliques(Graph graph, List<Node> nodes)	Finds all maximal cliques in a given graph.
static Graph	nondirectedGraph(Graph graph)	undirectedGraph.
static String	pathString(Graph graph, Node... x)	Generates a string representation of a path in a given graph, starting from the specified nodes.
static String	pathString(Graph graph, List<Node> path, boolean showBlocked)	Constructs a string representation of a path in a graph.
static String	pathString(Graph graph, List<Node> path, Set<Node> conditioningVars)	Returns a string representation of the given path in the graph, considering the conditioning variables.
static String	pathString(Graph graph, List<Node> path, Set<Node> conditioningVars, boolean showBlocked, boolean allowSelectionBias)	Returns a string representation of the given path in the graph, with additional information about conditioning variables.
static double	pValuesAdP(Map<org.apache.commons.lang3.tuple.Pair<Node,Node>,Set<Double>> _pValues)	Calculates the p-value using the Anderson-Darling test for a given set of p-values from an independence test.
static void	recallUnshieldedTriples(Graph pag, Set<Triple> unshieldedColliders, Knowledge knowledge)	Recall unshielded triples in a given graph.
static boolean	removeAlmostCycles(Graph pag, Set<Triple> unshieldedColliders, Set<Triple> extraUnshieldedColliders, FciOrient fciOrient, Knowledge knowledge, boolean verbose)	Removes almost cycles from a graph.
static Graph	removeBidirectedOrientations(Graph estCpdag)	removeBidirectedOrientations.
static boolean	removeCycles(Set<Triple> unshieldedColliders, FciOrient fciOrient, Graph pag, Knowledge knowledge, boolean verbose)	Removes cycles from the given graph using the Fast Causal Inference (FCI) algorithm.
static void	removeNonSkeletonEdges(Graph graph, Knowledge knowledge)	Removes non-skeleton edges from the given graph based on the provided knowledge.
static void	reorientWithCircles(Graph pag, boolean verbose)	Reorients all edges in a Graph as o-o.
static Graph	replaceNodes(Graph originalGraph, List<Node> newVariables)	Converts the given graph, originalGraph, to use the new variables (with the same names as the old).
static List<Node>	replaceNodes(List<Node> originalNodes, Graph graph)	Converts the given list of nodes, originalNodes, to use the replacement nodes for them by the same name in the given graph.
static List<Node>	replaceNodes(List<Node> originalNodes, List<Node> newNodes)	Converts the given list of nodes, originalNodes, to use the new variables (with the same names as the old).
static Graph	restrictToMeasured(Graph graph)	Removes all latent nodes from the graph and returns the modified graph.
static Node	traverseSemiDirected(Node node, Edge edge)	Traverses a semi-directed edge to identify the next node in the traversal.
static Graph	trimGraph(List<Node> targets, Graph graph, int trimmingStyle)	Trims the given graph based on the specified trimming style.
static boolean	triple(Graph graph, Node a, Node b, Node c)	Checks if three nodes are connected in a graph.
static String	triplesToText(Set<Triple> triples, String title)	Converts a set of triples into a formatted string.
static Graph	undirectedGraph(Graph graph)	undirectedGraph.
static Graph	undirectedToBidirected(Graph graph)	Converts an undirected graph to a bidirected graph.
static boolean	unshieldedCollider(Graph graph, Node a, Node b, Node c)	Checks if the given nodes are unshielded colliders when considering the given graph.
static Set<Set<Node>>	visibleEdgeAdjustments1(Graph G, Node x, Node y, int numSmallestSizes, GraphUtils.GraphType graphType)	Calculates visual-edge adjustments given graph G between two nodes x and y that are subsets of MB(X).
static Set<Set<Node>>	visibleEdgeAdjustments3(Graph G, Node x, Node y, int numSmallestSizes, GraphUtils.GraphType graphType)	This method calculates visible-edge adjustments for a given graph, two nodes, a number of smallest sizes, and a graph type.

Methods inherited from class java.lang.Object

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

Method Details

getAssociatedNode

public static Node getAssociatedNode(Node errorNode,
 Graph graph)

Returns the associated node for the given error node in the specified graph.

Parameters:

errorNode - The error node for which the associated node needs to be retrieved.

graph - The graph in which to search for the associated node.

Returns:

The associated node of the error node.

Throws:

IllegalArgumentException - If the error node is not of type ERROR or if it does not have exactly one child.

isClique

public static boolean isClique(Collection<Node> set,
 Graph graph)

Checks if the given set of nodes forms a clique in the specified graph.

Parameters:

set - the collection of nodes to be checked

graph - the graph in which the nodes are located

Returns:

true if the given set forms a clique, false otherwise

markovBlanketSubgraph

public static Graph markovBlanketSubgraph(Node target,
 Graph graph)

Calculates the subgraph over the Markov blanket of a target node in a given DAG, CPDAG, MAG, or PAG. Target Node is not included in the result graph's nodes list. Edges including the target node is included in the result graph's edges list.

Parameters:

target - a node in the given graph.

graph - a DAG, CPDAG, MAG, or PAG.

Returns:

a Graph object

getMarkovBlanketSubgraphWithTargetNode

public static Graph getMarkovBlanketSubgraphWithTargetNode(Graph graph,
 Node target)

Calculates the subgraph over the Markov blanket of a target node for a DAG, CPDAG, MAG, or PAG. This is not necessarily minimal (i.e. not necessarily a Markov Boundary). Target Node is included in the result graph's nodes list. Edges including the target node is included in the result graph's edges list.

Parameters:

graph - a DAG, CPDAG, MAG, or PAG.

target - a node in the given graph.

Returns:

a Graph object

removeBidirectedOrientations

public static Graph removeBidirectedOrientations(Graph estCpdag)

removeBidirectedOrientations.

Parameters:

estCpdag - a Graph object

Returns:

a Graph object

undirectedGraph

public static Graph undirectedGraph(Graph graph)

undirectedGraph.

Parameters:

graph - a Graph object

Returns:

a Graph object

nondirectedGraph

public static Graph nondirectedGraph(Graph graph)

undirectedGraph.

Parameters:

graph - a Graph object

Returns:

a Graph object

completeGraph

public static Graph completeGraph(Graph graph)

completeGraph.

Parameters:

graph - a Graph object

Returns:

a Graph object

bidirectedToUndirected

public static Graph bidirectedToUndirected(Graph graph)

Converts a bidirected graph to an undirected graph.

Parameters:

graph - The bidirected graph to be converted.

Returns:

The converted undirected graph.

undirectedToBidirected

public static Graph undirectedToBidirected(Graph graph)

Converts an undirected graph to a bidirected graph.

Parameters:

graph - the undirected graph to be converted

Returns:

a new bidirected graph with the same nodes and bidirected edges as the input graph

pathString

public static String pathString(Graph graph,
 List<Node> path,
 boolean showBlocked)

Constructs a string representation of a path in a graph.

Parameters:

graph - the graph in which the path exists

path - the list of nodes representing the path

showBlocked - determines whether blocked nodes should be included in the string representation

Returns:

the string representation of the path

pathString

public static String pathString(Graph graph,
 Node... x)

Generates a string representation of a path in a given graph, starting from the specified nodes.

Parameters:

graph - the graph in which the path is located

x - the starting nodes of the path

Returns:

a string representation of the path

pathString

public static String pathString(Graph graph,
 List<Node> path,
 Set<Node> conditioningVars)

Returns a string representation of the given path in the graph, considering the conditioning variables.

Parameters:

graph - the graph to find the path in

path - the list of nodes representing the path

conditioningVars - the set of conditioning variables to consider

Returns:

a string representation of the path

pathString

public static String pathString(Graph graph,
 List<Node> path,
 Set<Node> conditioningVars,
 boolean showBlocked,
 boolean allowSelectionBias)

Returns a string representation of the given path in the graph, with additional information about conditioning variables.

Parameters:

graph - the graph containing the path

path - the list of nodes representing the path

conditioningVars - the list of nodes representing the conditioning variables

showBlocked - whether to show information about blocked paths

allowSelectionBias - whether to allow selection bias. For CPDAGs, this should be false, since undirected edges mean directed in one direction or the other. For PAGs, it should be true, since undirected edges indicate selection bias.

Returns:

a string representation of the path with conditioning information

replaceNodes

public static Graph replaceNodes(Graph originalGraph,
 List<Node> newVariables)

Converts the given graph, originalGraph, to use the new variables (with the same names as the old).

Parameters:

originalGraph - The graph to be converted.

newVariables - The new variables to use, with the same names as the old ones.

Returns:

A new, converted, graph.

restrictToMeasured

public static Graph restrictToMeasured(Graph graph)

Removes all latent nodes from the graph and returns the modified graph.

Parameters:

graph - the input graph to be modified

Returns:

a new graph with all latent nodes removed

replaceNodes

public static List<Node> replaceNodes(List<Node> originalNodes,
 List<Node> newNodes)

Converts the given list of nodes, originalNodes, to use the new variables (with the same names as the old).

Parameters:

originalNodes - The list of nodes to be converted.

newNodes - A list of new nodes, containing as a subset nodes with the same names as those in originalNodes. the old ones.

Returns:

The converted list of nodes.

countAdjErrors

public static int countAdjErrors(Graph graph1,
 Graph graph2)

Counts the adjacencies that are in graph1 but not in graph2.

Parameters:

graph1 - a Graph object

graph2 - a Graph object

Returns:

a int

Throws:

IllegalArgumentException - if graph1 and graph2 are not namewise isomorphic.

replaceNodes

public static List<Node> replaceNodes(List<Node> originalNodes,
 Graph graph)

Converts the given list of nodes, originalNodes, to use the replacement nodes for them by the same name in the given graph.

Parameters:

originalNodes - The list of nodes to be converted.

graph - A graph to be used as a source of new nodes.

Returns:

A new, converted, graph.

emptyGraph

public static Graph emptyGraph(int numNodes)

Creates an empty graph with the specified number of nodes.

Parameters:

numNodes - the number of nodes to create in the graph

Returns:

a new empty graph with the specified number of nodes

getAmbiguousTriplesFromGraph

public static List<Triple> getAmbiguousTriplesFromGraph(Node node,
 Graph graph)

Retrieves the list of ambiguous triples from the given graph for a given node. These are triple (X, Y, Z) for which Sepset(X, Z) contains Y for some sepsets but not others.

Parameters:

node - the node for which to find ambiguous triples

graph - the graph from which to retrieve the ambiguous triples

Returns:

the list of ambiguous triples found in the graph for the given node

getUnderlinedTriplesFromGraph

public static List<Triple> getUnderlinedTriplesFromGraph(Node node,
 Graph graph)

Retrieves the underlined triples from the given graph that involve the specified node. These are triples that represent definite noncolliders in the given graph.

Parameters:

node - the node for which to retrieve the underlined triples

graph - the graph from which to retrieve the underlined triples

Returns:

a list of underlined triples involving the node

getDottedUnderlinedTriplesFromGraph

public static List<Triple> getDottedUnderlinedTriplesFromGraph(Node node,
 Graph graph)

Retrieves the list of dotted and underlined triples from the given graph, with the specified node as the middle node.

Parameters:

node - The middle node to use for finding the triples.

graph - The graph to search for the triples.

Returns:

The list of dotted and underlined triples containing the specified node as the middle node.

containsBidirectedEdge

public static boolean containsBidirectedEdge(Graph graph)

Checks if a given graph contains a bidirected edge.

Parameters:

graph - the graph to check for bidirected edges

Returns:

true if the graph contains a bidirected edge, false otherwise

listColliderTriples

public static LinkedList<Triple> listColliderTriples(Graph graph)

Generates a list of triples where a node acts as a collider in a given graph.

Parameters:

graph - the graph to search for collider triples in

Returns:

a LinkedList of Triples where a node acts as a collider

asList

public static List<Node> asList(int[] indices,
 List<Node> nodes)

Constructs a list of nodes from the given nodes list at the given indices in that list.

Parameters:

indices - The indices of the desired nodes in nodes.

nodes - The list of nodes from which we select a sublist.

Returns:

The sublist selected.

asSet

public static Set<Node> asSet(int[] indices,
 List<Node> nodes)

Converts an array of indices into a set of corresponding nodes from a given list of nodes.

Parameters:

indices - an array of indices representing the positions of nodes in the list

nodes - the list of nodes

Returns:

a Set containing the nodes at the specified indices

asSet

public static Set<Node> asSet(Node... nodes)

Converts the given array of nodes into a Set of nodes.

Parameters:

nodes - the array of nodes.

Returns:

a Set containing the nodes from the input array.

degree

public static int degree(Graph graph)

Calculates the maximum degree of a graph.

Parameters:

graph - The graph to calculate the degree.

Returns:

The maximum degree of the graph. Returns 0 if the graph is empty.

getIntersectionComparisonString

public static String getIntersectionComparisonString(List<Graph> graphs)

Generates a comparison string for the intersection of multiple graphs.

Parameters:

graphs - the list of graphs to compare

Returns:

a string representation of the intersection of the given graphs

edgeMisclassifications

public static String edgeMisclassifications(double[][] counts,
 NumberFormat nf)

Generates a textual representation of the edge misclassifications based on the provided counts and number format.

Parameters:

counts - The 2D array representing the counts of edge misclassifications.

nf - The number format used to format the counts.

Returns:

A string containing the textual representation of the edge misclassifications.

edgeMisclassifications

public static String edgeMisclassifications(int[][] counts)

Calculates the misclassifications of edges based on the given counts.

Parameters:

counts - a 2D array containing the counts for different edge classifications

Returns:

a string representing the misclassifications of edges

addEdgeSpecializationMarkup

public static void addEdgeSpecializationMarkup(Graph graph)

Adds markups for edge specializations for the edges in the given graph. This used to be called PAG coloring.

Parameters:

graph - The graph to which PAG edge specialization markups will be added.

edgeMisclassificationCounts

public static int[][] edgeMisclassificationCounts(Graph leftGraph,
 Graph topGraph,
 boolean print)

Computes the misclassification counts for each edge in the given graphs.

Parameters:

leftGraph - The left graph.

topGraph - The top graph.

print - Whether to print debug information.

Returns:

A 2-dimensional array containing the counts for each misclassification type. The array has dimensions [m][n], where m is the number of misclassification types in the left graph and n is the number of misclassification types in the top graph.

maximalCliques

public static Set<Set<Node>> maximalCliques(Graph graph,
 List<Node> nodes)

Finds all maximal cliques in a given graph.

Parameters:

graph - The graph in which to find the maximal cliques

nodes - The list of nodes in the graph

Returns:

The set of all maximal cliques in the graph

graphNodeAttributesToText

public static String graphNodeAttributesToText(Graph graph,
 String title,
 char delimiter)

Converts the attributes of nodes in a graph to text format.

Parameters:

graph - the graph containing nodes

title - the title to be displayed before the attributes, can be null or empty

delimiter - the delimiter character used for separating node attributes

Returns:

a string representation of the graph node attributes, or null if there are no attributes

graphAttributesToText

public static String graphAttributesToText(Graph graph,
 String title)

Converts the attributes of a given graph into a text format.

Parameters:

graph - the graph whose attributes are to be converted

title - the title to be included at the beginning of the converted text

Returns:

the converted attributes in text format, or null if the graph has no attributes

graphNodesToText

public static String graphNodesToText(Graph graph,
 String title,
 char delimiter)

Converts the nodes of a graph to a formatted text representation.

Parameters:

graph - the graph containing the nodes

title - the title to be displayed at the beginning of the text (optional, can be null)

delimiter - the character used to separate the nodes in the text

Returns:

a string representing the nodes of the graph

graphEdgesToText

public static String graphEdgesToText(Graph graph,
 String title)

Converts the edges of a graph to text representation.

Parameters:

graph - The graph whose edges will be converted.

title - The title to be included in the text representation. Can be null or empty.

Returns:

The text representation of the graph edges.

triplesToText

public static String triplesToText(Set<Triple> triples,
 String title)

Converts a set of triples into a formatted string.

Parameters:

triples - the set of triples to convert

title - the optional title to include in the string

Returns:

the formatted string representation of the triples

getTwoCycleErrors

public static GraphUtils.TwoCycleErrors getTwoCycleErrors(Graph trueGraph,
 Graph estGraph)

Returns the TwoCycleErrors object that represents errors for direct feedback loops.

Parameters:

trueGraph - The true Graph object.

estGraph - The estimated Graph object.

Returns:

The TwoCycleErrors object that represents the adjacency errors.

getDegree

public static int getDegree(Graph graph)

Returns the maximum degree of a graph.

Parameters:

graph - the graph to calculate the degree for

Returns:

the maximum degree of the graph

getIndegree

public static int getIndegree(Graph graph)

Calculates the maximum indegree in a given graph.

Parameters:

graph - The graph to calculate the maximum indegree for.

Returns:

The maximum indegree in the graph.

traverseSemiDirected

public static Node traverseSemiDirected(Node node,
 Edge edge)

Traverses a semi-directed edge to identify the next node in the traversal.

Parameters:

node - The starting node of the edge.

edge - The semi-directed edge to be traversed.

Returns:

The next node in the traversal, or null if no such node exists.

getComparisonGraph

public static Graph getComparisonGraph(Graph graph,
 Parameters params)

Returns a comparison graph based on the specified parameters.

Parameters:

graph - the original graph to compare

params - the parameters for comparison

Returns:

the comparison graph based on the specified parameters

gfciExtraEdgeRemovalStep

public static void gfciExtraEdgeRemovalStep(Graph graph,
 Graph cpdag,
 List<Node> nodes,
 SepsetProducer sepsets,
 int depth,
 boolean verbose)
                                     throws InterruptedException

The extra-edge removal step for GFCI. This removes edges in triangles in the CPDAG from a score search like FGES or BOSS. We look for sepsets S for edge a--c, among the adjacents of b, such that a _||_ c | S.

Parameters:

graph - The graph being operated on and changed.

cpdag - The reference graph, a CPDAG obtained using such an algorithm.

nodes - The nodes in the graph.

sepsets - A SepsetProducer that will do the sepset search operation described.

depth - The depth of the sepset search.

verbose - Whether to print verbose output.

Throws:

InterruptedException

addForbiddenReverseEdgesForDirectedEdges

public static void addForbiddenReverseEdgesForDirectedEdges(Graph graph,
 Knowledge knowledge)

Adds forbidden reverse edges for directed edges in the given graph based on the knowledge.

Parameters:

graph - The graph to add forbidden reverse edges to.

knowledge - The knowledge used to determine the forbidden reverse edges.

removeNonSkeletonEdges

public static void removeNonSkeletonEdges(Graph graph,
 Knowledge knowledge)

Removes non-skeleton edges from the given graph based on the provided knowledge. A non-skeleton edge is determined by the name of the nodes. If either node's name starts with "E_", the edge is considered a skeleton edge and will not be removed.

Parameters:

graph - the graph from which to remove non-skeleton edges

knowledge - the knowledge base to check for forbidden edges

compatible

public static boolean compatible(Edge edge1,
 Edge edge2)

Determines if two edges are compatible.

Parameters:

edge1 - The first edge to compare.

edge2 - The second edge to compare.

Returns:

true if the edges are compatible, false otherwise.

markovBlanket

public static Set<Node> markovBlanket(Node x,
 Graph G)

Returns a Markov blanket of a node for a DAG, CPDAG, MAG, or PAG. This is not necessarily minimal (i.e. not necessarily a Markov Boundary).

Parameters:

x - The target node.

G - The PAG.

Returns:

A Markov blanket of the target node.

district

public static Set<Node> district(Node x,
 Graph G)

Calculates the district of a given node in a graph.

Parameters:

x - the node for which the district needs to be calculated

G - the graph in which to calculate the district

Returns:

the set of nodes that belong to the district of the given node

visibleEdgeAdjustments1

public static Set<Set<Node>> visibleEdgeAdjustments1(Graph G,
 Node x,
 Node y,
 int numSmallestSizes,
 GraphUtils.GraphType graphType)

Calculates visual-edge adjustments given graph G between two nodes x and y that are subsets of MB(X).

Parameters:

G - the input graph

x - the source node

y - the target node

numSmallestSizes - the number of smallest adjustment sets to return

graphType - the type of the graph

Returns:

the adjustment sets as a set of sets of nodes

Throws:

IllegalArgumentException - if the input graph is not a legal MPDAG

visibleEdgeAdjustments3

public static Set<Set<Node>> visibleEdgeAdjustments3(Graph G,
 Node x,
 Node y,
 int numSmallestSizes,
 GraphUtils.GraphType graphType)

This method calculates visible-edge adjustments for a given graph, two nodes, a number of smallest sizes, and a graph type.

Parameters:

G - the input graph

x - the first node

y - the second node

numSmallestSizes - the number of smallest sizes to consider

graphType - the type of the graph

Returns:

a set of subsets of nodes representing visible-edge adjustments

getGraphWithoutXToY

public static Graph getGraphWithoutXToY(Graph G,
 Node x,
 Node y,
 GraphUtils.GraphType graphType)

Returns a graph that is obtained by removing the edge from node x to node y from the input graph. The type of the output graph is determined by the provided graph type.

Parameters:

G - the input graph

x - the starting node of the edge to be removed

y - the ending node of the edge to be removed

graphType - the type of the output graph (CPDAG, PAG, or MAG)

Returns:

the resulting graph after removing the edge from node x to node y

Throws:

IllegalArgumentException - if the input graph type is not legal (must be CPDAG, PAG, or MAG)

anteriority

public static Set<Node> anteriority(Graph G,
 Node... x)

Computes the anteriority of the given nodes in a graph. An anterior node is a node that has a directed path to any of the given nodes. This method returns a set of anterior nodes.

Parameters:

G - the graph to compute anteriority on

x - the nodes to compute anteriority for

Returns:

a set of anterior nodes

isDag

public static boolean isDag(Graph graph)

Determines if the given graph is a directed acyclic graph (DAG).

Parameters:

graph - the graph to be checked

Returns:

true if the graph is a DAG, false otherwise

convert

public static Graph convert(String spec)

Converts a string spec of a graph--for example, "X1-->X2, X1---X3, X2o->X4, X3<->X4" to a Graph. The spec consists of a comma separated list of edge specs of the forms just used in the previous sentence. Unconnected nodes may be listed separately--example: "X,Y->Z". To specify a node as latent, use "Latent()." Example: "Latent(L1),Y->L1."

Parameters:

spec - a String object

Returns:

a Graph object

gfciR0

public static void gfciR0(Graph pag,
 Graph cpdag,
 SepsetProducer sepsets,
 Knowledge knowledge,
 boolean verbose,
 Set<Triple> unshieldedTriples)
                   throws InterruptedException

Applies the GFCI-R0 algorithm to orient edges in a pag based on a reference CPDAG, sepsets, and knowledge. This method modifies the given pag by changing the orientation of edges. Due to Spirtes.

Parameters:

pag - The pag to be modified.

cpdag - The reference CPDAG to guide the orientation of edges.

sepsets - The sepsets used to determine the orientation of edges.

knowledge - The knowledge used to determine the orientation of edges.

verbose - Whether to print verbose output.

unshieldedTriples - A set to store unshielded triples.

Throws:

InterruptedException

unshieldedCollider

public static boolean unshieldedCollider(Graph graph,
 Node a,
 Node b,
 Node c)

Checks if the given nodes are unshielded colliders when considering the given graph.

Parameters:

graph - the graph to consider

a - the first node

b - the second node

c - the third node

Returns:

true if the nodes are unshielded colliders, false otherwise

fciOrientbk

public static void fciOrientbk(Knowledge knowledge,
 Graph graph,
 List<Node> variables)

Attempts to orient the edges in the graph based on the given knowledge.

Parameters:

knowledge - The knowledge containing the forbidden and required edges to orient.

graph - The graph to orient the edges in.

variables - The list of nodes representing variables in the graph.

trimGraph

public static Graph trimGraph(List<Node> targets,
 Graph graph,
 int trimmingStyle)

Trims the given graph based on the specified trimming style.

Parameters:

targets - the list of target nodes to be trimmed

graph - the graph to be trimmed

trimmingStyle - the style indicating how the graph should be trimmed - 1: No trimming - 2: Trim nodes adjacent to target nodes - 3: Trim nodes in the Markov blanket of target nodes - 4: Trim semidirected arcs adjacent to target nodes

Returns:

the trimmed graph

Throws:

IllegalArgumentException - if an unknown trimming style is given

isConfoundingTrek

public static boolean isConfoundingTrek(Graph trueGraph,
 List<Node> trek,
 Node x,
 Node y)

Checks if the given trek in a graph is a confounding trek. This is a trek from measured node x to measured node y that has only latent nodes in between.

Parameters:

trueGraph - the true graph representing the causal relationships between nodes

trek - the trek to be checked

x - the first node in the trek

y - the last node in the trek

Returns:

true if the trek is a confounding trek, false otherwise

getTrekSource

public static Node getTrekSource(Graph graph,
 List<Node> trek)

This method returns the source node of a given trek in a graph.

Parameters:

graph - The graph containing the nodes and edges.

trek - The list of nodes representing the trek.

Returns:

The source node of the trek.

isCorrectBidirectedEdge

public static boolean isCorrectBidirectedEdge(Edge edge,
 Graph trueGraph)

Determines if the given bidirected edge has a latent confounder in the true graph--that is, whether for X <-> Y there is a latent node Z such that X <- (Z) -> Y.

Parameters:

edge - The edge to check.

trueGraph - The true graph (DAG, CPDAG, PAG_of_the_true_DAG).

Returns:

true if the given bidirected has a latent confounder in the true graph, false otherwise.

Throws:

IllegalArgumentException - if the edge is not bidirected.

guaranteePag

public static Graph guaranteePag(Graph pag,
 FciOrient fciOrient,
 Knowledge knowledge,
 Set<Triple> unshieldedColliders,
 Set<Triple> extraUnshieldedColliders,
 boolean verbose,
 Set<Node> selection)

Guarantees a legal PAG by repairing deviations of a graph from a legal PAG (partial ancestral graph).

Two types of repairs are attempted. First, if there is an edge x <-> y with a path x ~~> y, then the unshielded colldiers into x are removed and the graph is rebuilt.

Second, if there is an inducing path between two non-adjacent nodes x and y, then an edge x *-*.y is added. Arrows are included at x and y if including them prevents almost cycles.

The final orientation is then done using the FCI orient from DAG to PAG (using DSEP).

TODO: this method is in a bit of a state of flux as various ideas are tried for repairing PAGs

Parameters:

pag - the faulty PAG to be repaired

fciOrient - the FciOrient object used for final orientation

knowledge - the knowledge object used for orientation

unshieldedColliders - the set of unshielded colliders to be updated

extraUnshieldedColliders - the set of extra unshielded colliders oriented after the initial scoring step.

verbose - indicates whether or not to print verbose output

selection - the set of nodes to consider for selection

Returns:

the repaired PAG

Throws:

IllegalArgumentException - if the estimated PAG contains a directed cycle

getNumInducedAdjacenciesInPag

public static int getNumInducedAdjacenciesInPag(Graph trueGraph,
 Graph estGraph)

Calculates the number of induced adjacencies in the given estiamted Partial Ancestral (PAG) with respect to the given true PAG. An induced adjacency in a PAG is an edge that is adjacent in the estimated graph, but not in the true graph, and is not covering a collider or noncollider in the true graph.

Parameters:

trueGraph - the true PAG.

estGraph - the estimated PAG.

Returns:

the number of induced adjacencies in the PAG.

See Also:

• edgeInEstInTrue(Graph, Graph, Node, Node)

getNumCoveringAdjacenciesInPag

public static int getNumCoveringAdjacenciesInPag(Graph trueGraph,
 Graph estGraph)

Returns the number of covering edges in the given estimated partial ancestral graph (PAG) with respect to the given true PAG. A covering edge in a PAG connects two nodes such that the edges in the true graph represent the edges in the estimated graph.

Parameters:

trueGraph - The true ancestral graph

estGraph - The estimated ancestral graph

Returns:

The count of covering edges in the PAG

See Also:

• isCoveringAdjacency(Graph, Graph, Node, Node)

isCoveringAdjacency

public static boolean isCoveringAdjacency(Graph trueGraph,
 Graph estGraph,
 Node x,
 Node y)

Determines whether an edge between two nodes in the estimated graph is covering a collider or noncollider in the true graph. This is the case if the edge is adjacent in the estimated graph, but not in the true graph, and there is a common adjacent node in the estimated graph that is also a common adjacent node in the true graph. If the path through the common adjacent node is a collider in the true graph if and only if it is a noncollider in the estimated graph, then the edge is covering a collider or noncollider.

Parameters:

trueGraph - the true graph

estGraph - the estimated graph

x - the first node

y - the second node

Returns:

true if the edge is covering a collider or noncollider, false otherwise

asList

@NotNull
public static @NotNull List<Integer> asList(int[] choice)

Creates a new list containing the elements of the given array.

Parameters:

choice - the array of integers to be converted to a list

Returns:

a list of integers containing the elements of the array

dsep0

public static Set<Node> dsep0(Node x,
 Node y,
 Graph G)

Returns D-SEP(x, y) for a MAG G (or inducing path graph G, as in Causation, Prediction and Search). This method implements a reachability style.

We trust the user to make sure the given graph is a MAG or IPG; we don't check this.

Parameters:

x - The one endpoint.

y - The other endpoint.

G - The MAG.

Returns:

D-SEP(x, y) for MAG G.

dsep

public static Set<Node> dsep(Node x,
 Node y,
 Graph G)

Returns D-SEP(x, y) for a MAG G. This method implements a non-reachability style.

We trust the user to make sure the given graph is a MAG or IPG; we don't check this.

Parameters:

x - The one endpoint.

y - The other endpoint.

G - The MAG.

Returns:

D-SEP(x, y) for MAG G.

dsep2

public static Set<Node> dsep2(Node x,
 Node y,
 Graph G)

Returns D-SEP(x, y) for a MAG G. Somewhat optimized version.

We trust the user to make sure the given graph is a MAG or IPG; we don't check this.

Parameters:

x - The one endpoint.

y - The other endpoint.

G - The MAG.

Returns:

D-SEP(x, y) for MAG G.

dsepReachability

public static Set<Node> dsepReachability(Node x,
 Node y,
 Graph G)

Returns D-SEP(x, y) for a MAG G. This method implements a reachability style.

We trust the user to make sure the given graph is a MAG or IPG; we don't check this.

Parameters:

x - The one endpoint.

y - The other endpoint.

G - The MAG.

Returns:

D-SEP(x, y) for MAG G.

removeAlmostCycles

public static boolean removeAlmostCycles(Graph pag,
 Set<Triple> unshieldedColliders,
 Set<Triple> extraUnshieldedColliders,
 FciOrient fciOrient,
 Knowledge knowledge,
 boolean verbose)

Removes almost cycles from a graph.

Parameters:

pag - the graph

unshieldedColliders - a set of unshielded colliders

extraUnshieldedColliders - a set of unshielded colliders oriented after the initial scoring step.

fciOrient - the FciOrient object

knowledge - the knowledge base

verbose - a flag indicating whether to log verbose output

Returns:

AtomicBoolean(true) if any almost cycles were removed, AtomicBoolean(false) otherwise

removeCycles

public static boolean removeCycles(Set<Triple> unshieldedColliders,
 FciOrient fciOrient,
 Graph pag,
 Knowledge knowledge,
 boolean verbose)

Removes cycles from the given graph using the Fast Causal Inference (FCI) algorithm.

Parameters:

unshieldedColliders - the set of unshielded colliders.

fciOrient - the FciOrient object used for orientation

pag - the graph to remove cycles from

knowledge - the knowledge base used by the FCI algorithm

verbose - a flag indicating whether to log verbose information

Returns:

AtomicBoolean(true) if any cycles were removed, AtomicBoolean(false) otherwise

reorientWithCircles

public static void reorientWithCircles(Graph pag,
 boolean verbose)

Reorients all edges in a Graph as o-o. This method is used to apply the o-o orientation to all edges in the given Graph following the PAG (Partially Ancestral Graph) structure.

Parameters:

pag - The Graph to be reoriented.

verbose - A boolean value indicating whether verbose output should be printed.

recallUnshieldedTriples

public static void recallUnshieldedTriples(Graph pag,
 Set<Triple> unshieldedColliders,
 Knowledge knowledge)

Recall unshielded triples in a given graph.

Parameters:

pag - The graph to recall unshielded triples from.

unshieldedColliders - The set of unshielded colliders that need to be recalled.

knowledge - the knowledge object.

triple

public static boolean triple(Graph graph,
 Node a,
 Node b,
 Node c)

Checks if three nodes are connected in a graph.

Parameters:

graph - the graph to check for connectivity

a - the first node

b - the second node

c - the third node

Returns:

true if all three nodes are connected, false otherwise

colliderAllowed

public static boolean colliderAllowed(Graph pag,
 Node x,
 Node b,
 Node y,
 Knowledge knowledge)

Determines if the collider is allowed.

Parameters:

pag - The Graph representing the PAG.

x - The Node object representing the first node.

b - The Node object representing the second node.

y - The Node object representing the third node.

knowledge - The Knowledge object.

Returns:

true if the collider is allowed, false otherwise.

doRequiredOrientations

public static void doRequiredOrientations(FciOrient fciOrient,
 Graph pag,
 List<Node> best,
 Knowledge knowledge,
 boolean verbose)

Orient required edges in PAG.

Parameters:

fciOrient - The FciOrient object used for orienting the edges.

pag - The Graph representing the PAG.

best - The list of Node objects representing the best nodes.

knowledge - The Knowledge object.

verbose - A boolean value indicating whether verbose output should be printed.

distinct

public static boolean distinct(Node... n)

Determines whether three Node objects are distinct.

Parameters:

n - the nodes to check for distinctness

Returns:

true if x, b, and y are distinct; false otherwise

localMarkovInitializePValues

public static double localMarkovInitializePValues(Graph dag,
 boolean ensureMarkov,
 IndependenceTest test,
 Map<org.apache.commons.lang3.tuple.Pair<Node,Node>,Set<Double>> pValues)
                                           throws InterruptedException

Initializes and evaluates p-values for local Markov properties in a given graph.

Parameters:

dag - The input graph, a DAG (Directed Acyclic Graph).

ensureMarkov - Flag indicating that the method should proceed only if set to true.

test - The statistical test instance used to check for conditional independence.

pValues - A map to store the p-values, indexed by pairs of nodes.

Returns:

The percentage of p-values that are less than the significance level (alpha) used in the test. Returns 0.0 if the number of p-values is less than 5 or if ensureMarkov is false or test instance is invalid.

Throws:

IllegalArgumentException - if ensureMarkov is false.

InterruptedException

pValuesAdP

public static double pValuesAdP(Map<org.apache.commons.lang3.tuple.Pair<Node,Node>,Set<Double>> _pValues)

Calculates the p-value using the Anderson-Darling test for a given set of p-values from an independence test.

Parameters:

_pValues - A map where each key is a pair of nodes, and each value is a set of p-values associated with that node pair.

Returns:

The p-value calculated from the Anderson-Darling test.