如何分类具有交叉值列表的对象列表

Question

我有一个对象列表

main_streets = [street1, street2, street3 ...]

每条街道都有一个有序的节点列表

street.nodes = [nd1, nd2, nd3]

在现实生活中，所有街道是相互连接的（也就是说，它们有共同的起点和终点），但是main_streets这个列表并没有反映这种情况。

我该如何对main_streets进行排序呢？谢谢！

Answer 1

如果这些街道形成了一条连续的链条，那么你可以按照以下步骤来排列它们。首先，找出所有相连街道的配对：

>>> pairs = [(a, b) for a in main_streets for b in main_streets if a.nodes[-1] == b.nodes[0]]

接下来，确定哪条街道是第一条：

>>> seconds = [pair[1] for pair in pairs]
>>> ordered = [s for s in main_streets if s not in seconds]
>>> if len(ordered) > 1:
>>>     raise Exception("Error: There is not one continuous chain.")

然后，开始构建这条街道链。

>>> unordered = [s for s in main_streets if s not in ordered]
>>> for i in range(len(unordered)):
>>>     for (j, s) in enumerate(unordered):
>>>         if s.nodes[0] == ordered[-1].nodes[-1]:
>>>             ordered.append(unordered.pop(j))
>>>             break

如果链条中有断裂（也就是说，并不是所有街道都是相连的），那么在循环结束后，unordered 里仍然会有一些未处理的项目。如果你确实有多个链段，可以从最初的 ordered 列表开始，然后对每个未处理的项目分别运行上面的最后一部分。