3.4.1. pywhy_graphs.algorithms.acyclification

pywhy_graphs.algorithms.acyclification(G: MixedEdgeGraph, directed_edge_type: str = 'directed', bidirected_edge_type: str = 'bidirected', copy: bool = True) → MixedEdgeGraph

Acyclify a cyclic graph.

Applies the acyclification procedure presented in [1]. This converts to G to what is called \(G^{acy}\) in the reference.

Parameters:

Gpywhy_nx.MixedEdgeGraph

A graph with cycles.

directed_edge_typestr

The name of the sub-graph of directed edges.

bidirected_edge_typestr

The name of the sub-graph of bidirected edges.

copybool

Whether to operate on the graph in place, or make a copy.

Returns:

Gpywhy_nx.MixedEdgeGraph

The acyclified graph.

Notes

This replaces all strongly connected components of G by fully connected bidirected components without any directed edges. Then any node with an edge pointing into the SC (i.e. a directed edge, or bidirected edge) is made fully connected with the nodes of the SC either with a directed, or bidirected edge.

References

[1]

Joris M. Mooij and Tom Claassen. Constraint-based causal discovery using partial ancestral graphs in the presence of cycles. In Jonas Peters and David Sontag, editors, Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), volume 124 of Proceedings of Machine Learning Research, 1159–1168. PMLR, 03–06 Aug 2020. URL: https://proceedings.mlr.press/v124/m-mooij20a.html.