Class GraphUtils

java.lang.Object
edu.cmu.tetrad.graph.GraphUtils

public final class GraphUtils extends Object
Basic graph utilities.
Author:
josephramsey
  • Constructor Details

    • GraphUtils

      public GraphUtils()
  • Method Details

    • getAssociatedNode

      public static Node getAssociatedNode(Node errorNode, Graph graph)
      Returns:
      the node associated with a given error node. This should be the only child of the error node, E --> N.
    • isClique

      public static boolean isClique(Collection<Node> set, Graph graph)
      Returns:
      true if set is a clique in graph. R. Silva, June 2004
    • 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.
    • removeBidirectedOrientations

      public static Graph removeBidirectedOrientations(Graph estCpdag)
    • undirectedGraph

      public static Graph undirectedGraph(Graph graph)
    • completeGraph

      public static Graph completeGraph(Graph graph)
    • bidirectedToUndirected

      public static Graph bidirectedToUndirected(Graph graph)
      Returns:
      a new graph in which the bidirectred edges of the given graph have been changed to undirected edges.
    • undirectedToBidirected

      public static Graph undirectedToBidirected(Graph graph)
      Returns:
      a new graph in which the undirectred edges of the given graph have been changed to bidirected edges.
    • pathString

      public static String pathString(Graph graph, List<Node> path)
    • pathString

      public static String pathString(Graph graph, Node... x)
    • 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)
    • 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.
      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.
    • getNumCorrectArrowpts

      public static int getNumCorrectArrowpts(Graph correct, Graph estimated)
    • 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)
      Returns:
      an empty graph with the given number of nodes.
    • getAmbiguousTriplesFromGraph

      public static List<Triple> getAmbiguousTriplesFromGraph(Node node, Graph graph)
      Returns:
      A list of triples of the form <X, Y, Z>, where <X, Y, Z> is a definite noncollider in the given graph.
    • getUnderlinedTriplesFromGraph

      public static List<Triple> getUnderlinedTriplesFromGraph(Node node, Graph graph)
      Returns:
      A list of triples of the form <X, Y, Z>, where <X, Y, Z> is a definite noncollider in the given graph.
    • getDottedUnderlinedTriplesFromGraph

      public static List<Triple> getDottedUnderlinedTriplesFromGraph(Node node, Graph graph)
      Returns:
      A list of triples of the form <X, Y, Z>, where <X, Y, Z> is a definite noncollider in the given graph.
    • containsBidirectedEdge

      public static boolean containsBidirectedEdge(Graph graph)
    • listColliderTriples

      public static LinkedList<Triple> listColliderTriples(Graph graph)
    • 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)
    • asSet

      public static Set<Node> asSet(Node... nodes)
    • degree

      public static int degree(Graph graph)
    • getIntersectionComparisonString

      public static String getIntersectionComparisonString(List<Graph> graphs)
    • edgeMisclassifications

      public static String edgeMisclassifications(double[][] counts, NumberFormat nf)
    • edgeMisclassifications

      public static String edgeMisclassifications(int[][] counts)
    • addPagColoring

      public static void addPagColoring(Graph graph)
    • edgeMisclassificationCounts

      public static int[][] edgeMisclassificationCounts(Graph leftGraph, Graph topGraph, boolean print)
    • maximalCliques

      public static Set<Set<Node>> maximalCliques(Graph graph, List<Node> nodes)
    • graphToText

      public static String graphToText(Graph graph, boolean doPagColoring)
    • graphNodeAttributesToText

      public static String graphNodeAttributesToText(Graph graph, String title, char delimiter)
    • graphAttributesToText

      public static String graphAttributesToText(Graph graph, String title)
    • graphNodesToText

      public static String graphNodesToText(Graph graph, String title, char delimiter)
    • graphEdgesToText

      public static String graphEdgesToText(Graph graph, String title)
    • triplesToText

      public static String triplesToText(Set<Triple> triples, String title)
    • getTwoCycleErrors

      public static GraphUtils.TwoCycleErrors getTwoCycleErrors(Graph trueGraph, Graph estGraph)
    • getDegree

      public static int getDegree(Graph graph)
    • getIndegree

      public static int getIndegree(Graph graph)
    • traverseSemiDirected

      public static Node traverseSemiDirected(Node node, Edge edge)
    • getComparisonGraph

      public static Graph getComparisonGraph(Graph graph, Parameters params)
    • 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)
    • removeNonSkeletonEdges

      public static void removeNonSkeletonEdges(Graph graph, Knowledge knowledge)
    • compatible

      public static boolean compatible(Edge edge1, Edge edge2)
    • 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)
    • isDag

      public static boolean isDag(Graph graph)
    • 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."
    • gfciR0

      public static void gfciR0(Graph graph, Graph referenceCpdag, SepsetProducer sepsets, Knowledge knowledge)
    • fciOrientbk

      public static void fciOrientbk(Knowledge knowledge, Graph graph, List<Node> variables)
      Orients according to background knowledge
    • trimGraph

      public static Graph trimGraph(List<Node> targets, Graph graph, int trimmingStyle)