python - 如何对具有相交值列表的对象列表进行分类

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列表开始，然后分别为每个项目运行上面的最后一部分。