一个字典，其中的值可以是列表，也可以是列表的列表。

Question

我正在尝试使用networkx库绘制卡车路线优化的结果。首先，我需要准备数据，但目前遇到了困难。

这是初始数据的一个小例子：

| 车辆 | 路线           |
| ---- | -------------- |
| 0    | [0,3](V0)     |
| 1    | [3,0](V0)     |
| 2    | [0,3](V1)     |
| 3    | [0,8](V1)     |
| 4    | [2,0](V1)     |
| 5    | [3,2](V1)     |
| 6    | [8,0](V1)     |

这里有两辆卡车：V0和V1。V0的路线是0到3再到0。而V1有两条路线：0到8再到0以及0到3再到2再到0。

每个行程都必须从节点0开始并在0结束。

我需要解决两个问题：

对于每辆卡车（V0、V1），在给定列表中找到所有以0开始并以0结束的行程。
行程流不能有中断：每个子行程的终点[0,8]必须是下一个子行程[8,0]的起点。

最终结果应为：

{'V0': [0,3,0], 'V1': [[0,3,2,0], [0,8,0]]}

我已经编写了一段代码，但是它并没有得到我想要的结果：

tours = {'V0': ['0,3', '3,0'], 'V1': ['0,3', '0,8', '2,0', '3,2', '8,0']}

# 定义将字符串转换为列表的函数
def convert_to_list(s):
    return list(map(int, s.split(',')))

# 定义处理'tours'字典中每个值的函数
def process_value(value):
    result = []
    current_list = []

    for pair in value:
        pair_list = convert_to_list(pair)

        if not current_list or pair_list[0] == 0:
            current_list.extend(pair_list)
        elif pair_list[1] == 0:
            current_list.append(pair_list[0])
            current_list.append(0)
            result.append(current_list)
            current_list = [0]
        else:
            current_list.append(pair_list[0])

    if current_list:
        current_list.append(0)
        result.append(current_list)

    return result

# 创建处理后的'tours1'字典
tours1 = {key: process_value(value) for key, value in tours.items()}

# 打印结果
print(tours1)

输出结果：

{'V0': [[0, 3, 3, 0], [0, 0]], 'V1': [[0, 3, 0, 8, 2, 0], [0, 3, 8, 0], [0, 0]]}

有没有改进这段代码的想法或解决方案？非常感谢！

tvanfosson · Answer

以下是当没有节点可以被访问两次时，一个时间复杂度为O(N²)的可行解决方案，其中N为节点数量：

tours = {'V0': ['0,3', '3,0'], 'V1': ['0,3', '0,8', '2,0', '3,2', '8,0']}

def process(value):
    result = []  # 最终结果列表

    nodes = {}  # 存储起始节点与终止节点形式的字典
    starts = []  # 存储起始节点为0的起止节点对列表

    for val in value:  # 遍历每一行程
        a, b = val.split(",")  # 获取起始点和终止点
        nodes[a] = b  # 将节点添加至nodes字典
        if a == "0":  # 如果行程起始于0，则将其加入starts列表
            starts.append((a, b))

    for a, b in starts:  # 遍历每一个起始点
        inter = [a, b]  # 初始化一个代表一条路线的列表
        while b != "0":  # 只要还没回到0节点，就继续循环
            b = nodes[b]  # 获取下一个节点
            inter.append(b)  # 将该节点添加到路线列表中
        result.append(inter)

    return result


def convert():
    """
    遍历每辆卡车及其路线，并对其进行处理。
    """
    result_dict = {}  # 结果字典
    for truck, routes in tours.items():
        result_dict[truck] = process(routes)
    return result_dict


print(convert())

这段代码执行后得到了如下的结果：

{'V0': [['0', '3', '0']], 'V1': [['0', '3', '2', '0'], ['0', '8', '0']]]

如果你想让第二个列表也只包含一层维度，你只需在process方法中增加一个判断条件，如下所示：

def process(value):
    # ...（保持原有代码不变直到最后return语句前）

    if len(result) == 1:
        return result[0]
    return result

David Segonds · Answer

主要思路是将数据组织成一棵树，然后通过深度优先搜索（DFS）来提取有效的路径。

步骤一：将数据组织成树结构：

tours = {'V0': ['0,3', '3,0'], 'V1': ['0,3', '0,8', '2,0', '3,2', '8,0']}

tours2 = {}

for vehicle, routes in tours.items():
    route_tree = {}
    for route in routes:
        from_node, to_node = route.split(',')
        from_node = int(from_node)
        to_node = int(to_node)
        
        if from_node in route_tree:
            route_tree[from_node].append(to_node)
        else:
            route_tree[from_node] = [to_node]
    tours2[vehicle] = route_tree

经过处理后，tours2的数据结构如下：

{'V0': {0: [3], 3: [0]}, 'V1': {0: [3, 8], 2: [0], 3: [2], 8: [0]}}

步骤二：通过DFS寻找有效路径：

routes = {}

for vehicle in tours2:
    running_routes = [[0]]
    completed_routes = []

    while running_routes:
        current_route = running_routes.pop()
        
        if current_route[-1] == 0 and len(current_route) > 1:
            completed_routes.append(current_route)
        else:
            for next_node in tours2[vehicle][current_route[-1]]:
                extended_route = current_route + [next_node]
                running_routes.append(extended_route)

    routes[vehicle] = completed_routes

最终得到的有效路径存储在routes变量中：

{'V0': [[0, 3, 0]], 'V1': [[0, 8, 0], [0, 3, 2, 0]]}

Yu Hao · Answer

根据您的描述，您希望获得每辆车的欧拉路径（Eulerian path）：

首先，导入所需库并按照以下方式处理数据：

import pandas as pd
import networkx as nx
from itertools import chain, groupby

# 设定起始节点为0
NODE = 0

# 初始化一个空字典用于存储结果
d = {}

# 遍历每辆车及其对应的路线
for vehicle, routes in tours.items():
    # 创建一个有向图G
    G = nx.DiGraph()
    
    # 将路线数据转换为边并添加到图G中
    G.add_edges_from([[int(a), int(b)] for a, b in map(lambda x: x.split(","), routes)])

    # 使用networkx计算欧拉路径，并将路径结果转化为Series对象
    s = pd.Series(chain.from_iterable(nx.eulerian_path(G, source=NODE)))

    # 将连续的、以0结尾的子路径分组，并转换为列表格式
    d[vehicle] = (s.groupby((s.eq(NODE) & s.iloc[1:-1].duplicated()).cumsum())
                    .agg(lambda x: [k for k, _ in groupby(x)]).tolist())

# 输出结果
print(d)  # {'V0': [[0, 3, 0]], 'V1': [[0, 3, 2, 0], [0, 8, 0]]}

# 图形表示：
# （此处显示的是V0和V1车辆的路径图，但实际图形无法在文本环境中展示）

对于可视化部分，若要在生成的网络图中根据节点条件进行着色，您可以这样做：

# 定义节点颜色规则
colors = {
    k: "black" if k == 0
    else "green" if 1 <= k <= 4
    else "red" for k in range(10)
}

# 在外层循环（遍历每辆车时）内部添加以下代码
for node in G.nodes:
    # 设置节点样式为填充且指定颜色
    G.nodes[node]['style'] = "filled"
    G.nodes[node]['fillcolor'] = colors[node]

    # 若节点为0，设置字体颜色为白色
    if node == 0:
        G.nodes[node]['fontcolor'] = "white"