Un conjunto algoritmo de búsqueda de unión

Question

Tengo miles de líneas de 1 a 100 números, cada línea define un grupo de números y una relación entre ellos. Necesito obtener los conjuntos de números relacionados.

pequeño ejemplo: Si tengo esto 7 líneas de datos

T1 T2 
T3 
T4 
T5 
T6 T1 
T5 T4 
T3 T4 T7 

necesito un algoritmo no tan lento que saber que los juegos aquí son:

T1 T2 T6 (because T1 is related with T2 in the first line and T1 related with T6 in the line 5) 
T3 T4 T5 T7 (because T5 is with T4 in line 6 and T3 is with T4 and T7 in line 7) 

pero cuando se tiene muy los grandes conjuntos son dolorosamente lentos para hacer una búsqueda de un T (x) en cada conjunto grande, y hacer uniones de conjuntos ... etc.

¿Tiene una pista para hacer esto en un hombre no tan bruta? ner?

Estoy tratando de hacer esto en Python.

Answer 1

vez que haya construido la estructura de datos, exactamente lo que las consultas no se quiere correr en contra de ella? Muéstranos tu código actual. ¿Qué es un T (x)? Usted habla de "grupos de números" pero sus datos de muestra muestran T1, T2, etc. por favor explique.

¿Ha leído esto: http://en.wikipedia.org/wiki/Disjoint-set_data_structure

intentar ver la implementación de Python: http://code.activestate.com/recipes/215912-union-find-data-structure/

O puede atacar a algo bastante simple y comprensible a sí mismo, por ejemplo,

[Actualización: totalmente nuevo código]

class DisjointSet(object): 

    def __init__(self): 
     self.leader = {} # maps a member to the group's leader 
     self.group = {} # maps a group leader to the group (which is a set) 

    def add(self, a, b): 
     leadera = self.leader.get(a) 
     leaderb = self.leader.get(b) 
     if leadera is not None: 
      if leaderb is not None: 
       if leadera == leaderb: return # nothing to do 
       groupa = self.group[leadera] 
       groupb = self.group[leaderb] 
       if len(groupa) < len(groupb): 
        a, leadera, groupa, b, leaderb, groupb = b, leaderb, groupb, a, leadera, groupa 
       groupa |= groupb 
       del self.group[leaderb] 
       for k in groupb: 
        self.leader[k] = leadera 
      else: 
       self.group[leadera].add(b) 
       self.leader[b] = leadera 
     else: 
      if leaderb is not None: 
       self.group[leaderb].add(a) 
       self.leader[a] = leaderb 
      else: 
       self.leader[a] = self.leader[b] = a 
       self.group[a] = set([a, b]) 

data = """T1 T2 
T3 T4 
T5 T1 
T3 T6 
T7 T8 
T3 T7 
T9 TA 
T1 T9""" 
# data is chosen to demonstrate each of 5 paths in the code 
from pprint import pprint as pp 
ds = DisjointSet() 
for line in data.splitlines(): 
    x, y = line.split() 
    ds.add(x, y) 
    print 
    print x, y 
    pp(ds.leader) 
    pp(ds.group) 

y aquí está la salida de la última etapa:

T1 T9 
{'T1': 'T1', 
'T2': 'T1', 
'T3': 'T3', 
'T4': 'T3', 
'T5': 'T1', 
'T6': 'T3', 
'T7': 'T3', 
'T8': 'T3', 
'T9': 'T1', 
'TA': 'T1'} 
{'T1': set(['T1', 'T2', 'T5', 'T9', 'TA']), 
'T3': set(['T3', 'T4', 'T6', 'T7', 'T8'])} 

Answer 2

Trate sus números T1, T2, etc. como vértices del gráfico. Dos números que aparecen juntos en una línea se unen por un borde. Entonces su problema equivale a encontrar todos los connected components en este gráfico. Puede hacer esto comenzando con T1, luego haciendo una búsqueda de amplitud primero o profundidad para encontrar todos los vértices alcanzables desde ese punto. Marque todos estos vértices como pertenecientes a la clase de equivalencia T1. A continuación, busque el siguiente vértice Ti sin marcar, encuentre todos los nodos aún sin marcar a los que se puede acceder desde allí y etiquételos como pertenecientes a la clase de equivalencia Ti. Continúa hasta que todos los vértices estén marcados.

Para un gráfico con n vértices y bordes e, este algoritmo requiere O (e) tiempo y espacio para construir listas de adyacencia, y O (n) tiempo y espacio para identificar todos los componentes conectados una vez que la estructura del gráfico construido.

Answer 3

Puede usar una estructura de unión de búsqueda de datos para lograr este objetivo.

