Быстрая сортировка кортежей с несортированным содержимым в цепочки

Question

Я хочу отсортировать список кортежей [(0, 9), (5, 4), (2, 9), (7, 4), (7, 2)], чтобы получить [(0, 9 ), (2, 9), (7, 2), (7, 4), (5, 4)].

В частности, у меня есть набор ребер (сегментов линии), которые я хочу соединить в цепочки (полилинии). Порядок краев случайный, и я хочу их отсортировать. Каждое ребро имеет два узла, начальную и конечную точки, которые могут совпадать, а могут и не совпадать со своим направлением в конечной цепочке. Приведенный ниже код работает, но он очень медленный, тем более, что мне приходится вызывать эту функцию много раз. В моем случае узлы являются экземплярами пользовательского класса узла, а не целыми числами. В среднем можно соединить около 10 ребер. Приходится запускать в Iron python. Могу я спросить, есть ли хороший способ увеличить скорость этого? Спасибо большое!

Крис

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-образные формы, когда более 2 ребер соединяются в одном узле. Когда я запускаю метод, я уже проверил, все ли края каким-то образом связаны, но я не знаю, образуют ли они линию, круг или 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