Как я могу заказать список соединений

Question

В настоящее время у меня есть список соединений, хранящихся в списке, где каждое соединение представляет собой направленную ссылку, которая соединяет две точки, и ни одна точка никогда не связывается с более чем одной точкой или связана более чем с одной точкой. Например:

connections = [ (3, 7), (6, 5), (4, 6), (5, 3), (7, 8), (1, 2), (2, 1) ]

Должен производить:

ordered = [ [ 4, 6, 5, 3, 7, 8 ], [ 1, 2, 1 ] ]

Я пытаюсь сделать это, используя алгоритм, который берет точку ввода и список соединений и рекурсивно вызывает себя, чтобы найти следующую точку и добавить ее в растущий упорядоченный список. Тем не менее, мой алгоритм выходит из строя, когда я не начинаю с правильной точки (хотя это просто вопрос повторения того же алгоритма в обратном порядке), но также и при наличии нескольких не связанных нитей

Как лучше написать эффективный алгоритм для упорядочения этих соединений?

Answer 1

Алгоритм решения

Вы ищете топологический алгоритм сортировки:

from collections import defaultdict

def topological_sort(dependency_pairs):
    'Sort values subject to dependency constraints'
    num_heads = defaultdict(int)   # num arrows pointing in
    tails = defaultdict(list)      # list of arrows going out
    for h, t in dependency_pairs:
        num_heads[t] += 1
        tails[h].append(t)

    ordered = [h for h in tails if h not in num_heads]
    for h in ordered:
        for t in tails[h]:
            num_heads[t] -= 1
            if not num_heads[t]:
                ordered.append(t)
    cyclic = [n for n, heads in num_heads.iteritems() if heads]
    return ordered, cyclic

if __name__ == '__main__':
    connections = [(3, 7), (6, 5), (4, 6), (5, 3), (7, 8), (1, 2), (2, 1)]
    print topological_sort(connections)

Вот вывод для ваших образцов данных:

([4, 6, 5, 3, 7, 8], [1, 2])

Время выполнения линейно пропорционально количеству ребер (пар зависимостей).

КАК ЭТО УСТРОЕНО

Алгоритм организован вокруг таблицы поиска под названием num_heads, которая ведет подсчет количества предшественников (входящих стрелок). Рассмотрим пример со следующими подключениями: a->h b->g c->f c->h d->i e->d f->b f->g h->d h->e i->b, количество:

node  number of incoming edges
----  ------------------------
 a       0
 b       2
 c       0
 d       2
 e       1
 f       1  
 g       2
 h       2
 i       1

Алгоритм работает путем "посещения" узлов без предшественников. Например, узлы a а также c не имеют входящих ребер, поэтому они посещаются первыми.

Посещение означает, что узлы выводятся и удаляются из графика. Когда узел посещается, мы зацикливаемся на его преемниках и уменьшаем их входящий счетчик на единицу.

Например, в гостевом узле a Идем к его преемнику h уменьшить его входящий счетчик на единицу (так, чтобы h 2 становится h 1,

Аналогично, при посещении узла c Зациклились на его преемниках f а также h, уменьшая их количество на один (так что f 1 становится f 0 а также h 1 становится h 0).

Узлы f а также h у нас больше нет входящих ребер, поэтому мы повторяем процесс их вывода и удаления из графика, пока все узлы не будут посещены. В примере порядок посещения (топологический вид):

a c f h e d i b g

Если num_heads когда-либо приходит в состояние, когда нет узлов без входящих ребер, это означает, что существует цикл, который не может быть топологически отсортирован, и алгоритм завершает работу, чтобы показать запрошенные результаты.

Answer 2

Что-то вроде этого:

from collections import defaultdict
lis = [ (3, 7), (6, 5), (4, 6), (5, 3), (7, 8), (1, 2), (2, 1) ]
dic = defaultdict(list)

for k,v in lis:
    if v not in dic:
        dic[k].append(v)
    else:
        dic[k].extend([v]+dic[v])
        del dic[v]

for k,v in dic.items():
    for x in v:
        if x in dic and x!=k:
            dic[k].extend(dic[x])
            del dic[x]

print dic
print [[k]+v for k,v in dic.items()]

выход:

defaultdict(<type 'list'>, {2: [1, 2], 4: [6, 5, 3, 7, 8]})
[[2, 1, 2], [4, 6, 5, 3, 7, 8]]

Answer 3

Я думаю, что вы можете сделать это в O(n) с чем-то вроде этого:

ordered = {}

for each connection (s,t):
  if t exists in ordered :
     ordered[s] = [t] + ordered[t]
     del ordered[t]
  else:
     ordered[s] = [t]

# Now merge...
for each ordered (s : [t1, t2, ... tN]):
  ordered[s] = [t1, t2, ... tN] + ordered[tN]
  del ordered[tN]

В конце у вас останется что-то вроде этого, но вы можете легко это преобразовать

ordered = { 
  4 : [6, 5, 3, 7, 8],
  2 : [1, 2]
}