is_simple_path#
- is_simple_path(G, nodes)[source]#
Returns True if and only if
nodes
form a simple path inG
.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:
- Ggraph
A NetworkX graph.
- nodeslist
A list of one or more nodes in the graph
G
.
- Returns:
- bool
Whether the given list of nodes represents a simple path in
G
.
Notes
An empty list of nodes is not a path but 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
Additional backends implement this function
graphblas : OpenMP-enabled sparse linear algebra backend.