sequence of number for a list of tuple-CodePudding

I have a list of tuples that I need to convert to a sequence of numbers. For example, the following list contains a list of arcs (node to node). I need to pick only the nodes to create a route in which only the sequential nodes will be present.

arcs= [(1,13), (16,12), (13,16), (12,17)]

route= [1,13,16,12,17]

would appreciate it if anyone could point me in the right direction.

CodePudding user response：

To solve the problem in linear time complexity, you can create a dict that maps each node to the next. Start the route from the node that no other node leads to by taking a set difference between the starting nodes and the destination nodes. Keep appending to the route the next node according to the mapping until the current node no longer has a destination in the mapping:

mapping = dict(arcs)
route = [set.difference(*map(set, zip(*arcs))).pop()]
while route[-1] in mapping:
    route.append(mapping[route[-1]])

Given your input arcs, route would become:

[1, 13, 16, 12, 17]

Demo: https://replit.com/@blhsing/AgedEvilVisitor

CodePudding user response：

You can use networkx:

# pip install networkx
import networkx as nx

G = nx.from_edgelist(arcs)
routes = list(nx.all_simple_paths(G, arcs[0][0], arcs[-1][1]))
print(routes)

Output:
[[1, 13, 16, 12, 17]]

CodePudding user response：

Hope this helps,

arcs= [(1,13), (16,12), (13,16), (12,17)]
route=[]
for x in arcs:
    for y in x:
        if y not in route:
            route.append(y)
print (route)

Output:

[1, 13, 16, 12, 17]

PS: If this is not the expected output please modify your question with code.

CodePudding user response：

just do a simple iteration over iteration

for that you can have a code like this

arcs = [(1,13), (16,12), (13,16), (12,17)]

route = []

    
for i in arcs:
  for j in i:
    if j not in route:
        rout.append(j)