-3

I have a routes list like this:

routes= 
[[(0, 1), (1, 6), (6, 7), (7, 10), (10, 9), (9, 0)],
 [(0, 2), (2, 3), (3, 4), (4, 5), (5, 0)],
 [(0, 8), (8, 0)]]

Route 1 is from 0 to 1 to 6 to 7 and so on .... how can i transform this list into a list like this:

routes_new= [[0, 1, 6, 7, 10, 9, 0], [0, 2, 3, 4, 5, 0],[0,8,0]]

Thanks a lot!

iviuffek
  • 9
  • 1

3 Answers3

1

Assuming you are looking for cycles here, which seems to be the case, a simple way to achieve what you want is using NetworkX's nx.simple_cycles. This does not require for the edges to be ordered.

import networkx as nx

routes= [[(0, 1), (1, 6), (6, 7), (7, 10), (10, 9), (9, 0)],
 [(0, 2), (2, 3), (3, 4), (4, 5), (5, 0)],
 [(0, 8), (8, 0)]]

paths = []
for route in routes:
    G = nx.from_edgelist(route, create_using=nx.DiGraph)
    paths.append(list(nx.simple_cycles(G)))

paths
# [[[0, 1, 6, 7, 10, 9]], [[0, 2, 3, 4, 5]], [[0, 8]]]

If there can be multiple cycles in each route, check other functions in the cycle module, like nx.find_cycle, which allow you to specify an origin.

yatu
  • 86,083
  • 12
  • 84
  • 139
  • 1
    I started to write a networkx solution and got caught IRL, would have been something similar (I suspect however that it might be overkill) ;) +1 – mozway Aug 24 '22 at 13:08
  • In my experience networkx is handy at simplifying solutions. When a problem translates to a graph equivalent, there's probably a simple solution :) In most cases at least – yatu Aug 24 '22 at 13:09
  • Btw, you can directly use `nx.from_edgelist(route, create_using=nx.DiGraph)`. Enables a list comprehension: `[next(nx.simple_cycles(nx.from_edgelist(r, create_using=nx.DiGraph)), []) for r in routes]` ;) – mozway Aug 24 '22 at 13:10
  • True! let's add that then @mozway – yatu Aug 24 '22 at 13:11
  • I can't see any value added to the answer by including that one liner. If anything it makes it less readable. Leaving it as it was @mozway – yatu Aug 24 '22 at 13:23
  • as you want (I thought you wanted me to add it, I realize my comment edit might have crossed your response). For a personal point of view however I find such lists comprehensions usually more readable than `append` in a loop. Btw, note that your output if different from OP's provided one. – mozway Aug 24 '22 at 13:26
  • Not sure I agree with the extensive list comprehension readability vs multiple lines. For a simple case I would agree. The cycles don't include the origin in the end, yes. I imagine OP might find that simple enough if it is required @mozway – yatu Aug 24 '22 at 13:28
0

A simple list comprehension can help you flatten your lists:

routes_new = [[t[0] for t in l]+[l[-1][1]] for l in routes]

NB. this is assuming the edges are in order and linked. No check is performed. If this is not the case, please provide such an example.

output:

[[0, 1, 6, 7, 10, 9, 0], [0, 2, 3, 4, 5, 0], [0, 8, 0]]
mozway
  • 194,879
  • 13
  • 39
  • 75
0

You can just take the first number of each tuple and add the very last one for each route :

routes_new = [[val[0] for val in route] + [route[-1][-1]] for route in routes]
Arnaud
  • 106
  • 2