causaldag.classes.dag.DAG.greedy_optimal_fully_orienting_interventions

DAG.greedy_optimal_fully_orienting_interventions(cpdag=None)

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

>>> import causaldag as cd
>>> d = cd.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()