causaldag.classes.dag.DAG.chickering_sequence¶

DAG.chickering_sequence(imap, verbose=False)[source]¶

Return a Chickering sequence from this DAG to an I-MAP imap.

A Chickering sequence from DAG D1 to a DAG D2 is a sequence of DAGs starting at D1 and ending at D2, with consecutive DAGs differing by a single edge reversal or edge deletion, such that each DAG is an IMAP of D1.

See Chickering, David Maxwell. “Optimal structure identification with greedy search.” (2002) for more details.

Parameters:	imap (DAG) – The I-MAP of this DAG at which the Chickering sequence will end.

Examples

>>> import causaldag as cd
>>> d1 = cd.DAG(arcs={(0, 1), (1, 2)})
>>> d2 = cd.DAG(arcs={(2, 0), (2, 1), (1, 0)})
>>> sequence, moves = d1.chickering_sequence(d2)
>>> sequence[1].arcs
{(1, 0), (1, 2)}
>>> sequence[2].arcs
{(1, 0), (1, 2), (2, 0)}