Package edu.cmu.tetrad.search.utils

Class MsepVertexCutFinder

java.lang.Object
edu.cmu.tetrad.search.utils.MsepVertexCutFinder
public class MsepVertexCutFinder extends Object
The MsepVertexCutFinder class is responsible for finding "choke points" within a given directed acyclic graph (DAG) using d-separation principles. Choke points represent sets of nodes that separate two given nodes in the graph.

The implementation leverages ancestor maps and considers causal relationships represented in the graph to find paths and cut-points between two nodes.

  • Constructor Summary

    Constructors
    Constructor
    Description
    MsepVertexCutFinder(Graph graph)
    Constructs an instance of the MsepVertexCutFinder class with the specified graph.

  • Method Summary

    Modifier and Type
    Method
    Description
    Set<Node>
    findChokePoint(Node source, Node sink, Map<Node,Set<Node>> ancestorMap)
    Finds the choke points between a source node and a sink node within a given graph, considering a specific ancestor map and utilizing a d-separation-aware approach.
    static void
    main(String[] args)
    The entry point for the MsepVertexCutFinder application.

    Methods inherited from class java.lang.Object

    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • MsepVertexCutFinder

      public MsepVertexCutFinder(Graph graph)
      Constructs an instance of the MsepVertexCutFinder class with the specified graph.
      Parameters:
      graph - the graph for which vertex cuts will be identified. This graph serves as the base structure on which the operations of the MsepVertexCutFinder are conducted.

  • Method Details

    • main

      public static void main(String[] args)
      The entry point for the MsepVertexCutFinder application. This method generates a random directed acyclic graph (DAG), initializes necessary objects, and verifies m-separation conditions for pairs of non-adjacent nodes in the graph. It determines choke points and checks their validity based on m-separation.
      Parameters:
      args - command-line arguments (not used in this implementation).

    • findChokePoint

      public Set<Node> findChokePoint(Node source, Node sink, Map<Node,Set<Node>> ancestorMap)
      Finds the choke points between a source node and a sink node within a given graph, considering a specific ancestor map and utilizing a d-separation-aware approach.
      Parameters:
      source - the starting node in the graph.
      sink - the destination node in the graph.
      ancestorMap - a map containing each node's set of ancestors. Used to determine valid paths based on d-separation principles.
      Returns:
      a set of nodes representing the choke points between the source and sink if a valid path exists, or null if no such path exists.