El pseudo código para un algoritmo tal es como sigue:

func find(var element) 
    while (element is not the root) element = element's parent 
    return element 
end func 

func union(var setA, var setB) 
    var rootA = find(setA), rootB = find(setB) 
    if (rootA is equal to rootB) return 
    else 
    set rootB as rootA's parent 
end func 

(Tomado de http://www.algorithmist.com/index.php/Union_Find)

Answer 4

Puede modelar un grupo usando un set. En el siguiente ejemplo, coloqué el conjunto en una clase grupal para que sea más fácil mantener referencias a ellos y rastrear algunas características nocionales de "cabeza".

class Group: 
    def __init__(self,head): 
     self.members = set() 
     self.head = head 
     self.add(head) 
    def add(self,member): 
     self.members.add(member) 
    def union(self,other): 
     self.members = other.members.union(self.members) 

groups = {} 

for line in open("sets.dat"): 
    line = line.split() 
    if len(line) == 0: 
     break 
    # find the group of the first item on the row 
    head = line[0] 
    if head not in groups: 
     group = Group(head) 
     groups[head] = group 
    else: 
     group = groups[head] 
    # for each other item on the row, merge the groups 
    for node in line[1:]: 
     if node not in groups: 
      # its a new node, straight into the group 
      group.add(node) 
      groups[node] = group 
     elif head not in groups[node].members: 
      # merge two groups 
      new_members = groups[node] 
      group.union(new_members) 
      for migrate in new_members.members: 
       groups[migrate] = group 
# list them 
for k,v in groups.iteritems(): 
    if k == v.head: 
     print v.members 

de salida es:

set(['T6', 'T2', 'T1']) 
set(['T4', 'T5', 'T3']) 

Answer 5

Como Jim ha señalado más arriba, que son esencialmente buscando el connected components de un gráfico simple no dirigido donde los nodos son sus entidades (T1, T2 y así sucesivamente), y los bordes representan las relaciones pares entre ellos. Una implementación simple para la búsqueda de componentes conectados se basa en la búsqueda de amplitud: inicia un BFS desde la primera entidad, busca todas las entidades relacionadas, luego inicia otra BFS desde la primera entidad aún no encontrada, y así sucesivamente, hasta que las encuentres todas. Una simple aplicación de BFS se ve así:

class BreadthFirstSearch(object): 
    """Breadth-first search implementation using an adjacency list""" 

    def __init__(self, adj_list): 
     self.adj_list = adj_list 

    def run(self, start_vertex): 
     """Runs a breadth-first search from the given start vertex and 
     yields the visited vertices one by one.""" 
     queue = deque([start_vertex]) 
     visited = set([start_vertex]) 
     adj_list = self.adj_list 

     while queue: 
      vertex = queue.popleft() 
      yield vertex 
      unseen_neis = adj_list[vertex]-visited 
      visited.update(unseen_neis) 
      queue.extend(unseen_neis) 

def connected_components(graph): 
    seen_vertices = set() 
    bfs = BreadthFirstSearch(graph) 
    for start_vertex in graph: 
     if start_vertex in seen_vertices: 
      continue 
     component = list(bfs.run(start_vertex)) 
     yield component 
     seen_vertices.update(component) 

Aquí, adj_list o es una estructura de datos de lista de adyacencia, básicamente le da los vecinos de un vértice dado en el gráfico. Para construirlo desde su archivo, usted puede hacer esto:

adj_list = defaultdict(set) 
for line in open("your_file.txt"): 
    parts = line.strip().split() 
    v1 = parts.pop(0) 
    adj_list[v1].update(parts) 
    for v2 in parts: 
     adj_list[v2].add(v1) 

continuación, puede ejecutar:

components = list(connected_components(adj_list)) 

Por supuesto, la aplicación de todo el algoritmo en Python puro tiende a ser más lento que una implementación en C con una estructura de datos de gráficos más eficiente. Puede considerar usar igraph o alguna otra biblioteca de gráficos como NetworkX para hacer el trabajo. Ambas bibliotecas contienen implementaciones para la búsqueda de componentes conectados; en igraph, se reduce a lo siguiente (suponiendo que el archivo no contiene líneas con entradas individuales, sólo se aceptan entradas por parejas):

>>> from igraph import load 
>>> graph = load("edge_list.txt", format="ncol", directed=False) 
>>> components = graph.clusters() 
>>> print graph.vs[components[0]]["name"] 
['T1', 'T2', 'T6'] 
>>> print graph.vs[components[1]]["name"] 
['T3', 'T4', 'T5'] 

responsabilidad: yo soy uno de los autores de igraph