Package edu.cmu.tetrad.search

Class SearchGraphUtils

java.lang.Object
edu.cmu.tetrad.search.SearchGraphUtils
public final class SearchGraphUtils extends Object
Graph utilities for search algorithm. Lots of orientation method, for instance.
Author:
Joseph Ramsey

  • Constructor Details

    • SearchGraphUtils

      public SearchGraphUtils()

  • Method Details

    • pcOrientbk

      public static void pcOrientbk(Knowledge bk, Graph graph, List<Node> nodes)
      Orients according to background knowledge.

    • pcdOrientC

      public static void pcdOrientC(IndependenceTest test, Knowledge knowledge, Graph graph)
      Performs step C of the algorithm, as indicated on page xxx of CPS, with the modification that X--W--Y is oriented as X-->W<--Y if W is *determined by* the sepset of (X, Y), rather than W just being *in* the sepset of (X, Y).

    • orientUsingMeekRulesLocally

      public static void orientUsingMeekRulesLocally(Knowledge knowledge, Graph graph, IndependenceTest test, int depth)
      Orients using Meek rules, double checking noncolliders locally.

    • orientCollidersUsingSepsets

      public static void orientCollidersUsingSepsets(SepsetMap set, Knowledge knowledge, Graph graph, boolean verbose, boolean enforceCpdag)
      Step C of PC; orients colliders using specified sepset. That is, orients x *-* y *-* z as x *-> y <-* z just in case y is in Sepset({x, z}).

    • existsLocalSepsetWithout

      public static boolean existsLocalSepsetWithout(Node x, Node y, Node z, IndependenceTest test, Graph graph, int depth)

    • meekR1Locally

      public static boolean meekR1Locally(Graph graph, Knowledge knowledge, IndependenceTest test, int depth)
      Orient away from collider.

    • meekR2

      public static boolean meekR2(Graph graph, Knowledge knowledge)
      If

    • meekR3

      public static boolean meekR3(Graph graph, Knowledge knowledge)
      Meek's rule R3. If a--b, a--c, a--d, c-->b, c-->b, then orient a-->b.

    • meekR4

      public static boolean meekR4(Graph graph, Knowledge knowledge)

    • isArrowpointAllowed

      public static boolean isArrowpointAllowed(Object from, Object to, Knowledge knowledge)
      Checks if an arrowpoint is allowed by background knowledge.

    • basicCPDAG

      public static void basicCPDAG(Graph graph)
      Get a graph and direct only the unshielded colliders.

    • basicCpdagRestricted2

      public static void basicCpdagRestricted2(Graph graph, Node node)

    • cpdagFromDag

      public static Graph cpdagFromDag(Graph dag)
      Returns:
      the cpdag to which the given DAG belongs.

    • dagFromCPDAG

      public static Graph dagFromCPDAG(Graph graph)

    • dagFromCPDAG

      public static Graph dagFromCPDAG(Graph graph, Knowledge knowledge)

    • pagToMag

      public static Graph pagToMag(Graph pag)

    • isLegalPag

      public static SearchGraphUtils.LegalPagRet isLegalPag(Graph pag)

    • arrangeByKnowledgeTiers

      public static void arrangeByKnowledgeTiers(Graph graph, Knowledge knowledge)

    • arrangeByKnowledgeTiers

      public static void arrangeByKnowledgeTiers(Graph graph)

    • getReachableNodes

      public static Set<Node> getReachableNodes(List<Node> initialNodes, LegalPairs legalPairs, List<Node> c, List<Node> d, Graph graph, int maxPathLength)
      Parameters:
      initialNodes - The nodes that reachability undirectedPaths start from.
      legalPairs - Specifies initial edges (given initial nodes) and legal edge pairs.
      c - a set of vertices (intuitively, the set of variables to be conditioned on.
      d - a set of vertices (intuitively to be used in tests of legality, for example, the set of ancestors of c).
      graph - the graph with respect to which reachability is
      Returns:
      the set of nodes reachable from the given set of initial nodes in the given graph according to the criteria in the given legal pairs object.

      A variable v is reachable from initialNodes iff for some variable X in initialNodes thers is a path U [X, Y1, ..., v] such that legalPairs.isLegalFirstNode(X, Y1) and for each [H1, H2, H3] as subpaths of U, legalPairs.isLegalPairs(H1, H2, H3).

      The algorithm used is a variant of Algorithm 1 from Geiger, Verma, and Pearl (1990).

    • translate

      public static Node translate(String a, List<Node> nodes)
      Returns:
      the string in nodelist which matches string in BK.

    • powerSet

      public static List<Set<Node>> powerSet(List<Node> nodes)

    • isArrowpointAllowed1

      public static boolean isArrowpointAllowed1(Node from, Node to, Knowledge knowledge)
      Checks if an arrowpoint is allowed by background knowledge.

    • generateCpdagDags

      public static List<Graph> generateCpdagDags(Graph cpdag, boolean orientBidirectedEdges)
      Generates the list of DAGs in the given cpdag.

    • getDagsInCpdagMeek

      public static List<Graph> getDagsInCpdagMeek(Graph cpdag, Knowledge knowledge)

    • getAllGraphsByDirectingUndirectedEdges

      public static List<Graph> getAllGraphsByDirectingUndirectedEdges(Graph skeleton)

    • getCpcTripleType

      public static SearchGraphUtils.CpcTripleType getCpcTripleType(Node x, Node y, Node z, IndependenceTest test, int depth, Graph graph)

    • cpdagForDag

      public static Graph cpdagForDag(Graph dag)

    • structuralHammingDistance

      public static int structuralHammingDistance(Graph trueGraph, Graph estGraph)
      Tsamardinos, I., Brown, L. E., and Aliferis, C. F. (2006). The max-min hill-climbing Bayesian network structure learning algorithm. Machine learning, 65(1), 31-78.

      Converts each graph (DAG or CPDAG) into its CPDAG before scoring.

    • getGraphComparison

      public static GraphUtils.GraphComparison getGraphComparison(Graph trueGraph, Graph targetGraph)

    • getGraphComparison2

      public static GraphUtils.GraphComparison getGraphComparison2(Graph graph, Graph trueGraph)
      Just counts arrowpoint errors--for cyclic edges counts an arrowpoint at each node.

    • graphComparisonString

      public static String graphComparisonString(String trueGraphName, Graph trueGraph, String targetGraphName, Graph targetGraph, boolean printStars)

    • graphComparison

      public static int[][] graphComparison(Graph trueCpdag, Graph estCpdag, PrintStream out)

    • dagToPag

      @NotNull public static @NotNull Graph dagToPag(Graph trueGraph)