graphical_models.classes.dags.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

>>> from graphical_models import DAG
>>> d1 = DAG(arcs={(0, 1), (1, 2)})
>>> d2 = 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)}
>>> moves
[
    {'sink': 0, 'move': 6, 'd': 2},
    {'sink': 0, 'move': 4},
    {'sink': 1, 'move': 6, 'd': 2}
]