Networkx工具问询：无向/有向图交点及路径起止节点获取

1. 获取无向图/有向图的交点节点 #

首先明确：你说的“交点节点”指的是多条路径交汇的核心节点，通常对应度数大于2的节点（无向图），或有向图中满足入度/出度/总度数符合多路径交汇特征的节点。

无向图的交点节点获取 #

直接筛选度数≥3的节点即可，NetworkX的degree()方法可快速获取节点度数：

import networkx as nx

# 构建示例无向图
G_undir = nx.Graph()
G_undir.add_edges_from([(1,2), (2,3), (2,4), (4,5), (4,6)])

# 获取度数≥3的交点节点
intersection_nodes_undir = [node for node, deg in G_undir.degree() if deg >= 3]
print("无向图交点节点:", intersection_nodes_undir)  # 输出: [2,4]

有向图的交点节点获取 #

有向图需区分入度、出度，按需选择：

• 入度≥2（多个节点指向它）：

G_dir = nx.DiGraph()
G_dir.add_edges_from([(1,2), (3,2), (2,4), (4,5), (4,6)])

# 获取入度≥2的交点节点
intersection_nodes_dir_in = [node for node, deg in G_dir.in_degree() if deg >= 2]
print("有向图入度型交点:", intersection_nodes_dir_in)  # 输出: [2]

• 出度≥2（它指向多个节点）：

intersection_nodes_dir_out = [node for node, deg in G_dir.out_degree() if deg >= 2]
print("有向图出度型交点:", intersection_nodes_dir_out)  # 输出: [2,4]

• 总度数（入+出）≥3：

intersection_nodes_dir_total = [node for node in G_dir.nodes() if G_dir.in_degree(node) + G_dir.out_degree(node) >=3]
print("有向图总度数型交点:", intersection_nodes_dir_total)  # 输出: [2,4]

2. 基于交点节点的路径分组 #

核心是把图分解成以交点/叶子节点（度数1）为端点的路径段，通过移除交点节点后提取连通分量，再补全端点信息：

无向图的路径分组实现 #

def get_path_groups_undir(G, intersection_nodes):
    # 复制原图避免修改原数据
    temp_G = G.copy()
    temp_G.remove_nodes_from(intersection_nodes)
    components = list(nx.connected_components(temp_G))
    path_groups = []
    
    for comp in components:
        if len(comp) == 1:
            # 单个叶子节点，找到它连接的交点
            leaf_node = next(iter(comp))
            neighbor = next(iter(G.neighbors(leaf_node)))
            path_groups.append((leaf_node, neighbor))
        else:
            # 路径分量，找到两端节点对应的交点
            subpath_nodes = list(comp)
            start, end = subpath_nodes[0], subpath_nodes[-1]
            start_inter = next(iter(set(G.neighbors(start)) - comp))
            end_inter = next(iter(set(G.neighbors(end)) - comp))
            path_groups.append((start_inter, end_inter))
    
    # 补充直接连接两个交点的边
    for u, v in G.edges():
        if u in intersection_nodes and v in intersection_nodes:
            if (u,v) not in path_groups and (v,u) not in path_groups:
                path_groups.append((u,v))
    
    return path_groups

# 测试示例
path_groups = get_path_groups_undir(G_undir, intersection_nodes_undir)
print("无向图路径分组:", path_groups)
# 输出: [(1,2), (2,4), (5,4), (6,4)]

有向图的路径分组实现 #

需处理方向，提取从起点到终点的路径段：

def get_path_groups_dir(G, intersection_nodes):
    temp_G = G.copy()
    temp_G.remove_nodes_from(intersection_nodes)
    path_groups = []
    
    # 处理每个弱连通分量
    for comp in nx.weakly_connected_components(temp_G):
        subG = temp_G.subgraph(comp)
        starts = [n for n in subG.nodes() if subG.in_degree(n) == 0]
        ends = [n for n in subG.nodes() if subG.out_degree(n) == 0]
        for start in starts:
            for end in ends:
                # 找到起点关联的交点
                start_inter = next(iter(G.predecessors(start))) if G.in_degree(start) >0 else next(iter(G.successors(start)))
                # 找到终点关联的交点
                end_inter = next(iter(G.successors(end))) if G.out_degree(end) >0 else next(iter(G.predecessors(end)))
                path_groups.append((start_inter, end_inter))
    
    # 补充直接连接两个交点的有向边
    for u, v in G.edges():
        if u in intersection_nodes and v in intersection_nodes:
            path_groups.append((u,v))
    
    return path_groups

# 测试示例
path_groups_dir = get_path_groups_dir(G_dir, intersection_nodes_dir_total)
print("有向图路径分组:", path_groups_dir)

以上代码可实现你需要的路径分组效果，每个组对应一段以交点或起止节点为端点的路径。

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