graphical_models.classes.dags.dag.DAG.greedy_optimal_fully_orienting_interventions

DAG.greedy_optimal_fully_orienting_interventions(cpdag=None)[source]

Find a set of interventions which fully orients a CPDAG into this DAG, using greedy selection of the interventions. By submodularity, the number of interventions is a (1 + ln K) multiplicative approximation to the true optimal number of interventions, where K is the number of undirected edges in the CPDAG.

Parameters: cpdag – the starting CPDAG containing known orientations. If None, use the observational essential graph.
Returns: The selected interventions and the associated cpdags that they induce.
Return type: (interventions, cpdags)

Examples

>>> from graphical_models import DAG
>>> d = DAG(arcs={(0, 1), (1, 2), (0, 2), (0, 3), (1, 3), (2, 3)})
>>> ivs, icpdags = d.greedy_optimal_fully_orienting_interventions()
>>> ivs
[1, 2]
>>> icpdags[0].edges
{frozenset({2, 3})}
>>> icpdags[1].edges
set()