Различные результаты при перетасовке списка

Question

Я хочу разделить неполный график на отдельные, несвязанные тела. Ребра графа находятся в списке edges.

Код дает другой результат при перетасовке порядка краев. Почему это?

from random import shuffle 

edges = [('7', '9'), ('2', '8'), ('4', '10'), ('5', '9'), ('1', '2'), ('1', '6'), ('6', '10')] 
bodylist = [] 
shuffle(edges) 

for edge in edges: 
    #If at least one node of the edge is anywhere in bodylist, append the new nodes to that list. 
    try: 
     index = [i for i, body in enumerate(bodylist) if edge[0] in body or edge[1] in body][0] 
     bodylist[index].append(edge[0]) 
     bodylist[index].append(edge[1]) 
    #If not, make a new list containing the new nodes. 
    except: 
     bodylist.append([edge[0], edge[1]]) 

print([set(x) for x in bodylist]) 

Ожидаемый результат: [{'1', '2', '8', '4', '6', '10'}, {'9', '5', '7'}]

Некоторые из реальных выходов: [{'9', '5', '7'}, {'1', '2', '8'}, {'10', '4', '6', '1'}]

[{'9', '7', '5'}, {'6', '2', '1', '8'}, {'6', '10', '4'}]

Обратите внимание, что ожидаемый выход также приходит время от времени. (Это всегда должно быть так)

Я также буду признателен за различные подходы, так как этот, вероятно, не самый лучший.

Answer 1

Предположим, у вас есть три ребра [(1, 2), (3, 4), (2, 3)]. Здесь описывается связанный граф.

Однако, ваш код будет сначала проверен на (1, 2), ничего не найдете, поэтому добавьте это в bodylist.

Тогда он будет искать (3, 4), не найти ни 3, ни 4, поэтому добавьте его в новый список.

Наконец-то он добавит (2, 3) в первый список, но он не вернется, чтобы исправить свою ошибку, он не поймет, что (3, 4) принадлежат к одному корпусу.

Чтобы решить эту проблему, вы можете цикл полностью через остальные ребра каждый раз, когда вы добавляете новый край к телу для того, чтобы проверить, есть ли связь:

while edges: 
    current_edge = edges.pop(0) 
    body = {current_edge[0], current_edge[1]} 
    i = 0 
    while i < len(edges): 
     if edges[i][0] in body or edges[i][1] in body: 
      body.add(edges[i][0]) 
      body.add(edges[i][1]) 
      edges.pop(i) # Edge added, no need to check it again 
      i = 0 # Restart the loop 
     else: 
      i += 1 
    bodylist.append(body) 

Что вы ищете называется connected component графика.

Если вы ищете эффективный алгоритм, вы должны взглянуть на this answer.

Answer 2

Это потому, что ваш алгоритм неверен. Проблема с вашим алгоритмом заключается в том, что он зависит от того, к каким краям мы начинаем создавать список тел. Чтобы объяснить это, возьмем простой пример графика с 4 ребрами как - edges = [('1','2'),('2','3'),('3','4'),('1','4')].

Первый случай -

>>> edges = [('1','2'),('2','3'),('3','4'),('1','4')] 
>>> bodylist = [] 
>>> for edge in edges: 
...  #If at least one node of the edge is anywhere in bodylist, append the new nodes to that list. 
...  try: 
...   index = [i for i, body in enumerate(bodylist) if edge[0] in body or edge[1] in body][0] 
...   bodylist[index].append(edge[0]) 
...   bodylist[index].append(edge[1]) 
...  #If not, make a new list containing the new nodes. 
...  except: 
...   bodylist.append([edge[0], edge[1]]) 
... 
>>> print([set(x) for x in bodylist]) 
[{'4', '1', '3', '2'}] 

Вы получаете одно тело с вершинами - 1, 2, 3, 4. Зачем?

Беспокойство, начатое с (1,2), добавлено в список объектов. Затем вы взяли (2,3), вы видите, что 2 уже есть в элементе, добавленном в список объектов, вы добавляете его снова к тому же, и это продолжается, и все они добавляются в один и тот же объект.

Теперь давайте берем те же края в другом порядке - edges = [('1','2'),('3','4'),('2','3'),('1','4')]. Это получается как -

>>> edges = [('1','2'),('3','4'),('2','3'),('1','4')] 
>>> bodylist = [] 
>>> .... #same logic 
>>> print([set(x) for x in bodylist]) 
[{'4', '1', '3', '2'}, {'4', '3'}] 

Как вы можете видеть, на этот раз, у вас есть два различных тела (и, очевидно, что они не правы) Почему?

Снова вы начали с (1,2), добавили, что для бодилера как тела, тогда вы взяли (3,4), проверяя это, вы видите, что ни одна из вершин уже не существует в любом теле, следовательно вы добавили это в отдельный орган. Принимая третий элемент (2,3), вы видите, что это есть как в первом, так и во втором теле, но ваша логика состоит в том, чтобы просто взять первое тело и добавить к нему элемент. (Вы видите, где вы собираетесь не так?)

---

Вот почему вы получите разные результаты, когда вы перетасовать список, так как порядок имеет важное значение для вашей логики (что неправильно).

Что вам нужно сделать, так это то, что если вы найдете вершины для края в нескольких телах, вам нужно объединить оба тела в единое тело.

---

Другой совет, нам не нужно, чтобы добавить списки в bodylist вместо этого мы можем использовать sets для каждого body.

Образец решение будет выглядеть -

from random import shuffle 

edges = [('7', '9'), ('2', '8'), ('4', '10'), ('5', '9'), ('1', '2'), ('1', '6'), ('6', '10')] 
bodylist = [] 
shuffle(edges) 

for edge in edges: 
    bodies = [body for i, body in enumerate(bodylist) if edge[0] in body or edge[1] in body] 
    if len(bodies) > 0: 
     tempset = {edge[0],edge[1]} 
     for x in bodies: 
      tempset.update(x) 
      print('tempset :',tempset) 
      bodylist.remove(x) 
     bodylist.append(tempset) 
    else: 
     bodylist.append({edge[0],edge[1]}) 

print([set(x) for x in bodylist])