基于节点序列查找NetworkX中的路径

没问题，我来帮你实现这个需求！针对你给定的NetworkX有向图，我们可以通过以下步骤来获取以指定节点序列开头的所有路径：

核心思路 #

1. 验证起始序列有效性：先确认输入的节点序列在图中是真实存在的路径（每一对相邻节点之间都有对应的有向边），避免无效输入导致错误。
2. 生成后续延伸路径：以起始序列的最后一个节点为起点，找出所有从该节点出发的简单路径（包括节点本身，也就是长度为0的路径）。
3. 拼接完整路径：将起始序列的前半部分（除最后一个节点外）与每一条后续延伸路径拼接，得到最终的完整路径列表。

代码实现 #

import networkx as nx

def validate_start_sequence(digraph, start_seq):
    """验证起始节点序列是否是图中的有效路径"""
    for i in range(len(start_seq) - 1):
        if not digraph.has_edge(start_seq[i], start_seq[i+1]):
            raise ValueError(f"起始序列中不存在边 {start_seq[i]} -> {start_seq[i+1]}")

def generate_all_paths_from_node(digraph, start_node):
    """生成从指定节点出发的所有简单路径（包括节点本身）"""
    paths = [[start_node]]
    stack = [(start_node, [start_node])]
    
    while stack:
        current_node, current_path = stack.pop()
        # 遍历当前节点的所有邻居
        for neighbor in digraph.neighbors(current_node):
            # 避免循环（如果图中有环可保留此判断，你的示例图是无环DAG，也可去掉）
            if neighbor not in current_path:
                new_path = current_path + [neighbor]
                paths.append(new_path)
                stack.append((neighbor, new_path))
    return paths

def get_paths_starting_with_sequence(digraph, start_seq):
    """获取以指定节点序列为起始的所有路径"""
    # 先验证起始序列有效性
    validate_start_sequence(digraph, start_seq)
    # 获取起始序列的前缀（除最后一个节点外）
    prefix = start_seq[:-1]
    # 获取从最后一个节点出发的所有路径
    suffix_paths = generate_all_paths_from_node(digraph, start_seq[-1])
    # 拼接前缀和后缀路径
    full_paths = [prefix + path for path in suffix_paths]
    return full_paths

# 构建你的有向图
DG = nx.DiGraph()
attrs = {(1, 2), (2,3), (2,4), (4,5), (5, 6), (3,6), (6,7)}
DG.add_edges_from(attrs)

# 获取两组路径
paths_123 = get_paths_starting_with_sequence(DG, [1,2,3])
paths_124 = get_paths_starting_with_sequence(DG, [1,2,4])

all_path = [paths_123, paths_124]
print(all_path)

运行结果 #

执行上述代码后，输出结果与你的预期完全一致：

[[[1, 2, 3], [1, 2, 3, 6], [1, 2, 3, 6, 7]], [[1, 2, 4], [1, 2, 4, 5], [1, 2, 4, 5, 6], [1, 2, 4, 5, 6, 7]]]

额外说明 #

• 验证步骤可选：如果你能确保输入的起始序列一定有效，可以直接跳过validate_start_sequence函数的调用。
• 适配有环图：如果你的图存在环，generate_all_paths_from_node中的neighbor not in current_path判断可以避免无限循环，保证只生成简单路径。
• 扩展性强：这个方案可以适配任意合法的起始节点序列，只要序列在图中是有效路径即可。

内容的提问来源于stack exchange，提问作者KKK