[ENH] Add the ability to find Proper Possibly Directed Paths in a Graph

[aryan26roy]

Is your feature request related to a problem? Please describe.
This is in continuation of PR #1148 in Dowhy. First PR in an effort to provide seamless integration with Dowhy.

Describe the solution you'd like
A couple of functions that can take a graphs and find Proper Possibly Directed Paths in a graph.

[aryan26roy]

@adam2392 I have a question: The paper defines a proper directed path as follows: "A possibly directed path or possibly causal path from X to Y is a path from X to Y that does not contain an arrowhead pointing in the direction of X." Does this mean any edge (including undirected edge) is fine as long as an arrowhead doesn't point in the direction of X?

[adam2392]

Yep!

These are all valid X ... -o ..., Y, or X ... o-o ..., Y, or ``X ... o-> ..., Y, or X ... -- ..., Y`. So the check should be quite simple (hopefully).

• if checking a single path: if the path from X to Y contains at any point a directed edge towards X, it is not a possibly directed path
• if checking multiple paths: same as above

[aryan26roy]

@adam2392 for this I will need to first know all the paths from X to Y regardless of edge type. Is there a function that already does that?

[adam2392]

No, but one can possibly just convert to an undirected graph and then run: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.simple_paths.all_simple_paths.html#all-simple-paths

Not "as efficient" cuz of the conversion, but we can just leave an in-line comment there.

[aryan26roy]

@adam2392 continuing the conversation, if I just convert to an undirected graph and run "all_simple_paths" then I need to find a way to identify any edges that might contain an arrowhead pointing towards X. Once I convert to an undirected graph, I loose this information. One way is to do this is

• convert all the graphs to undirected graphs and then run "all_simple_paths"
• find all the arrowheads pointing towards X in all of the possible paths from X in the original graph. Then keep a map of all of these edges and check in the resulting path from step 1 if it contains any of these edges.

[adam2392]

Yeah I think it's pretty inefficient, but the only other way I can think of is a BFS/DFS style algorithm that just keeps track of edge types along each path.

However, I'm okay with a more inefficient algorithm initially and an inline comment documenting why its inefficient.

[aryan26roy]

Actually, I think the BFS/DFS style approach would be easier to implement. Since all I will have to do is check for a backwards arrow at each edge while keeping track of all the possible paths. For any path to be invalid, either it has a backwards arrow or it doesn't lead to Y. Otherwise, return all paths.

[aryan26roy]

Of course, this will be more memory intensive since I will have to keep all the possible paths in memory, which makes me wonder whether this approach would in fact be worse for larger graphs.

[aryan26roy]

On second thought, in method 1, both the steps are essentially BFS/DFS with all the paths being kept track of in memory. This would mean the same memory intensive procedure being done twice.
And the step 2 in method 1 is essentially method 2.
I think we should go with the second method from the start.

[adam2392]

Sounds good!