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

Question

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

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

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

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

---

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

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

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

Answer 1

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

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

"""
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

Answer 2

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

Answer 3

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

Answer 4

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

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

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

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

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

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

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

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

Answer 5

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

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

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

Answer 6

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

Answer 7

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

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

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