Dictionary where values can be either a list or a list of lists

Question

I am trying to plot the result of truck routing optimization using networkx library. First I must prepare the data and I am stuck.

Here is small example of the initial data:

Vehicle       Route  
0       V0   [0,3](V0) 
1       V0   [3,0](V0)  
2       V1   [0,3](V1) 
3       V1   [0,8](V1) 
4       V1   [2,0](V1) 
5       V1   [3,2](V1) 
6       V1   [8,0](V1) 

There are two trucks: V0 and V1. The route for V0 is: 0 to 3 to 0. But V1 has TWO routes: 0 to 8 to 0 AND 0 to 3 to 2 to 0.

Every tour must start and end at node 0.

I must solve two issues:

1. For each truck (V0, V1) I must find all the tours within a given list that starts and end with zero
2. The flow of tours can not have breaks: the end of each sub-tour [0,8] must be the beginning of the next one [8,0]

the final result must look:

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

I have a code but it does not produce what I want:

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(',')))

# Function to process each value in the 'tours' dictionary
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

# Create the 'tours1' dictionary using the processing functions
tours1 = {key: process_value(value) for key, value in tours.items()}

# Print the result
print(tours1)

OUTPUT:

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

Any ideas?

Thank you!

Answer 1

IIUC, you want the Eulerian path of each vehicle :

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

NODE = 0

d = {}

for vehicle, routes in tours.items():
    G = nx.DiGraph()
    G.add_edges_from([[*map(int, x.split(","))] for x in routes])

    s = pd.Series(chain.from_iterable(nx.eulerian_path(G, source=NODE)))
       
    d[vehicle] = (s.groupby((s.eq(NODE) & s.iloc[1:-1].duplicated()).cumsum())
                    .agg(lambda x: [k for k, _ in groupby(x)]).tolist())

Output :

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

Tours of both vehicles :

Update (requested in the comments) :

To conditionally color the nodes, you can use :

colors = {
    k: "black" if k == 0
    else "green" if 1 <= k <= 4
    else "red" for k in range(10)
}

# to put inside the outer loop
for node in G.nodes:
    G.nodes[node]["style"] = "filled"
    G.nodes[node]["fillcolor"] = colors[node]
    if node == 0:
        G.nodes[node]["fontcolor"] = "white"