The list of tuples is the output from a capacitated vehicle-routing optimization and represents the arcs from one stop to another, where 0 represents the depot of the vehicle (start and end point of vehicle). As the vehicle must drive several laps it may return to the depot before all stops were made. The solver will always return the starting-arcs first, which in the example below means that the first consecutive tuples starting with 0, namely (0, 3), (0, 7), (0, 8) will determine how many laps (= 3) there are.
How can I sort the arcs in consecutive order so that one vehicle could drive the arcs one after another?
Input:
li = [(0, 3), (0, 7), (0, 8), (3, 0), (4, 0), (7, 3), (8, 4), (3, 0)]
Output:
[(0, 3), (3, 0), (0, 7), (7, 3), (3, 0), (0, 8), (8, 4), (4, 0)]
What I tried so far:
laps = 0
for arc in li:
if arc[0] == 0:
laps = laps + 1
new_list = []
for i in range(laps):
value = li.pop(0)
new_list.append([value])
for i in range(laps):
while new_list[i][-1][1] != 0:
arc_end = new_list[i][-1][1]
for j in range(len(li)):
if li[j][0] == arc_end:
value = li.pop(j)
new_list[i].append(value)
break
flat_list = [item for sublist in new_list for item in sublist]
return flat_list
