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

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

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

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

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

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

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

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

7 Solutions collect form web for “Какова наиболее эффективная структура данных графа в Python?”

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

Пример генерации и анализа случайных графов Erdős-Rényi

 """ 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 для манипуляции графами, называемом графическим инструментом . Это очень эффективно, так как структуры данных и алгоритмы реализованы на C ++, с метапрограммой шаблонов, используя библиотеку Boost Graph. Поэтому его производительность (как в использовании памяти, так и во время выполнения) сопоставима с чистой библиотекой C ++ и может на порядки лучше, чем типичный код python, не жертвуя простотой использования. Я постоянно использую его для работы с очень большими графиками.

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

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

Судя по вашему примеру, «Имущество», вы бы лучше походили на классный подход для конечного уровня и реальных свойств? Или имена свойств, изменяющихся много от узла к узлу?

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

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

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

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

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

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

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

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

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

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

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

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

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