Dividir una tupla de tuplas (o lista de listas) de valores emparejados en conjuntos completos independientes?

Question

Tengo valores emparejados en un archivo csv. Ninguno de los valores emparejados es necesariamente único. Me gustaría dividir esta gran lista en conjuntos completos independientes para su posterior análisis.

Para ilustrar, mi "megalist" es como:

megalist = [['a', 'b'], ['a', 'd'], ['b', 'd'],['b', 'f'], ['r', 's'], ['t', 'r']...] 

que es más importante, la salida sería preservar la lista de parejas de valores (es decir, no consolidar los valores). Idealmente, la salida eventualmente resultaría en diferentes archivos csv para análisis individual más adelante. Por ejemplo, este sería megalist:

completeset1 = [['a', 'b'], ['a', 'd'], ['b', 'd'], ['b', 'f']] 
completeset2 = [['r', 's'], ['t', 'r']] 
... 

En un contexto teoría de grafos, estoy tratando de tomar una gráfica gigante de subgrafos mutuamente excluyentes (donde los valores emparejados se vértices conectados) y dividirlas en gráficos independientes que son más manejables Gracias por cualquier entrada!

Editar 1: Esto me puso en un lugar desde el cual puedo avanzar. ¡Gracias de nuevo!

import sys, csv 
import networkx as nx 

megalist = csv.reader(open('megalistfile.csv'), delimiter = '\t') 

G = nx.Graph() 
G.add_edges_from(megalist) 

subgraphs = nx.connected_components(G) 

output_file = open('subgraphs.txt','w') 

for subgraph in subgraphs: 
    output_line = str(G.edges(subgraph)) + '\n' 
    output_file.write(output_line) 

output_file.close() 

Answer 1

Puede usar networkx para esto. La construcción de la gráfica:

>>> import networkx as nx 
>>> megalist = [['a', 'b'], ['a', 'd'], ['b', 'd'],['b', 'f'], ['r', 's'], ['t', 'r']] 
>>> G = nx.Graph() 
>>> G.add_edges_from(megalist) 

continuación para obtener la lista de subgrahs:

>>> subgraphs = nx.connected_components(G) 
>>> subgraphs 
[['a', 'b', 'd', 'f'], ['s', 'r', 't']] 
>>> [G.edges(subgraph) for subgraph in subgraphs] 
[[('a', 'b'), ('a', 'd'), ('b', 'd'), ('b', 'f')], [('s', 'r'), ('r', 't')]] 

Answer 2

Se podría definir manualmente sus sublistas usando rebanar:

completeset1=megalist[0:4] 
completeset2=megalist[4:] 

Sin embargo, lo que realmente suena como desea aplicar un poco de lógica más profunda, o el uso de datos adicionales, para crear estos segmentos de forma automática de acuerdo a alguna condición. es difícil aconsejar sin saber más sobre la lógica que le gustaría aplicar.

Editar: los comentarios a la pregunta pueden ser buenos punteros.

Answer 3

algo muy simple, con Contador http://docs.python.org/library/collections.html#collections.Counter

from collections import Counter 

megalist = [['a', 'b'], ['a', 'd'], ['b', 'd'],['b', 'f'], ['r', 's'], ['t', 'r']] 

result = [] 
for l in megalist: 
    cl = Counter(l) 
    if not result: 
     result.append([l]) 
    else: 
     add = False 
     for result_item in result: 
      add = bool(filter(lambda e: bool(cl & Counter(e)) , result_item)) 

      if add and l not in result_item: 
       result_item.append(l) 
       break      

     if not add: 
      result.append([l]) 


print result 

[[['a', 'b'], ['a', 'd'], ['b', 'd'], ['b', 'f']], [['r', 's'], ['t', 'r']]]