3.2.3. pywhy_graphs.algorithms.uncovered_pd_path#
- pywhy_graphs.algorithms.uncovered_pd_path(graph: PAG, u: int | float | str | Any, c: int | float | str | Any, max_path_length: int | None = None, first_node: int | float | str | Any | None = None, second_node: int | float | str | Any | None = None, force_circle: bool = False, forbid_node: int | float | str | Any | None = None) Tuple[List[int | float | str | Any], bool][source]#
Compute uncovered potentially directed (pd) paths from u to c.
In a pd path, the edge between V(i) and V(i+1) is not an arrowhead into V(i) or a tail from V(i+1). An intuitive explanation given in [1] notes that a pd path could be oriented into a directed path by changing circles into tails or arrowheads.
In addition, the path is uncovered, meaning every node beside the endpoints are unshielded, meaning V(i-1) and V(i+1) are not adjacent.
A special case of a uncovered pd path is an uncovered circle path, which appears as u o-o … o-o c.
- Parameters:
- graphPAG
PAG to orient.
- unode
A node in the graph to start the uncovered path.
- cnode
A node in the graph.
- max_path_lengthoptional, int
The maximum distance to check in the graph. By default None, which sets it to 1000.
- first_nodenode, optional
The node previous to ‘u’. If it is before ‘u’, then we will check that ‘u’ is unshielded. If it is not passed, then ‘u’ is considered the first node in the path and hence does not need to be unshielded. Both ‘first_node’ and ‘second_node’ cannot be passed.
- second_nodenode, optional
The node after ‘u’ that the path must traverse. Both ‘first_node’ and ‘second_node’ cannot be passed.
- force_circle: bool
Whether to search for only circle paths (u o-o … o-o c) or all potentially directed paths. By default False, which searches for all potentially directed paths.
- forbid_node: node, optional
A node after ‘u’ which is forbidden to immediately traverse when searching for a path.
Notes
The definition of an uncovered pd path is taken from [1].
Typically uncovered potentially directed paths are defined by two nodes. However, in one use case within the FCI algorithm, it is defined relative to an adjacent third node that comes before ‘u’.
In certain cases (e.g. R5 of FCI) an uncovered pd path must be found between two variables, but these variables are already adjacent and connected by a trivial uncovered pd path. To prevent the function from returning this trivial path, the ‘forbid_node’ argument can be used.
References