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

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

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

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

Что бы вы предложили?

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

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

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

Ответы

Ответ 1

Я бы решительно выступал за то, чтобы вы посмотрели 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 ([email protected])"""
__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

Ответ 2

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

Ответ 3

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

Ответ 4

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

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

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

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

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

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

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

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

Ответ 5

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

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

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

Ответ 6

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

Ответ 7

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

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

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