Class LegEnumerator

java.lang.Object
edu.cmu.tetrad.graph.LegEnumerator
All Implemented Interfaces:
Iterable<Graph>, Iterator<Graph>
public final class LegEnumerator extends Object implements Iterator<Graph>, Iterable<Graph>
Lazily enumerates the Loyal Equivalent Graphs (LEGs) of a directed Markov equivalence class by walking the class transformationally, via Zhang & Spirtes' legitimate directed-edge reversals rather than by re-orienting the circle component from scratch.

A LEG of a DMAG is a Markov-equivalent MAG whose bidirected edges are all invariant (equivalently, the class members with the fewest bidirected edges); see Zhang & Spirtes (2005), "A Transformational Characterization of Markov Equivalence for Directed Acyclic Graphs with Latent Variables," UAI 2005 (arXiv:1207.1419), Prop. 2. The enumeration starts from one LEG -- e.g. GraphTransforms.zhangMagFromPag(pag), whose only bidirected edges are the PAG's invariant <-> edges -- and does a breadth-first search over the class using:

Legitimate edge reversal (Lemma 2). Reversing A -> B preserves Markov equivalence iff Pa(B) = Pa(A) union {A} and Sp(B) = Sp(A) (parents, resp. spouses). This is the MAG generalization of Chickering's covered-edge reversal (drop spouses and it is exactly the covered edge). Two facts make the walk clean:

  • A reversal flips one directed edge and touches no bidirected edge, so the invariant bidirected set is preserved -- every graph visited is again a LEG.
  • An invariant directed edge cannot satisfy Lemma 2 (if it did, it would be reversible), so the walk never disturbs an invariant mark.
Hence no per-step legality or equivalence re-check is required: each move yields a legal MAG in the same class by construction. Completeness -- that BFS from one LEG reaches ALL of them -- is Theorem 2: the LEG set is connected under legitimate reversals, with every intermediate graph a LEG.

Compared with enumerating the circle component's acyclic moral orientations, this branches on the currently reversible edges rather than on sink orders, so it sidesteps the linear-extension / simplicial blowup; the first LEG emitted is the seed. Cost: a visited set of size O(#LEGs) is kept to emit each once (#LEGs = the number of AMOs of the circle component), so memory scales with the class, unlike the O(n) circle-orientation iterator. For the small-model regime this is the intended tradeoff.

Scope. The transformational characterization is for DIRECTED MAGs; with selection bias (undirected edges) a single mark change breaks ancestrality (Zhang & Spirtes, Fig. 6), so Lemma-2 reversal is not complete. This class therefore rejects a start graph containing an undirected edge; drop back to the circle-resolution enumeration in that case.

Author:
josephramsey

  • Field Details

    • VERBOSE

      public static volatile boolean VERBOSE
      Static verbose.

  • Constructor Details

    • LegEnumerator

      public LegEnumerator(Graph startLeg)
      Enumerates over LEGs starting wiht the given LEG.
      Parameters:
      startLeg - a LEG of the class (e.g. GraphTransforms.zhangMagFromPag(pag)). Its bidirected edges must all be invariant; if it is a genuine LEG the whole LEG set is reached (Theorem 2). Must contain no undirected edge.

  • Method Details

    • fromPag

      public static LegEnumerator fromPag(Graph pag)
      Seeds the enumeration from the canonical Zhang MAG of a PAG, which is a LEG.
      Parameters:
      pag - the PAG whose (directed) equivalence class is to be enumerated.
      Returns:
      an enumerator over the class's LEGs.

    • iterator

      public Iterator<Graph> iterator()
      Specified by:
      iterator in interface Iterable<Graph>

    • hasNext

      public boolean hasNext()
      Specified by:
      hasNext in interface Iterator<Graph>

    • next

      public Graph next()
      Specified by:
      next in interface Iterator<Graph>