将包含未排序内容的元组快速排序为链

Question

我想对元组列表[(0，9(，(5，4(，(2，9(、(7，4(、(7,2(]进行排序，以得到[(0、9(。

更具体地说，我有一组要连接到链(多段线(中的边(线段(。边的顺序是随机的，我想对它们进行排序。每条边都有两个节点，即起点和终点，它们在最终链中的方向可能匹配，也可能不匹配。下面的代码可以工作，但速度非常慢，尤其是我不得不多次调用这个函数。在我的例子中，节点是自定义Node类的实例，而不是整数。平均而言，可能有大约10个边缘需要连接。我必须在Ironpython中运行它。我可以问一下是否有一个好的方法来提高速度吗？非常感谢！

Chris

from collections import Counter
class Edge():
def __init__(self,nodeA,nodeB,edges):
self.nodes = (nodeA,nodeB)
self.index = len(edges)
edges.append(self)
def chainEdges(edges):
# make chains of edges along their connections
nodesFlat = [node for edge in edges for node in edge.nodes]
if any(Counter(nodesFlat)[node]>2 for node in nodesFlat): return# the edges connect in a non-linear manner (Y-formation)
# find first edge
elif all(Counter(nodesFlat)[node]==2 for node in nodesFlat):# the edges connect in a loop
chain = [min(edges, key=lambda edge: edge.index)]# first edge in the loop is the one with the lowest index
edges.remove(chain[-1])
nodeLast = chain[-1].nodes[-1]
else:# edges form one polyline
chain = [min([edge for edge in edges if any(Counter(nodesFlat)[node]==1 for node in edge.nodes)], key=lambda edge: edge.index)]# first edge is the one with the lowest index
edges.remove(chain[0])
nodeLast = chain[-1].nodes[0] if Counter(nodesFlat)[chain[-1].nodes[0]]==2 else chain[-1].nodes[1]
# loop through remaining edges
while len(edges)>0:
for edge in edges:
if nodeLast in edge.nodes:
chain.append(edge)
edges.remove(edge)
nodeLast = edge.nodes[0] if nodeLast==edge.nodes[1] else edge.nodes[1]
break
return chain
edges = []
for [nodeA,nodeB] in [(0, 9), (5, 4), (2, 9), (7, 4), (7, 2)]:
Edge(nodeA,nodeB,edges) 
print [edge.nodes for edge in chainEdges(edges)]
>>>[(0, 9), (2, 9), (7, 2), (7, 4), (5, 4)]

Answer 1

我发现了问题，慢的部分是当一个节点上有两条以上的边连接时，我如何检查Y形。当我运行该方法时，我已经检查了所有的边是否以某种方式连接，但我不知道它们是形成一条线、一个圆还是一个Y。下面的速度要快得多：

def chainEdges(edges):
# make chains of edges along their connections
chain = [min(edges, key=lambda edge: edge.index)]
edges.remove(chain[-1])
nodesSorted = list(chain[-1].nodes)
while len(edges)>0:
for edge in edges[:]:
if nodesSorted[0] in edge.nodes:
chain.insert(0,edge)
edges.remove(edge)
nodesSorted.insert(0,edge.nodes[0] if nodesSorted[0]==edge.nodes[1] else edge.nodes[1])
if nodesSorted[0] in nodesSorted[1:-1] or (nodesSorted[0]==nodesSorted[-1] and len(edges)>0): chain = [False]# the edges connect in a non-linear manner (Y-formation)
break
elif nodesSorted[-1] in edge.nodes:
chain.append(edge)
edges.remove(edge)
nodesSorted.append(edge.nodes[0] if nodesSorted[-1]==edge.nodes[1] else edge.nodes[1])
if nodesSorted[-1] in nodesSorted[1:-1]: chain = [False]# the edges connect in a non-linear manner (Y-formation)
break
else: chain = [False]# the edges connect in a non-linear manner (Y-formation)
if chain == [False]: break
return chain