基于Start、End节点列排序道路路段并新增道路起止节点列的方法

我有一张符合上述逻辑的表，其中包含一条由多个路段组成的道路，每个路段都对应有start节点和stop节点。我该如何对该表进行排序，使得每条道路的所有路段按实际关联顺序排列（该顺序非数值顺序，由start、end节点的关联关系决定）？排序完成后我还需要新增两列Start和End，用于标识整条道路的起点节点和终点节点。上述表格对应的预期输出如下：

问题配套示例数据：

import pandas as pd
data = [['Road_id','Segment_id','Start_node','End_node'], [1,8285,4740,4741], [1,8509,4741,5144], [1,8437, 5016,5017], [1,8447, 5031, 5016], [1, 8520, 5144,5168], [1,9104,5168,4785],[1,8550,5017,4740]]
df = pd.DataFrame(data[1:], columns = data[0]) 

实现思路 #

• 按道路ID分组处理，支持同时处理多条独立道路
• 对单条道路，先统计所有节点的出现情况：整条道路的起点是仅出现在Start_node列、从未出现在End_node列的节点
• 从起点开始，依次匹配下一个路段的Start_node等于当前路段的End_node，遍历所有路段即可得到按连通关系排序的列表
• 排序完成后取首路段的起点、末路段的终点，统一填充到新增的Start和End列即可

代码实现 #

def sort_road_segments(group):
    # 建立起始节点到路段行的映射，方便快速查找
    node_map = {row['Start_node']: row for _, row in group.iterrows()}
    # 查找整条道路的起点
    end_node_set = set(group['End_node'])
    road_start = [s for s in group['Start_node'] if s not in end_node_set][0]
    # 按连通关系拼接路段
    sorted_segs = []
    current_node = road_start
    while current_node in node_map:
        current_seg = node_map[current_node]
        sorted_segs.append(current_seg)
        current_node = current_seg['End_node']
    # 构造排序后的DataFrame并补充全局起终点列
    sorted_df = pd.DataFrame(sorted_segs)
    road_end = sorted_df.iloc[-1]['End_node']
    sorted_df['Start'] = road_start
    sorted_df['End'] = road_end
    return sorted_df

# 按Road_id分组执行排序逻辑
result_df = df.groupby('Road_id', group_keys=False).apply(sort_road_segments).reset_index(drop=True)
print(result_df)

注：如果你的场景包含环形道路，可以修改起点查找逻辑，任选一个节点作为起点遍历即可。

内容的提问来源于stack exchange，提问作者Wee How Chan