Поиск компонентов очень большого графика

Question

У меня есть очень большой график, представленный в текстовом файле размером около 1 ТБ с каждым краем следующим образом.

From-node to-node 

Я хотел бы разбить его на его слабосвязанные компоненты. Если бы он был меньше, я мог бы загрузить его в networkx и запустить алгоритмы поиска компонентов. Например, http://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.components.connected.connected_components.html#networkx.algorithms.components.connected.connected_components

Есть ли способ сделать это, не загружая все это в память?

Answer 1

Если даже количество узлов слишком велик, чтобы поместиться в памяти, вы можете разделять и властвовать и использовать внешние виды памяти, чтобы сделать большую часть работы для вас (например, команда sort в комплекте с ОС Windows и Unix можно сортировать файлы намного больше, чем память):

1. Выберите пороговую вершину k.
2. Прочитайте исходный файл и записывать каждый из его краев на один из 3 файлов:
   • Чтобы a, если его максимальная пронумерованных вершина < К
   • Для b, если его минимальная пронумерованных вершина> = к
   • для c иначе (т.е. если она имеет одну вершину < к и одну вершину> = к)
3. Если a достаточно мал, чтобы решить (найти связную ком ponents for) в памяти (с использованием, например,Peter de Rivaz's algorithm), тогда сделайте это, иначе рекурсия решит его. Решение должно быть файлом, строки которого состоят из двух чисел x y и который сортируется по x. Каждый номер x является числом вершин, а y является его представителем - наименьшая пронумерованная вершина в том же компоненте, что и x.
4. Аналогично для b.
5. Сортировка краев в c по их наименьшей нумерованной конечной точке.
6. Пройдите по каждому краю в c, переименовав конечную точку, которая является < k (помните, что должна быть ровно одна такая конечная точка) ее представителю, найденному из решения подзадачи a. Это можно сделать эффективно, используя алгоритм слияния с линейным временем, чтобы слиться с решением подзадачи a. Вызвать полученный файл d.
7. Сортировка краев в d по их наивысшей конечной точке. (Тот факт, что мы уже переименовали конечную точку с наименьшим номером, не делает это небезопасным, так как переименование никогда не может увеличить число вершин.)
8. Пройдите по каждому ребру в d, переименовав конечную точку с> = k в ее представитель, найденный из решения подзадачи b с использованием слияния с линейным временем, как и раньше. Вызвать полученный файл e.
9. Solve e. (Как и в случае с a и b, сделайте это непосредственно в памяти, если это возможно, в противном случае повторите процедуру. Если вам нужно выполнить рекурсию, вам нужно будет найти другой способ разбиения ребер, поскольку все ребра в e уже «оседлают» k. может, например, перенумеровать вершины, используя случайную перестановку вершинных чисел, рекурсивно решить возникающую проблему, а затем переименовать их.) Этот шаг необходим, потому что может быть ребро (1, k), другое ребро (2, k + 1) и третьего ребра (2, k), и это будет означать, что все вершины в компонентах 1, 2, k и k + 1 необходимо объединить в один компонент.
10. Пройдите каждую строку в решении по подзадаче a, обновив представителя для этой вершины, используя решение подзадачи e, если необходимо. Это можно сделать эффективно с помощью линейного слияния. Выпишите новый список представителей (который уже будет отсортирован по количеству вершин из-за того, что мы создали его с a) в файл f.
11. Аналогично для каждой строки в решении для подзадачи b, создавая файл g.
12. Конкатенация f и g для получения окончательного ответа. (Для большей эффективности просто сделайте шаг 11, приложите его результаты непосредственно к f).

Все операции слияния с линейным временем, используемые выше, могут считываться непосредственно из файлов с диска, поскольку они только когда-либо получают доступ к элементам из каждого списка в порядке возрастания (т. Е. Не требуется медленный произвольный доступ).

Answer 2

Если у вас мало узлов (например, несколько сотен миллионов), вы можете вычислить подключенные компоненты с помощью одного прохода через текстовый файл, используя память disjoint set forest.

Эта структура данных хранит только указатель ранга и родителя для каждого узла, поэтому он должен вписываться в память, если у вас мало узлов.

Для большего количества узлов вы можете попробовать ту же идею, но сохранить структуру данных на диске (и, возможно, улучшить с помощью кеша в памяти для хранения часто используемых элементов).

Вот некоторые Python код, который реализует простую версию в памяти непересекающихся набора лесов:

N=7 # Number of nodes 
rank=[0]*N 
parent=range(N) 

def Find(x): 
    """Find representative of connected component""" 
    if parent[x] != x: 
     parent[x] = Find(parent[x]) 
    return parent[x] 

def Union(x,y): 
    """Merge sets containing elements x and y""" 
    x = Find(x) 
    y = Find(y) 
    if x == y: 
     return 
    if rank[x]<rank[y]: 
     parent[x] = y 
    elif rank[x]>rank[y]: 
     parent[y] = x 
    else: 
     parent[y] = x 
     rank[x] += 1 

with open("disjointset.txt","r") as fd: 
    for line in fd: 
     fr,to = map(int,line.split()) 
     Union(fr,to) 

for n in range(N): 
    print n,'is in component',Find(n) 

Если применить его к текстовый файл под названием disjointset.txt, содержащий:

1 2 
3 4 
4 5 
0 5 

он печатает

0 is in component 3 
1 is in component 1 
2 is in component 1 
3 is in component 3 
4 is in component 3 
5 is in component 3 
6 is in component 6 

Вы можете сохранить память, не используя массив рангов, на стоимость потенциально увеличенного времени вычислений.

Answer 3

Обход диаграммы внешней памяти является сложным, чтобы получить производительность. Я советую не писать собственный код, детали реализации делают разницу между временем выполнения нескольких часов и временем выполнения нескольких месяцев. Вы должны рассмотреть возможность использования существующих библиотек, таких как stxxl. См. here для бумаги, использующей его для вычисления подключенных компонентов.