How to rearrange a list of tuples (start node ID, end node ID) to create continuous path in Python?

Question

I have a list of tuples with the start and end node ID of a segment. I want to rearrange the tuples (segments) in a way that constructs a continuous path. There can be a loop in the path i.e., one node can be traversed multiple times. I do know the origin and destination of the entire path. There may be some segments that cannot be included in the path as their start or end node cannot be connected to the previous or next node to form that continuous path. These segments should be removed from the rearranged list of tuples.

Example:

The list of tuples may look like the following. Also, I know that the path should start at 101 and end at 205.

[(101, 203), (104, 202), (203, 104), (104, 208), (185, 205), (202, 185)]

Expected Results:

[(101, 203), (203, 104), (104, 202), (202, 185), (185, 205)]

I would like to solve this in Python. My understanding is that this can be solved using a loop that looks at the end node ID of each segment, finds a segment with a similar start node ID, and adds that append that segment to the list of rearranged tuples. I am not quite sure how it can be solved efficiently. So, any hints or example codes would really help.

score 1 · Answer 1 · answered Dec 30 '21 at 06:56

Using networkx to solve this as a shortest path problem (as suggested in answer by @tangolin):

import networkx as nx

data = [(101, 203), (104, 202), (203, 104), (104, 208), (185, 205), (202, 185)]

G = nx.DiGraph()

G.add_edges_from(data)

path = nx.shortest_path(G, source=101, target=205)
formatted_path = [(i, j) for i, j in zip(path, path[1:])]
print(formatted_path)
# [(101, 203), (203, 104), (104, 202), (202, 185), (185, 205)]

tangolin · Answer 2 · 2021-12-30T07:00:06.603

The main challenge in this question is probably just choosing between tuples with the same starting/ending node, e.g. choosing between whether (104, 202) or (104, 208) should come after (203, 104). You didn't really make it clear of what conditions the resultant path must satisfy so I assume any continuous path is fine.

In such a case, this question can simply be framed as a shortest path question, so you just need to find the shortest path between node 101 and 205, and the weight of each vertice is just 1 if the node tuple exist in the set, else infinity. So for example. the vertice between 203 and 104 is 1 since (203, 104) is in the original list, on the other hand the weight between 203 and 208 is infinity, since the vertice doesn't exist. You can then apply the standard Dijkstra shortest path algorithm to obtain the nodes traversed and therefore the tuples.

Edit

I think I misunderstood what you are trying to do, so I think you are actually trying to include as many nodes as possible for the path created. In such a case, perhaps something like breadth first search would be possible, where you keep track of all possible paths and keep deleting those that have no further possible connections.

score -1 · Answer 3 · answered Dec 30 '21 at 06:51

The data

data = [(101, 203), (104, 202), (203, 104), (104, 208), (185, 205), (202, 185)]

The first thing you want to do, in case your data is not sorted according to the first starting point,

# taken from https://stackoverflow.com/a/3121985/3212945
sorted_data = sorted(data, key=lambda tup: tup[0])

Once your data is sorted, you can separate the initial and final values to compare them,

start = np.array([i[0] for i in test])
stop = np.array([i[1] for i in test])

Use another variable that will be reassigned every time a single comparison is completed. Also, a variable is needed to store the indices where the comparison matches and one to store the order of tuple matching.

_stop, _indices, order = stop[0], [], []

try:
    for i, v in enumerate(data):
        _indices.append(np.where(_stop == start)[0])
        # the reason to get last value is because
        # we are appending values, so the latest value
        # will be the last one
        _stop = stop[min(_indices[-1])]
# ValueError because it will return empty array at last comparison
except ValueError:
    for i in _indices:
        if len(i) > 1:
            order.append([i[0]])
        else:
            order.append(i)

order = np.concatenate(order)

Rearranging the tuple

new_data = [data[i] for i in order]

Your code doesn't work if the nodes form a loop. Say `data = [(101, 203), (104, 201), (203, 104), (104, 202), (185, 205), (202, 185)]` — Ming, Dec 30 '21 at 08:40

How to rearrange a list of tuples (start node ID, end node ID) to create continuous path in Python?

3 Answers3

Edit