Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

networkx.algorithms.simple_paths.is_simple_path

is_simple_path(G, nodes)

Returns True if and only if the given nodes form a simple path in G.

A simple path in a graph is a nonempty sequence of nodes in which no node appears more than once in the sequence, and each adjacent pair of nodes in the sequence is adjacent in the graph.

Parameters:nodes (list) – A list of one or more nodes in the graph G. Returns:Whether the given list of nodes represents a simple path in G. Return type:bool

Notes

A list of zero nodes is not a path and a list of one node is a path. Here’s an explanation why.

This function operates on node paths. One could also consider edge paths. There is a bijection between node paths and edge paths.

The length of a path is the number of edges in the path, so a list of nodes of length n corresponds to a path of length n - 1. Thus the smallest edge path would be a list of zero edges, the empty path. This corresponds to a list of one node.

To convert between a node path and an edge path, you can use code like the following:

>>> from networkx.utils import pairwise
>>> nodes = [0, 1, 2, 3]
>>> edges = list(pairwise(nodes))
>>> edges
[(0, 1), (1, 2), (2, 3)]
>>> nodes = [edges[0][0]] + [v for u, v in edges]
>>> nodes
[0, 1, 2, 3]

Examples

>>> G = nx.cycle_graph(4)
>>> nx.is_simple_path(G, [2, 3, 0])
True
>>> nx.is_simple_path(G, [0, 2])
False