Class ConsistentDagIterator

java.lang.Object
edu.cmu.tetrad.graph.ConsistentDagIterator
All Implemented Interfaces:
Iterable<Graph>, Iterator<Graph>
public final class ConsistentDagIterator extends Object implements Iterator<Graph>, Iterable<Graph>
Lazily enumerates the consistent DAG extensions of a DAG or CPDAG.

This is the graph-valued companion to the valid-order enumeration. It runs the same Dor-Tarsi sink-peeling DFS (peel a node with no child whose undirected neighbors form a clique, branching over ALL valid sinks), but at each peel it orients every undirected neighbor z--x into the sink as z->x, so a completed peel sequence is a consistent extension.

With distinct (the default) each extension is emitted exactly once. A single extension is a topological order of many peel sequences; two peel sequences produce the same DAG iff they differ only by transposing adjacent nodes that are NON-adjacent in the graph (such a swap flips no edge). The lexicographically-minimal (by rank) sequence of each such class is characterized by having no adjacent commuting inversion, so we forbid one incrementally: a sink x is peeled after prev only unless x shares no edge with prev and outranks it (in which case x could have been peeled before prev for the same DAG -- a non-canonical duplicate, deferred). This reaches each distinct DAG exactly once WITHOUT generating the duplicate orders, at O(n) working memory. With distinct == false the prune is off and every valid order yields a DAG.

Ranks come from initialOrder/forward exactly as in getValidOrder; the first extension emitted is the one that method's order induces.

Cost note: the prune removes the linear-extension blowup for the common case (e.g. an edgeless or near-edgeless component no longer costs n! -- it costs about the number of rank-increasing prefixes). It is NOT output-polynomial in the worst case, though: a component with many simplicial vertices that are simultaneously valid sinks and pairwise non-adjacent (a large star, say) can still explore up to ~2^k dead-end prefixes to emit k+1 DAGs, because a lower-rank node blocked only transitively (through a shared neighbor) cannot be pruned by the adjacent-pair test. When that bites, enumerate the acyclic moral orientations of the chordal component directly with a clique-tree method (polynomial delay); ask and I'll wire it up.

Assumes a DAG or CPDAG (no bidirected/circle endpoints; the undirected-neighbor clique test is complete only for a completed PDAG). A malformed cyclic input simply yields nothing.

Author:
josephramsey

  • Constructor Details

    • ConsistentDagIterator

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

    • ConsistentDagIterator

      public ConsistentDagIterator(Graph graph, List<Node> initialOrder, boolean forward, boolean distinct)
      Iterates over DAGs consistent with a given CPDAG.
      Parameters:
      graph - a DAG or CPDAG.
      initialOrder - rank source: the first extension emitted is the one induced by getValidOrder(initialOrder, forward).
      forward - forward (true) or reverse (false) rank preference.
      distinct - true to emit each consistent extension exactly once; false to emit one DAG per valid order (i.e. with linear-extension multiplicity).

  • Method Details