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

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

    • countArrowptErrors

      public static int countArrowptErrors(Graph graph1, Graph graph2)
      Counts the arrowheads that are in graph1 but not in graph2.
      Parameters:
      graph1 - a Graph object
      graph2 - a Graph object
      Returns:
      a int

    • getNumCorrectArrowpts

      public static int getNumCorrectArrowpts(Graph correct, Graph estimated)

      getNumCorrectArrowpts.

      Parameters:
      correct - a Graph object
      estimated - a Graph object
      Returns:
      a int

    • 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 specilizations for the edges in the given graph.
      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

    • graphToText

      public static String graphToText(Graph graph, boolean pagEdgeSpecializationMarked)
      Converts a given graph to human-readable text format.
      Parameters:
      graph - the graph to be converted
      pagEdgeSpecializationMarked - whether to add edge specialization markups to the graph before conversion
      Returns:
      the human-readable representation of 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)
      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.

    • 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

    • visualEdgeAdjustments2

      public static Set<Set<Node>> visualEdgeAdjustments2(Graph G, Node x, Node y, int numSmallestSizes, GraphUtils.GraphType graphType)
      Calculates visual-edge adjustments of a given graph G between two nodes x and y that are subsets of MB(Yma
      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)
      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.

    • 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.
      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, boolean checkCyclicity, boolean verbose)
      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
      checkCyclicity - indicates whether or not to check for cyclicity
      verbose - indicates whether or not to print verbose output
      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

      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

    • getUndirectedPathMatrix

      public static Matrix getUndirectedPathMatrix(Graph graph, int power)
      Returns an undirected path matrix based on the given graph and power. The undirected path matrix represents the existence of a path of a specific length between any two nodes in the graph.
      Parameters:
      graph - the graph from which to create the undirected path matrix
      power - the power used to calculate the undirected path matrix
      Returns:
      the undirected path matrix

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

      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.

    • removeAlmostCycles2

      public static boolean removeAlmostCycles2(Set<Triple> unshieldedColliders, FciOrient fciOrient, Graph pag, Knowledge knowledge, boolean verbose)
      Removes almost cycles from a graph.
      Parameters:
      unshieldedColliders - a set of unshielded colliders
      fciOrient - the FciOrient object
      pag - the graph
      knowledge - the knowledge base
      verbose - a flag indicating whether to log verbose output
      Returns:
      true if any change was made to the graph, 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:
      true if any cycles were removed, 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.

    • couldCreateAlmostCycle

      public static boolean couldCreateAlmostCycle(Graph pag, Node x, Node y)
      Checks if creating an almost cycle between nodes x, b, and y is possible in a given graph.
      Parameters:
      pag - The graph to check if the almost cycle can be created.
      x - The first node of the almost cycle.
      y - The third node of the almost cycle.
      Returns:
      True if creating the almost cycle is possible, false otherwise.

    • 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 x, Node b, Node y)
      Determines whether three Node objects are distinct.
      Parameters:
      x - the first Node object
      b - the second Node object
      y - the third Node object
      Returns:
      true if x, b, and y are distinct; false otherwise