Risultato diverso dopo aver mischiato un elenco

Question

Voglio dividere un grafico incompleto in corpi separati e non connessi. I bordi del grafico si trovano nell'elenco edges.

Il codice restituisce un risultato diverso dopo aver mischiato l'ordine dei bordi. Perché?

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]) 

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

Alcune delle uscite effettive: [{'9', '5', '7'}, {'1', '2', '8'}, {'10', '4', '6', '1'}]

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

Si noti che l'output previsto inoltre viene di volta in volta. (Dovrebbe essere sempre così)

Apprezzerò anche diversi approcci, poiché questo probabilmente non è il migliore.

Answer 1

Si supponga di avere i tre spigoli [(1, 2), (3, 4), (2, 3)]. Descrive un grafico connesso.

Tuttavia, il codice controlla prima il numero (1, 2), non trova nulla, quindi aggiungilo allo bodylist.

Quindi, cercherà (3, 4), non trovare né 3 o 4 quindi aggiungerlo come un nuovo elenco.

Infine aggiungerà (2, 3) alla prima lista ma non tornerà per correggere l'errore, non realizzerà che lo (3, 4) appartiene allo stesso corpo.

Per risolvere questo problema, è possibile ciclo interamente attraverso i bordi rimanenti ogni volta che si aggiunge un nuovo bordo di un corpo al fine di verificare se v'è un collegamento:

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) 

Quello che state cercando si chiama connected component di un grafico.

Se si sta cercando un algoritmo efficiente, è necessario dare un'occhiata a this answer.

Answer 2

Questo perché il tuo algoritmo è sbagliato. Il problema con il tuo algoritmo è che dipende dai bordi con cui iniziamo a creare la lista dei corpi. Per spiegare questo, prendi un semplice esempio di un grafico con 4 spigoli come - edges = [('1','2'),('2','3'),('3','4'),('1','4')].

Primo caso -

>>> 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'}] 

si ottiene un corpo unico con i vertici - 1, 2, 3, 4. Perché?

Se si inizia con (1,2) aggiunto all'elenco dei corpi. Poi hai preso (2,3), vedi che 2 è già lì nella voce aggiunta nella body list, la aggiungi nuovamente alla stessa e questa continua e tutte sono aggiunte allo stesso corpo.

---

Ora, consente di prendere gli stessi bordi in un altro ordine - edges = [('1','2'),('3','4'),('2','3'),('1','4')]. Questo risulta come -

>>> 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'}] 

Come si può vedere questa volta, hai due corpi diversi (e, ovviamente, hanno torto) Perché?

Ancora una volta hai iniziato con (1,2), l'hai aggiunto al corpo come corpo, poi hai preso (3,4), verificando questo, vedi che nessuno dei vertici è già lì in nessun corpo, quindi hai aggiunto questo a un corpo separato. Prendendo il terzo elemento (2,3), vedi che questo è presente sia nel primo che nel secondo corpo, ma la tua logica è prendere il primo corpo e aggiungere l'elemento. (Vuoi vedere dove si sta andando male?)

---

Questo è il motivo per cui si ottengono risultati diversi quando si rimescola la lista, come l'ordine è importante per la vostra logica (che è sbagliato).

Quello che devi fare è che, se trovi i vertici per un bordo in più corpi, devi unire entrambi i corpi in un unico corpo.

---

Un altro consiglio, non abbiamo bisogno di aggiungere liste in bodylist invece possiamo utilizzare sets per ogni body.

Una soluzione del campione sarebbe simile -

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])