Алгоритм поиска набора соединений

Question

У меня есть тысячи строк от 1 до 100 чисел, каждая строка определяет группу чисел и отношения между ними. Мне нужно получить наборы связанных чисел.

Маленький пример: Если у меня есть это 7 строк данных

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

мне нужен не так медленно алгоритм, чтобы знать, что множества здесь:

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) 

, но когда у вас есть очень большие наборы очень медленны, чтобы делать поиск T (x) в каждом большом наборе и делать объединения множеств ... и т.д.

У вас есть намек на это не так грубому человеку нер?

Я пытаюсь сделать это в Python.

Answer 1

После того, как вы построили структуру данных, точно, какие запросы вы хотите запустить против него? Покажите нам свой существующий код. Что такое T (x)? Вы говорите о «группах чисел», но ваши данные показывают T1, T2 и т. Д .; пожалуйста, объясни.

Вы читали это: http://en.wikipedia.org/wiki/Disjoint-set_data_structure

Попробуйте посмотреть на этой реализации Python: http://code.activestate.com/recipes/215912-union-find-data-structure/

ИЛИ вы можете наброситься на что-то довольно просто и понятно себя, например,

[Update: совершенно новый код]

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) 

и вот выход из последнего шага:

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

Рассматривайте свои числа T1, T2 и т. Д. Как вершины графа. Любые два числа, появляющиеся вместе на линии, соединяются ребром. Тогда ваша проблема сводится к нахождению всего connected components на этом графике. Вы можете сделать это, начав с T1, затем выполнив поиск по ширине или глубине, чтобы найти все вершины, доступные из этой точки. Отметьте все эти вершины как принадлежащие классу эквивалентности T1. Затем найдите следующую немаркированную вершину Ti, найдите все еще немаркированные узлы, доступные оттуда, и назовите их как принадлежащие классу эквивалентности Ti. Продолжайте, пока не будут отмечены все вершины.

Для графика с n вершинами и e ребрами для этого алгоритма требуется O (e) время и пространство для создания списков смежности и O (n) время и пространство для идентификации всех подключенных компонентов после того, как структура графика будет встроенный.

Answer 3

Для достижения этой цели вы можете использовать структуру данных поиска соединения.

Псевдо код такого алгоритма заключается в следующем:

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 

(из http://www.algorithmist.com/index.php/Union_Find)

Answer 4

Вы можете моделировать группу с помощью set. В приведенном ниже примере я поместил набор в класс Group, чтобы упростить ссылки на них и отслеживать некоторые условные элементы «head».

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 

Выход:

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

Answer 5

Как Jim указывалось выше, вы в основном ищете connected components из простой неориентированный граф, где узлы являются вашими сущностями (T1, T2 и т. д.), а ребра представляют собой попарные отношения между ними. Простая реализация для поиска связанных компонентов основана на первом поиске: вы запускаете BFS из первого объекта, находите все связанные объекты, затем запускаете другую BFS из первой, но необоснованной сущности, и так далее, пока не найдете их все. Простая реализация BFS выглядит следующим образом:

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) 

Здесь adj_list или это структура данных, список смежности, в основном это дает вам сосед данной вершины в графе. Для того, чтобы построить его из файла, вы можете сделать это:

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) 

Затем вы можете запустить:

components = list(connected_components(adj_list)) 

Конечно, реализуя весь алгоритм в чистом Python, как правило, медленнее, чем реализация в C с более эффективной структурой данных графа. Возможно, вы захотите использовать igraph или какую-либо другую графическую библиотеку, например NetworkX. Обе библиотеки содержат реализации для поиска подключенных компонентов; в igraph, она сводится к следующему (при условии, что файл не содержит строки с отдельными записями, только попарные заявки принимаются):

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

Отказ от ответственности: Я один из авторов igraph