如何在NetworkX中基于节点类型过滤并折叠图边？

要实现你说的需求——只保留商店节点，同时把中间道路节点组成的路径合并成商店间的直接边，NetworkX有几种简洁的实现方式，下面是具体方案：

基础实现（适合小图） #

先构建示例图，再通过路径检测筛选并添加目标节点间的直接边：

import networkx as nx

# 构建示例图
G = nx.DiGraph()
# 添加节点并标记类型
G.add_nodes_from(["Store1", "Store2"], node_type="store")
G.add_nodes_from(["Road1", "Road2", "Road3"], node_type="road")
# 添加边
G.add_edges_from([
    ("Store1", "Road1"),
    ("Road1", "Road2"),
    ("Road2", "Road3"),
    ("Road3", "Store2")
])

# 1. 筛选出需要保留的商店节点
store_nodes = [n for n, attrs in G.nodes(data=True) if attrs["node_type"] == "store"]

# 2. 创建新的精简图
simplified_graph = nx.DiGraph()
simplified_graph.add_nodes_from(store_nodes, node_type="store")

# 3. 为每对商店节点添加直接边（如果它们之间存在仅经道路的路径）
for source in store_nodes:
    for target in store_nodes:
        if source == target:
            continue
        # 检查是否存在从source到target的路径，且路径中间无其他商店
        for path in nx.all_simple_paths(G, source=source, target=target):
            # 路径中间节点是path[1:-1]
            has_no_stores = all(G.nodes[n]["node_type"] != "store" for n in path[1:-1])
            if has_no_stores:
                simplified_graph.add_edge(source, target)
                break  # 找到一条有效路径就停止，避免重复加边

# 查看结果
print(list(simplified_graph.edges()))
# 输出: [('Store1', 'Store2')]

高效实现（适合大图） #

如果图的节点数量较多，遍历所有路径效率较低，可以利用可达性分析直接生成精简边：

import networkx as nx

# 复用上面的G和store_nodes定义

simplified_graph = nx.DiGraph()
simplified_graph.add_nodes_from(store_nodes, node_type="store")

for source in store_nodes:
    # 获取source能到达的所有节点，筛选其中的商店节点
    reachable_nodes = nx.descendants(G, source)
    reachable_stores = [n for n in reachable_nodes if n in store_nodes]
    # 为每个可达商店添加直接边
    for target in reachable_stores:
        simplified_graph.add_edge(source, target)

# 查看结果
print(list(simplified_graph.edges()))
# 输出: [('Store1', 'Store2')]

这种方法无需遍历所有路径，直接通过可达性判断性能更优。如果两个商店之间的路径中途经过其他商店，它会自动保留到中间商店的边（比如Store1->Road->Store3->Road->Store2会生成Store1->Store3和Store3->Store2），符合逻辑。

注意事项 #

• 若需要保留边的属性（比如路径长度、权重），可以在添加边时把中间路径的属性聚合后赋值给新边（例如把路径总长度作为新边的权重）
• 如果是无向图，只需把DiGraph换成Graph即可，逻辑完全通用

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