Class ValidOrderIterator

java.lang.Object
edu.cmu.tetrad.graph.ValidOrderIterator
All Implemented Interfaces:
Iterable<List<Node>>, Iterator<List<Node>>
public final class ValidOrderIterator extends Object implements Iterator<List<Node>>, Iterable<List<Node>>
Lazily enumerates EVERY valid causal order of a DAG or CPDAG, each exactly once.

A valid order is a topological order of some consistent DAG extension of the graph. This is the enumerating generalization of Bryan Andrews' getValidOrder: that method peels off, at each step, the FIRST node (in a supplied order) that can legally be the last node of an extension -- a Dor-Tarsi valid sink: no child, and its undirected neighbors form a clique. Here we instead branch over ALL valid sinks at each peel. Each complete sequence of sink choices is one valid order (reversed); each order arises from exactly one sequence; and by the standard collider argument every topological order of every consistent extension is reachable -- so this yields each valid order once, none missed.

The enumeration is lazy and uses O(n^2) working memory (it operates on an induced-subgraph membership set rather than copying the graph), so the potentially exponential number of orders is fine to iterate and break out of early.

The first order produced equals getValidOrder(initialOrder, forward) for the same arguments, and subsequent orders relax that greedy first-fit in DFS order -- a useful cross-check.

Assumes a DAG or CPDAG (no bidirected edges; for a raw PDAG the undirected-neighbor clique test is not sufficient). A well-formed CPDAG always has at least one valid sink at every step; a cyclic/malformed input simply yields no orders (empty iterator).

Author:
josephramsey

  • Constructor Details

    • ValidOrderIterator

      public ValidOrderIterator(Graph graph)
      Enumerate preferring the graph's own node order (forward).
      Parameters:
      graph - a DAG or CPDAG.

    • ValidOrderIterator

      public ValidOrderIterator(Graph graph, List<Node> initialOrder, boolean forward)
      Iterates over valid orders for a CPDAG.
      Parameters:
      graph - a DAG or CPDAG.
      initialOrder - orders are produced preferring to keep nodes close to this order; the first order returned matches getValidOrder(initialOrder, forward).
      forward - whether the preference runs in the forward (true) or reverse (false) direction, matching getValidOrder.

  • Method Details