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:
      target - a node in the given graph.
      graph - a DAG, CPDAG, MAG, or PAG.
      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

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

      pathString.

      Parameters:
      graph - a Graph object
      path - a List object
      Returns:
      a String object

    • pathString

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

      pathString.

      Parameters:
      graph - a Graph object
      x - a Node object
      Returns:
      a String object

    • 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 referenceCpdag, List<Node> nodes, SepsetProducer sepsets, boolean verbose)
      The extra-edge removal step for GFCI. This removed edges in triangles in the reference graph by looking for sepsets for edge a--b among the adjacents of a or the adjacents of b.
      Parameters:
      graph - The graph being operated on and changed.
      referenceCpdag - The reference graph, a CPDAG or a DAG obtained using such an algorithm.
      nodes - The nodes in the graph.
      sepsets - A SepsetProducer that will do the sepset search operation described.
      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(Y).
      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 graph, Graph referenceCpdag, SepsetProducer sepsets, Knowledge knowledge, boolean verbose)
      Applies the GFCI-R0 algorithm to orient edges in a graph based on a reference CPDAG, sepsets, and knowledge. This method modifies the given graph by changing the orientation of edges. Due to Spirtes.
      Parameters:
      graph - The graph to be modified.
      referenceCpdag - 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.

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