gradgraph.graph.paths module

find_apical_paths(G, weight=None, sort_neighbors=None)[source]

Find all apical paths in an undirected subcubic graph.

An apical path is defined as a simple path that starts from a leaf node (degree == 1), follows edges toward neighbors with non-increasing node weights, and terminates when reaching a node of degree > 2. Each path is returned as a sequence of nodes ordered from the branchpoint (high-degree node) down to the apex (leaf).

Parameters:

  • G (networkx.Graph) – Undirected input graph. Assumed to be subcubic (maximum degree ≤ 3).

  • weight (str or None, optional) – Node attribute key to use for weight comparisons. If None, no weight constraints are applied (paths follow only structure).

  • sort_neighbors (callable or None, optional) – Function to control the traversal order of neighbors. Should accept an iterable of nodes and return an iterable (e.g., sorted). If None, neighbors are visited in the order from G.neighbors.

Yields:

path (numpy.ndarray of shape (k,)) – Array of node identifiers representing one apical path, ordered from the branchpoint (degree > 2 node) to the apex (degree == 1 node).

Notes

  • A node is considered an apex if its degree is 1 (a leaf).

  • Paths are simple (no repeated nodes).

  • If weight is given, traversal only proceeds to neighbors with weight less than or equal to the current node’s weight.

Examples

>>> import networkx as nx
>>> import numpy as np
>>> G = nx.Graph()
>>> G.add_nodes_from([
...     (1, {"w": 3}),
...     (2, {"w": 2}),
...     (3, {"w": 1}),
...     (4, {"w": 1}),
...     (5, {"w": 1}),
...     (6, {"w": 1}),
... ])
>>> G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 5), (4, 6)])
>>> for path in find_apical_paths(G, weight="w"):
...     print(path)
[4 3 2 1]
[4 5]
[4 6]