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.

  • 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

    • getParentsSubgraphWithTargetNode

      public static Graph getParentsSubgraphWithTargetNode(Graph graph, Node target)
      Calculates the subgraph over the parents 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

    • getAdjacencySubgraphWithTargetNode

      public static Graph getAdjacencySubgraphWithTargetNode(Graph graph, Node target)
      Calculates the subgraph over the adjacency 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

    • 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

    • 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> knownColliders, boolean verbose, Set<Node> selection)
      Guarantees the correctness of a Partial Ancestral Graph (PAG) by repairing faulty structures such as cycles, violations of maximality, and incorrectly oriented edges. It uses FCI orientation rules and knowledge constraints to perform the repair process.
      Parameters:
      pag - the initial PAG to be repaired
      fciOrient - the FCI (Fast Causal Inference) orientation utility for edge orientation
      knowledge - the background knowledge to enforce during the repair process
      knownColliders - a set of triples representing unshielded colliders to be enforced
      verbose - whether to provide detailed logging of the repair process
      selection - a set of nodes to be considered during the maximality repair
      Returns:
      the repaired PAG that satisfies required constraints and is free of faults

    • repairMaximality

      public static boolean repairMaximality(Graph pag, boolean verbose, Set<Node> selection, FciOrient fciOrient, Knowledge knowledge, Set<Triple> knownColliders)
      Repairs the maximality of a PAG (Partial Ancestral Graph) by ensuring that any inducing path between two nodes not currently adjacent in the graph results in an added non-directed edge. The method modifies the graph in-place.
      Parameters:
      pag - the Partial Ancestral Graph to be repaired for maximality
      verbose - if true, logs the actions performed during the repair process
      selection - a set of nodes to be considered during the inducing path check
      fciOrient - The Fci orientation procedure.
      knowledge - The knowledge.
      knownColliders - Known colliders.
      Returns:
      true if the graph was modified during the repair process; false otherwise

    • 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

      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.

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

    • recallInitialColliders

      public static void recallInitialColliders(Graph pag, Set<Triple> initialColliders, Knowledge knowledge)
      Recall unshielded triples in a given graph.
      Parameters:
      pag - The graph to recall unshielded triples from.
      initialColliders - The set of unshielded colliders that need to be recalled from the CPDAG.
      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.

    • 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 preserveMarkov, 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).
      preserveMarkov - 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 preserveMarkov is false or test instance is invalid.
      Throws:
      IllegalArgumentException - if preserveMarkov is false.
      InterruptedException - if any

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

    • fixDirections

      @NotNull public static @NotNull Graph fixDirections(Graph graph)
      Processes the given graph by fixing the directions of edges to ensure consistency, flipping edges where necessary, and optionally preserving ancillary graph information.
      Parameters:
      graph - the input graph whose edge directions are to be fixed
      Returns:
      a new graph with corrected edge directions, preserving ancillary graph information if present

    • orientCollider

      public static void orientCollider(Graph g, Node x, Node z, Node y)
      Orients the edges of the given graph by setting both specified nodes as arrow endpoints directed towards the specified target node.
      Parameters:
      g - The graph in which the edges will be oriented.
      x - The first node to be set as an arrow endpoint directed towards the target node z.
      z - The target node towards which both nodes x and y will be oriented.
      y - The second node to be set as an arrow endpoint directed towards the target node z.

    • stronglyConnectedComponents

      public static List<Set<Node>> stronglyConnectedComponents(Graph g)
      Compute strongly connected components (SCCs) of a directed graph. Uses Tarjan's algorithm. Each SCC is returned as a Set.
      Parameters:
      g - The graph.
      Returns:
      List of SCCs, each represented as a Set of Nodes.