Class RecursiveBlockingVerbose

java.lang.Object
edu.cmu.tetrad.search.RecursiveBlockingVerbose
public class RecursiveBlockingVerbose extends Object
The RecursiveBlocking class implements a recursive procedure for constructing candidate separating sets between two nodes under PAG semantics, with optional verbose tracing for debugging and pedagogy.

  • Method Details

    • blockPathsRecursively

      public static Set<Node> blockPathsRecursively(Graph graph, Node x, Node y, Set<Node> containing, Set<Node> notFollowed, int maxPathLength) throws InterruptedException
      Blocks paths recursively between two nodes in a graph, based on specified constraints and conditions.
      Parameters:
      graph - the graph in which paths are to be blocked
      x - the starting node for the path to be blocked
      y - the target node for the path to be blocked
      containing - a set of nodes that must be present in the blocked paths
      notFollowed - a set of nodes that must not be followed during the path blocking traversal
      maxPathLength - the maximum allowable length for a path to be considered for blocking
      Returns:
      a set of nodes that were part of the blocked paths
      Throws:
      InterruptedException - if the execution is interrupted during the operation

    • blockPathsRecursively

      public static Set<Node> blockPathsRecursively(Graph graph, Node x, Node y, Set<Node> containing, Set<Node> notFollowed, int maxPathLength, Knowledge knowledge) throws InterruptedException
      Recursively blocks paths in a graph between two nodes under specified constraints.
      Parameters:
      graph - The graph containing the nodes and edges being analyzed.
      x - The starting node of the paths to be blocked.
      y - The target node of the paths to be blocked.
      containing - A set of nodes that must be included in the paths being evaluated.
      notFollowed - A set of nodes that should not be followed during the path exploration process.
      maxPathLength - The maximum allowed length of the paths to be evaluated. A value of -1 indicates no limit.
      knowledge - A contextual object containing additional constraints or knowledge about the graph structure.
      Returns:
      A set of nodes that have been determined to block the paths based on the given constraints.
      Throws:
      InterruptedException - If the thread executing the method is interrupted during execution.

    • blockPathsRecursivelyVerbose

      public static Set<Node> blockPathsRecursivelyVerbose(Graph graph, Node x, Node y, Set<Node> containing, Set<Node> notFollowed, int maxPathLength, PrintStream out) throws InterruptedException
      Blocks paths recursively between two nodes in a graph while tracing the process.
      Parameters:
      graph - The graph in which the paths need to be blocked.
      x - The starting node of the path.
      y - The ending node of the path.
      containing - A set of nodes that must be included in the path to be blocked.
      notFollowed - A set of nodes that must not be followed during the traversal.
      maxPathLength - The maximum allowable path length for blocking. Paths exceeding this length are ignored.
      out - The PrintStream instance to output detailed trace information during recursive processing.
      Returns:
      A set of nodes representing the paths that were blocked during the process.
      Throws:
      InterruptedException - If the operation is interrupted during execution.

    • blockPathsRecursivelyVerbose

      public static Set<Node> blockPathsRecursivelyVerbose(Graph graph, Node x, Node y, Set<Node> containing, Set<Node> notFollowed, int maxPathLength, Knowledge knowledge, PrintStream out) throws InterruptedException
      Blocks paths recursively between two nodes in a graph with detailed verbose tracing output. This method utilizes a tracer to provide debug information for each step of the recursive path-blocking process.
      Parameters:
      graph - the graph in which paths are to be blocked
      x - the node from which to start blocking paths
      y - the node at which to stop blocking paths
      containing - a set of nodes that must be included in the paths to be blocked
      notFollowed - a set of nodes that must not be followed in the paths
      maxPathLength - the maximum allowable length of paths to be considered
      knowledge - additional domain-specific knowledge to guide the path-blocking process
      out - the print stream for verbose trace output
      Returns:
      a set of nodes representing the results of the path-blocking process
      Throws:
      InterruptedException - if the path-blocking process is interrupted

    • findPathToTarget

      public static RecursiveBlockingVerbose.Blockable findPathToTarget(Graph graph, Node a, Node b, Node y, Set<Node> path, Set<Node> z, int maxPathLength, Set<Node> notFollowed, Map<Node, Set<Node>> descendantsMap) throws InterruptedException
      Finds and returns a path from node 'a' to the target node 'b' in a given graph considering various constraints.
      Parameters:
      graph - The graph in which the pathfinding occurs.
      a - The starting node of the path.
      b - The target node of the path.
      y - An intermediary node that may influence the pathfinding process.
      path - A set of nodes representing the currently considered path.
      z - A set of excluded nodes that cannot be part of the path.
      maxPathLength - The maximum allowable path length.
      notFollowed - A set of nodes that should not be followed during pathfinding.
      descendantsMap - A map containing nodes and their respective descendants, used to guide the pathfinding logic.
      Returns:
      A Blockable object representing the discovered path or null if no path is found.
      Throws:
      InterruptedException - If the operation is interrupted while executing.

    • findPathToTarget

      public static RecursiveBlockingVerbose.Blockable findPathToTarget(Graph graph, Node a, Node b, Node y, Set<Node> path, Set<Node> z, int maxPathLength, Set<Node> notFollowed, Map<Node, Set<Node>> descendantsMap, RecursiveBlockingVerbose.Tracer tracer) throws InterruptedException
      Recursive method to find and evaluate the path between two nodes in a graph. The method determines if the path from a source node to a target node is blockable, unblockable, or indeterminate based on various conditions, including the presence of certain nodes, maximum path length, and contextual constraints provided by descendants and traced paths.
      Parameters:
      graph - The graph containing the nodes and edges for evaluation.
      a - The source node from which the path begins.
      b - The current node being evaluated along the path.
      y - The target node to which the path is being traced.
      path - A set of nodes constituting the current path. Used to prevent cycles during the evaluation.
      z - A set of conditioned nodes in the graph that must be considered during the path evaluation.
      maxPathLength - The maximum allowed length of the path. If -1, no limit is enforced.
      notFollowed - A set of nodes that should not be followed during path exploration.
      descendantsMap - A mapping from each node to the set of its descendants (direct or indirect) in the graph. Used for reachability evaluation.
      tracer - A utility object for logging, tracing, and debugging the recursive operations.
      Returns:
      A RecursiveBlockingVerbose.Blockable enum indicating whether the path is: - UNBLOCKABLE: The path to the target node is definitively possible without blocks. - BLOCKED: The path to the target node is definitively blocked. - INDETERMINATE: The path cannot be conclusively determined due to limitations such as interruption.
      Throws:
      InterruptedException - If the thread executing the method is interrupted during execution.