pywhy_graphs.algorithms.all_semi_directed_paths

pywhy_graphs.algorithms.all_semi_directed_paths(G, source: int | float | str | Any, target: int | float | str | Any, cutoff: int = None)

Generate all semi-directed paths from source to target in G.

A semi-directed path is a path from source to target in that no end-point is directed from target to source. I.e. target *-> source does not exist.

Parameters:

GGraph

The graph.

sourceNode

The source node.

targetNode

The target node.

cutoffinteger, optional

Depth to stop the search. Only paths of length <= cutoff are returned.

Notes

This algorithm is very similar to networkx’s networkx.algorithms.simple_paths.all_simple_paths() function.

This algorithm uses a modified depth-first search to generate the paths [1]. A single path can be found in $O(V+E)$ time but the number of semi-directed paths in a graph can be very large, e.g. $O(n!)$ in the complete graph of order $n$.

This function does not check that a path exists between source and target. For large graphs, this may result in very long runtimes. Consider using has_path to check that a path exists between source and target before calling this function on large graphs.

References

[1]

R. Sedgewick, “Algorithms in C, Part 5: Graph Algorithms”, Addison Wesley Professional, 3rd ed., 2001.