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 excludeSelectionBias)
      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
      excludeSelectionBias - whether to exclude 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.

    • copyNode

      public static Node copyNode(Node node)
      Returns a copy of the given node that is equal to it (same name, type, and, for a discrete variable, the same categories, so that it indexes the same column of a data set) and has the same position, but is a distinct object, so that a position later set on either is not seen through the other. Node-level attributes are copied.

      Positions (the center used by the workbench) live on node objects, not in graphs. Two graphs that share node objects therefore share a layout: a data set's variable objects are shared by every graph built from that data set, and a graph handed from one session box to another is shared by both. See detachNodes(Graph) and EdgeListGraph(Graph, boolean).

      Parameters:
      node - the node to copy
      Returns:
      the copy

    • detachNodes

      public static Graph detachNodes(Graph graph)
      Returns a copy of the graph whose nodes are fresh objects (see copyNode(Node)), equal to the originals and in the same positions, with the same edges (including their properties, edge type probabilities, and display attributes), underlines, ambiguous triples, and graph attributes. Unlike replaceNodes(Graph, List), latent nodes are copied too.

      Use this on a graph that is about to become the graph of a session box and whose nodes are shared with something else: a search result, whose nodes are usually the data set's variable objects, or the graph of another box. Once detached, the box starts with the layout the graph came with, but the layout the workbench writes to it afterwards stays with it, and it no longer follows positions set on the shared objects by some other box. Where a fresh layout is wanted instead, lay the copy out afterwards.

      Parameters:
      graph - the graph
      Returns:
      the copy

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

    • traversePotentiallyDirected

      public static Node traversePotentiallyDirected(Node node, Edge edge)
      Traverses a potentially directed edge to identify the next node in the traversal.
      Parameters:
      node - The starting node of the edge.
      edge - The potentially 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)
      Computes the Markov blanket for a given node in a graph. The Markov blanket of a node x is the set of nodes that include the parents of x, the children of x, and all other parents of x's children (i.e., colliders involving x).
      Parameters:
      x - the target node for which the Markov blanket is computed
      G - the graph containing the nodes and edges
      Returns:
      a set of nodes representing the Markov blanket of x

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

    • 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

    • 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 potentially directed 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

    • trekSourceLatent

      public static boolean trekSourceLatent(Graph trueGraph, List<Node> trek, Node x, Node y)
      Checks if the souce L of the given trek in a graph (not equal to x or y) is a latent. This is a trek from measured node x to measured node y with a latent source. Other nodes on the path may be measured or latent.
      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 source of the trek (not equal to x or y) is latent, false otherwise.

    • bidirectedExistsLatentCommonCauseUncovered

      public static boolean bidirectedExistsLatentCommonCauseUncovered(Edge edge, Graph trueGraph, Graph estGraph)
      Determines whether the given bidirected edge has a latent common cause in the true graph via a trek x <~~ L ~~> y whose source L is latent, but where at least one consecutive pair of nodes (w, r) along the trek is NOT adjacent in the estimated graph. Other nodes on the trek may be measured or latent; only the source L is required to be latent.

      This is a variation of bidirectedExistsLatentCommonCause(Edge, Graph) that additionally requires the trek to contain an edge (w, r) for which !estGraph.isAdjacentTo(w, r) -- i.e., the trek is not fully "covered" by adjacencies in the estimated graph.

      Parameters:
      edge - The edge to check.
      trueGraph - The true graph (DAG, CPDAG, PAG_of_the_true_DAG).
      estGraph - The estimated graph against which consecutive-pair adjacency is checked.
      Returns:
      true if such a trek exists, false otherwise.
      Throws:
      IllegalArgumentException - if the edge is not bidirected.

    • trekIsUncovered

      public static boolean trekIsUncovered(Graph trueGraph, Graph estGraph, List<Node> trek)
      Checks whether the given trek is "uncovered" relative to the estimated graph in the following sense: every consecutive pair along the trek is adjacent in the true graph, and among the consecutive pairs whose BOTH endpoints are measured, at least one is non-adjacent in the estimated graph. If the trek has no measured-to-measured consecutive pair, the condition is vacuously satisfied.

      Nodes are matched into the estimated graph by name, so the trek (from the true graph) and the estimated graph need not share node objects.

      Parameters:
      trueGraph - the true graph, used to confirm consecutive-pair adjacency along the trek
      estGraph - the estimated graph in which measured-to-measured adjacency is checked
      trek - the trek whose consecutive pairs are examined
      Returns:
      true if the trek is uncovered as defined above, 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.

    • bidirectedExistsLatentConfounder

      public static boolean bidirectedExistsLatentConfounder(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.

    • bidirectedExistsLatentCommonCause

      public static boolean bidirectedExistsLatentCommonCause(Edge edge, Graph trueGraph)
      Determines whether a bidirected edge exists due to a latent common cause in the given graph. A latent common cause refers to an unobserved variable responsible for the relationship between the two nodes connected by the bidirected edge.
      Parameters:
      edge - the bidirected edge to be checked. Must be bidirected, otherwise an IllegalArgumentException will be thrown.
      trueGraph - the graph in which the check for a latent common cause is performed. This graph is assumed to contain the necessary structure and properties for validating the existence of a latent common cause.
      Returns:
      true if the bidirected edge exists due to a latent common cause in the provided graph; false otherwise.
      Throws:
      IllegalArgumentException - if the input edge is not a bidirected edge.

    • guaranteePag

      public static Graph guaranteePag(Graph pag, FciOrient fciOrient, Knowledge knowledge, Set<Triple> knownColliders, boolean verbose, Set<Node> selection, boolean excludeSelectionBias, int recursiveDepth)
      Guarantees the correctness of a Partial Ancestral Graph (PAG) by repairing faulty structures such as cycles, violations of maximality, and incorrectly oriented edges, using FCI orientation rules and knowledge constraints.

      The method works down a ladder of increasingly aggressive fallbacks, returning at the first rung that yields a legal PAG (as judged by PagLegalityCheck.isLegalPagQuiet(Graph, Set, int), uniformly, with the given selection set):

      1. the repair loop (monotone edge additions to a fixpoint);
      2. a MAG round-trip of the repaired graph;
      3. a second repair pass and round-trip applied to the round-trip output, if it made progress;
      4. the pre-round-trip repaired state itself;
      5. a DAG orientation of the repaired skeleton (cannot fail: every DAG is a legal MAG). This rung preserves the estimated adjacencies but discards orientation information, and respects background knowledge only up to tier ordering.

      NOTE: pag is modified in place, and knownColliders is destructively consumed as colliders are sacrificed to shielding repairs. Callers that need either object afterward should pass copies.

      Parameters:
      pag - the initial PAG to be repaired (modified in place)
      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; consumed
      verbose - whether to provide detailed logging of the repair process
      selection - a set of nodes to be considered during the maximality repair
      excludeSelectionBias - whether to exclude the selection bias during the repair process
      recursiveDepth - the maximum current depth of recursion in the repair process
      Returns:
      a legal PAG

    • 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. (fciOrient, knowledge, and knownColliders are retained in the signature for API compatibility but are not used; reorientation happens once per pass in the repair loop.)
      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.

    • connectedComponents

      public static List<Set<Node>> connectedComponents(Graph g)
      Identifies all connected components in a given graph. A connected component is a subset of the graph's nodes such that each pair of nodes is connected by a path, and which is not connected to any additional nodes in the graph.
      Parameters:
      g - The graph for which to find connected components. It is assumed to be an undirected graph and implemented as a data structure providing access to its nodes and the adjacency list for each node.
      Returns:
      A list of sets, where each set contains the nodes that belong to a single connected component of the graph.

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

    • getReplicatingGraph

      @NotNull public static @NotNull Graph getReplicatingGraph(Graph graph)
      Creates a replicating graph based on the provided graph. The method generates a new graph where edges are replicated only for child nodes that are lag-0 (i.e., nodes without a colon in their name). Lag-0 nodes and their parent relationships are preserved and replicated automatically to all other lag-slices.
      Parameters:
      graph - the source graph from which the replicating graph is generated. The input graph contains nodes and edges that determine the structure of the resulting replicating graph.
      Returns:
      a new Graph instance representing the replicating graph. This graph includes all the replicated relationships as described.

    • applyForbiddenCircleResolution

      public static boolean applyForbiddenCircleResolution(Graph pag, Knowledge knowledge)
      Resolves forbidden circles in the given partially oriented graph (PAG) based on the provided knowledge. Updates edge endpoints to arrowheads where forbidden relationships are detected. Temp method to try to fix a putative knowledge issue in FCI.
      Parameters:
      pag - the partially oriented graph to be processed
      knowledge - the knowledge object containing forbidden relationships between nodes
      Returns:
      true if any changes were made to the graph; false otherwise