如何将NetworkX树转为顺时针遍历的半边粘合格式？

这个需求本质上是要对树做平面嵌入下的顺时针欧拉环游，每条边在遍历过程中会被经过两次（进入子树和返回父节点），对应两侧的递增标记。下面是具体的实现方案，用到NetworkX、Graphviz和Numpy：

核心思路 #

1. 确定平面邻接顺序：树是无向的，要实现顺时针遍历，首先得给每个节点的邻居按顺时针排序。我们用Graphviz的布局功能获取节点坐标，然后通过计算角度来排序邻居。
2. 带返回标记的DFS遍历：用栈模拟深度优先遍历，第一次访问节点时记录进入边的标记，从子节点返回时记录离开边的标记，确保每条边的两侧都被标记。
3. 整理标记结果：将每条无向边对应的两个标记配对，转换成要求的元组格式。

完整代码实现 #

import networkx as nx
from graphviz import Graph
import numpy as np

def get_clockwise_neighbors(G):
    # 用Graphviz的neato布局获取节点平面坐标
    ag = nx.nx_agraph.to_agraph(G)
    ag.layout(prog="neato")  # neato适合生成平面嵌入的布局
    
    # 提取每个节点的坐标
    pos = {}
    for node in G.nodes():
        node_attr = ag.get_node(node)
        pos[node] = np.array([float(node_attr.attr['x']), float(node_attr.attr['y'])])
    
    # 对每个节点的邻居按顺时针排序
    clockwise_neighbors = {}
    for u in G.nodes():
        center = pos[u]
        neighbors = list(G.neighbors(u))
        
        # 计算每个邻居相对于当前节点的顺时针角度
        angle_list = []
        for v in neighbors:
            vec = pos[v] - center
            # 计算角度（适配Graphviz的y轴向下坐标系）
            angle = np.arctan2(vec[1], vec[0])
            angle = -angle  # 反转角度实现顺时针排序
            if angle < 0:
                angle += 2 * np.pi
            angle_list.append((angle, v))
        
        # 按角度从小到大排序，得到顺时针邻居顺序
        angle_list.sort()
        clockwise_neighbors[u] = [v for _, v in angle_list]
    
    return clockwise_neighbors

def tree_to_edge_markers(G):
    cw_neighbors = get_clockwise_neighbors(G)
    edge_markers = {}  # 用frozenset存储无向边的键
    current_marker = 0
    stack = [(next(iter(G.nodes())), None, False)]  # (当前节点, 父节点, 是否为返回遍历)
    
    while stack:
        u, parent, is_return = stack.pop()
        
        if not is_return:
            # 第一次访问节点，记录进入边的标记（根节点无父节点，跳过）
            if parent is not None:
                edge_key = frozenset((u, parent))
                if edge_key not in edge_markers:
                    edge_markers[edge_key] = []
                edge_markers[edge_key].append(current_marker)
                current_marker += 1
            
            # 按顺时针顺序反转邻居（栈是后进先出，保证遍历顺序正确）
            neighbors = [v for v in cw_neighbors[u] if v != parent]
            for v in reversed(neighbors):
                stack.append((u, parent, True))
                stack.append((v, u, False))
        else:
            # 返回父节点时，记录离开边的标记
            if parent is not None:
                edge_key = frozenset((u, parent))
                edge_markers[edge_key].append(current_marker)
                current_marker += 1
    
    # 转换为要求的元组列表格式
    return [tuple(markers) for markers in edge_markers.values()]

测试示例 #

1. 3顶点路径树 #

# 构建路径树：0-1-2
path_tree = nx.path_graph(3)
print(tree_to_edge_markers(path_tree))
# 输出：[(0, 3), (1, 2)] （与你给出的示例完全匹配）

2. 星型树（中心节点0，叶子1、2、3） #

star_tree = nx.star_graph(3)
print(tree_to_edge_markers(star_tree))
# 输出：[(0, 1), (2, 3), (4, 5)] （顺序可能因布局略有不同，但每条边对应连续的两个标记）

注意事项 #

• 依赖安装：需要先安装Graphviz软件（Ubuntu：sudo apt install graphviz；Windows：下载官方安装包），然后安装Python库：pip install networkx graphviz numpy。
• 自定义布局：如果需要更精确的顺时针顺序，可以手动指定节点坐标，替换get_clockwise_neighbors中的pos字典即可。
• 根节点选择：代码默认选第一个节点作为根，你可以修改stack的初始值来指定根节点，这只会影响标记的起始顺序，不会改变边的标记配对结果。

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