Алгоритмы ядра с подключенными компонентами

Question

У меня есть 4 000 000 000 (четыре миллиарда) ребер для неориентированного графика. Они представлены в большом текстовом файле в виде пар идентификаторов узлов. Я хотел бы вычислить связанные компоненты этого графа. К сожалению, как только вы загружаете идентификаторы узлов с краями в память, это занимает более 128 ГБ оперативной памяти, доступной мне.

Есть ли встроенный алгоритм для нахождения сильно связанных компонентов, которые относительно просты в реализации? Или, что еще лучше, может ли он быть вымощен вместе с командами Unix и существующими (python) библиотеками?

Answer 1

Вы можете хранить только массив вершин как их «цвет» (значение int), а затем запускать файл без загрузки всего набора ссылок, отмечая вершины цветом, новый, если ни одна вершина не окрашена , тот же цвет, если один цвет, а другой нет, и самый низкий из двух цветов вместе с перекраской всех других вершин массива, которые окрашены с самым высоким цветом, если оба окрашены. Псевдокод пример:

int nextColor=1; 
int merges=0; 
int[] vertices; 
while (!file.eof()) { 
    link=file.readLink(); 
    c1=vertices[link.a]; 
    c2=vertices[link.b]; 
    if ((c1==0)&&(c2==0)) { 
     vertices[link.a]=nextColor; 
     vertices[link.b]=nextColor; 
     nextColor++; 
    } else if ((c1!=0)&&(c2!=0)) { 
     // both colored, merge 
     for (i=vertices.length-1;i>=0;i--) if (vertices[i]==c2) vertices[i]=c1; 
     merges++; 
    } else if (c1==0) vertices[link.a]=c2; // only c1 is 0 
    else vertices[link.b]=c1; // only c2 is 0 
} 

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

UPDATE: поскольку вершины не являются действительно ints, а строками вместо этого, вы должны также иметь карту строки для int при разборе этого файла. Если ваши строки ограничены по длине, вы можете поместить их все в память как хеш-таблицу, но я предварительно обработал файл, создав еще один файл, в котором все строки «s1» заменены на «1», «s2» «с« 2 »и т. д., где« s1 »,« s2 »- это любые имена, отображаемые в виде вершин в файле, так что данные будут уплотнены в список пар int. В случае, если вы будете обрабатывать подобные данные позже (т. Е. Ваш график не сильно меняется и содержит в основном одинаковые имена вершин, сохраните файл «metadata» со ссылками от имен на int, чтобы облегчить дальнейшие предварительные обработки.

Answer 2

Основываясь на описании проблемы, которую вы предоставили, и ответах, которые вы предоставили в комментариях, я думаю, что самый простой способ сделать это может заключаться в использовании такого подхода, как описанный описанный @dreamzor. (

)

Основная идея состоит в том, чтобы преобразовать данные в более сжатый формат, который вписывается в память, запускать алгоритм регулярных подключенных компонентов для этих данных, а затем распаковывать его. Обратите внимание, что если вы назначаете каждый узла 32-разрядный цифровой идентификатор, тогда общее пространство, необходимое для хранения всех узлы не более чем на четыре миллиарда узлов и восемь миллиардов краев (при условии, что вы храните две копии каждого края), что составляет пространство для двенадцати миллиардов 32-разрядных целых чисел, всего около 48 ГБ пространства, ниже вашего порога памяти.

Для начала напишите сценарий, который читает в файле edge, назначает числовой идентификатор каждому узлу (возможно, последовательно в том порядке, в котором они появляются). Попросите этот сценарий записать это сопоставление в файл и, как говорится, напишите новый файл ребер, который использует числовые идентификаторы узлов, а не имена строк. Когда вы закончите, у вас будут идентификаторы сопоставления имен имен для имен и файл ребер, занимающий гораздо меньше места, чем раньше. Вы упомянули в комментариях, что вы можете поместить все имена узлов в память, поэтому этот шаг должен быть очень разумным. Обратите внимание, что вам не нужно хранить все ребра в памяти - вы можете передавать их через программу - так что это не должно быть узким местом.

Далее, напишите программу, которая считывает файл ребер, но не файл имен, в память и находит подключенные компоненты с использованием любого разумного алгоритма (BFS или DFS здесь будет замечательно).Если вы будете осторожны с вашей памятью (использование чего-то типа C или C++ здесь будет хорошим вызовом), это должно удобно вписываться в основную память. Когда все будет готово, выпишите все кластеры во внешний файл с помощью числового идентификатора. Теперь у вас есть список всех CCs по ID.

Наконец, напишите программу, которая читает в идентификаторе сопоставление узлов из файла имен, затем передает в идентификаторы кластера и записывает имена всех узлов в каждом кластере в конечный файл.

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