Package edu.cmu.tetrad.graph

Class GraphUtils

java.lang.Object
edu.cmu.tetrad.graph.GraphUtils
public final class GraphUtils extends Object
Basic graph utilities.
Author:
Joseph Ramsey

  • 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

    • markovBlanketDag

      public static Graph markovBlanketDag(Node target, Graph dag)
      Calculates the Markov blanket of a target in a DAG. This includes the target, the parents of the target, the children of the target, the parents of the children of the target, edges from parents to target, target to children, parents of children to children, and parent to parents of children. (Edges among children are implied by the inclusion of edges from parents of children to children.) Edges among parents and among parents of children not explicitly included above are not included. (Joseph Ramsey 8/6/04)
      Parameters:
      target - a node in the given DAG.
      dag - the DAG with respect to which a Markov blanket DAG is to be calculated. All the nodes and edges of the Markov Blanket DAG are in this DAG.

    • allAdjacenciesAreDirected

      public static boolean allAdjacenciesAreDirected(Node node, Graph graph)

    • removeBidirectedOrientations

      public static Graph removeBidirectedOrientations(Graph estCpdag)

    • removeBidirectedEdges

      public static Graph removeBidirectedEdges(Graph estCpdag)

    • undirectedGraph

      public static Graph undirectedGraph(Graph graph)

    • completeGraph

      public static Graph completeGraph(Graph graph)

    • adjacenciesComplement

      public static List<Edge> adjacenciesComplement(Graph graph1, Graph graph2)
      Returns:
      the edges that are in graph1 but not in graph2, as a list of undirected edges..

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

    • getNoncollidersFromGraph

      public static List<Triple> getNoncollidersFromGraph(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.

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

    • numDirectionalErrors

      public static int numDirectionalErrors(Graph result, Graph cpdag)

    • numBidirected

      public static int numBidirected(Graph result)

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

    • retainUnshieldedColliders

      public static void retainUnshieldedColliders(Graph graph, Knowledge knowledge)
      Retains only the unshielded colliders of the given graph.
      Parameters:
      graph - The graph to retain unshielded colliders in.

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

    • pagMb

      public static Set<Node> pagMb(Node x, Graph G)

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