Какая структура данных графа наиболее эффективна в Python?

Мне нужно иметь возможность манипулировать большим (10^7 узлов) графиком в Python. Данные, соответствующие каждому узлу / ребру, минимальны, скажем, небольшое количество строк. Каков наиболее эффективный с точки зрения памяти и скорости способ сделать это?

Диктовка диктов является более гибкой и простой в реализации, но я интуитивно ожидаю, что список списков будет быстрее. Опция list также потребует, чтобы я держал данные отдельно от структуры, в то время как dicts допускает что-то в этом роде:

graph[I][J]["Property"]="value"

Что ты предлагаешь?


Да, мне следовало бы прояснить, что я имею в виду под эффективностью. В данном конкретном случае я имею в виду поиск с произвольным доступом.

Загрузка данных в память не является большой проблемой. Это сделано раз и навсегда. Часть времени занимает посещение узлов, поэтому я могу извлечь информацию и измерить интересующие меня метрики.

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

7 ответов

Решение

Я настоятельно рекомендую вам взглянуть на NetworkX. Это боевой конь, испытанный в бою, и первый инструмент, доступный большинству "исследовательских" типов для анализа сетевых данных. Я без проблем манипулировал графиками с сотнями тысяч ребер на ноутбуке. Его функция богата и очень проста в использовании. Вы обнаружите, что больше внимания уделяете проблеме, а не деталям базовой реализации.

Пример генерации и анализа случайных графов Эрдеша-Реньи


"""
Create an G{n,m} random graph with n nodes and m edges
and report some properties.

This graph is sometimes called the Erd##[m~Qs-Rényi graph
but is different from G{n,p} or binomial_graph which is also
sometimes called the Erd##[m~Qs-Rényi graph.
"""
__author__ = """Aric Hagberg (hagberg@lanl.gov)"""
__credits__ = """"""
#    Copyright (C) 2004-2006 by 
#    Aric Hagberg 
#    Dan Schult 
#    Pieter Swart 
#    Distributed under the terms of the GNU Lesser General Public License
#    http://www.gnu.org/copyleft/lesser.html

from networkx import *
import sys

n=10 # 10 nodes
m=20 # 20 edges

G=gnm_random_graph(n,m)

# some properties
print "node degree clustering"
for v in nodes(G):
    print v,degree(G,v),clustering(G,v)

# print the adjacency list to terminal 
write_adjlist(G,sys.stdout)

Визуализации также просты:

Дополнительная визуализация: http://jonschull.blogspot.com/2008/08/graph-visualization.html

Несмотря на то, что этот вопрос сейчас довольно старый, я думаю, что стоит упомянуть мой собственный модуль Python для манипулирования графами, называемый graph-tool. Это очень эффективно, поскольку структуры данных и алгоритмы реализованы на C++ с метапрограммированием шаблонов с использованием библиотеки графов ускорения. Поэтому его производительность (как в использовании памяти, так и во время выполнения) сравнима с чистой библиотекой C++ и может быть на несколько порядков лучше, чем в обычном коде Python, без ущерба для простоты использования. Я использую его постоянно для работы с очень большими графиками.

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

Словарь может также содержать накладные расходы, в зависимости от фактической реализации. Хеш-таблица обычно содержит некоторое простое число доступных узлов для начала, даже если вы можете использовать только пару узлов.

Судя по вашему примеру "Недвижимость", вам лучше использовать классовый подход для финального уровня и реальных свойств? Или имена свойств сильно меняются от узла к узлу?

Я бы сказал, что то, что означает "эффективный", зависит от многих вещей, таких как:

  • скорость обновления (вставка, обновление, удаление)
  • скорость поиска в произвольном доступе
  • скорость последовательного поиска
  • используемая память

Я думаю, вы обнаружите, что структура данных, которая является быстрой, обычно потребляет больше памяти, чем медленная. Это не всегда так, но большинство структур данных, похоже, следуют этому.

Словарь может быть простым в использовании и дать вам относительно равномерный быстрый доступ, он, скорее всего, будет использовать больше памяти, чем, как вы предлагаете, списки. Однако списки обычно содержат больше служебных данных, когда вы вставляете в них данные, если только они не выделяют X-узлы, в которых они снова будут использовать больше памяти.

В общем, я бы предложил просто использовать метод, который кажется вам наиболее естественным, а затем провести "стресс-тест" системы, добавив к ней значительное количество данных и посмотреть, не станет ли это проблемой.

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

Насколько я понимаю, произвольный доступ осуществляется в постоянном времени как для диктовок, так и для списков Python, разница состоит в том, что вы можете осуществлять произвольный доступ только к целочисленным индексам со списками. Я предполагаю, что вам нужно искать узел по его метке, так что вы хотите, чтобы диктовалось.

Тем не менее, с точки зрения производительности, загрузка его в память может не быть проблемой, но если вы используете слишком много, вы в конечном итоге перейдете на диск, что снизит производительность даже высокоэффективных команд Python. Постарайтесь максимально сократить использование памяти. Кроме того, оперативная память сейчас удивительно дешева; если вы много делаете такого рода вещи, нет причин не иметь по крайней мере 4 ГБ.

Если вам нужен совет по снижению использования памяти, предоставьте дополнительную информацию о том, какую информацию вы отслеживаете для каждого узла.

Создание структуры на основе классов, вероятно, будет иметь больше накладных расходов, чем структура на основе dict, поскольку в классах python фактически используются dicts, когда они реализованы.

Без сомнения, NetworkX - лучшая структура данных для графа. Он поставляется с такими утилитами, как вспомогательные функции, структуры данных и алгоритмы, генераторы случайных последовательностей, декораторы, упорядочивание Кутхилла-Макки, контекстные менеджеры.

NetworkX великолепен, потому что он хорош для графиков, орграфов и мультиграфов. Он может написать график несколькими способами: Список смежности, Многострочный список смежности, Список границ, GEXF, GML. Работает с Pickle, GraphML, JSON, SparseGraph6 и т. Д.

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

Другие вопросы по тегам