Package edu.cmu.tetrad.graph

Class GraphUtils

java.lang.Object
edu.cmu.tetrad.graph.GraphUtils
public final class GraphUtils extends Object
Utility class for manipulating graphs.
Author:
josephramsey

  • Constructor Details

    • GraphUtils

      public GraphUtils()

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

    • addPagColoring

      public static void addPagColoring(Graph graph)
      Adds PAG coloring to the edges in the given graph.
      Parameters:
      graph - The graph to which PAG coloring 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 doPagColoring)
      Converts a graph to a textual representation.
      Parameters:
      graph - the input graph to be converted
      doPagColoring - boolean flag indicating whether to add PAG coloring to the graph
      Returns:
      the textual 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)
      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.

    • 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

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

    • 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